ACMプログラミングコンテストでは、多くの問題は多倍精度計算が必要とする。つまり、整数の桁数が数十、数百、数千となると必要になってくる。

このブログで書いた、多倍長整数関係の関数を使えばよいが、判りやすくするため、もう一度まとめてみる。

まずこれらの関数で使う N は、いまのGnu C コンパイラ環境に合わせ、N = 10000000 として使おう。つまり 1語の表現できる数は9桁10進数としよう。

で、多倍長整数では、1つの整数は以下の配列で表す。例えば、

   int num[50];

は49語の多倍長整数。num[0]には多倍長整数の語の数(長さ)が入っているので、実質数値として使うのは49語となるわけだ。

その49語で表現できる最大整数は約 49*9=441桁10進数となる。配列を大きく取れば何千桁の整数でも対応できるわけだ。

数値は1の位からnum[1]、num[2]、と入っていく。まず 0 (ゼロ) は
  num[0] = 0
と表現される。最小の自然数 1 は
  num[0] = 1,  num[1] = 1
。123456は
  num[0] = 1、num[1] = 123456
。つまり、N = 10000000 よりも小さい整数 K については、
  num[0] = 1,  num[1] = K
で使える。数値 789012345678901234567890 は
  num[0] = 3,  num[1] = 234567890,  num[2] = 345678901,  num[3] = 789012
。なお、マイナスの数値は多倍長整数では直接表現できない。その絶対値を多倍長整数で表現し、符号はほかの整数で表現しよう。

さて、多倍長整数の一般的な使い方だが、まず入力から、mpStr2Num( ) を使って、多倍長整数に変換しておく。四則演算はそれぞれの関数を使う。計算結果については、mpNum2Str( ) で文字列に直し、出力すればよい。

開平(平方根)の計算する関数はまだないが、暇があれば追加しておく。

Comments are closed.

Post Navigation