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( ) で文字列に直し、出力すればよい。

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

<関数名>
  mpNum2Long 多倍長整数をlong整数値に変換する

<形式>
  int mpNum2Long(unsigned long *ul, int *num);

<引数>
  ul  (出力) 対応した符号なしlong整数値
  num (入力) 多倍長整数

<関数値>
  変換できなかったときは -1、OK 時は 0。

<注意事項>
  配列の各要素 ai(i は 1 以上)は1語を表し、1語で表し得る最大の整数は 9999 。語の長さは a0 の値で表す。すなわち、多倍長整数は

      anKn-1+an-1Kn-2+…+a2K+a1

   で表現する。ただし、K=10000、n=a0
  
用例
  本関数以外に、キー入力に 関数 mpStr2Num()数字列を多倍長整数に も使う。

<関数本体>
  mpNum2Long.c

<説明>
  変換したい多倍長整数が、最大の符号なしlong整数値よりも大きい場合は、変換不可とする。

C言語でよく使うlong整数値を、多桁数整数に変換する関数。

色々な計算に、本関数があると便利な場合が多い。

<関数名>
  mpLong2Num —- long整数値を多倍長整数に変換する

<形式>
  void mpLong2Num(int *num, unsigned long ul);

<引数>
  num (出力) 変換された多倍長整数
  ul   (入力) 符号なし long整数値

<関数値>
  なし

<注意事項>
  配列の各要素 ai(i は 1 以上)は1語を表し、1語で表し得る最大の整数は 9999 。語の長さは a0 の値で表す。すなわち、多倍長整数は

      anKn-1+an-1Kn-2+…+a2K+a1

   で表現する。ただし、K=10000、n=a0
  
用例
  本関数以外に、画面表示に 関数 mpNum2Str()多倍長整数を数字列に)も使う。

<関数本体>
  mpLong2Num.c

最後の印刷や画面表示の際に必要となってくる関数。

<関数名>
  mpNum2Str —- 多倍長整数を数列に変換する

<形式>
  void mpNum2Str(char *str, int *num);

<引数>
  str  (出力) 対応した数字列
  num (入力) 多倍長整数

<関数値>
  なし

<注意事項>
  配列の各要素 ai(i は 1 以上)は1語を表し、1語で表し得る最大の整数は 9999 。語の長さは a0 の値で表す。すなわち、多倍長整数は

      anKn-1+an-1Kn-2+…+a2K+a1

   で表現する。ただし、K=10000、n=a0
  
用例
  本関数以外に、キー入力に 関数 mpStr2Num()数字列を多倍長整数に)も使う。

<関数本体>
  mpNum2Str.c

数字列を多倍長整数のフォーマットに変換してくれる関数。

キー入力の際に必要となる。

<関数名>
  mpStr2Num —- 数字列を多倍長整数に変換する

<形式>
  void mpStr2Num(int *num, char *str);

<引数>
  num (出力) 変換された多倍長整数
  str  (入力) 数字列

<関数値>
  なし

<注意事項>
  配列の各要素 ai(i は 1 以上)は1語を表し、1語で表し得る最大の整数は 9999 。語の長さは a0 の値で表す。すなわち、多倍長整数は

      anKn-1+an-1Kn-2+…+a2K+a1

   で表現する。ただし、K=10000、n=a0
  
用例

<関数本体>
  mpStr2Num.c

整数同士の比較。

<関数名>
  mpCmp —- 多倍長整数同士の大小比較

<形式>
  int mpCmp(int *a, int *b);

<引数>
  a, b 多倍長整数

<関数値>
  aはbよりも大きい場合は正の値、小さい場合は負の値、等しい場合はゼロの値

<注意事項>
  配列の各要素 ai(i は 1 以上)は1語を表し、1語で表し得る最大の整数は 9999 。語の長さは a0 の値で表す。すなわち、多倍長整数は

      anKn-1+an-1Kn-2+…+a2K+a1

   で表現する。ただし、K=10000、n=a0
  
用例
  本関数以外に、キー入力に 関数 mpStr2Num()数字列を多倍長整数に)、画面表示に 関数 mpNum2Str()多倍長整数を数字列に)も使う。

<関数本体>
  mpCmp.c

<説明>
  語数の大きさをまず比べる。同じ語数ならば、上位語より順に比べていけばよい。

桁数の長い整数同士の割り算。

整数の世界から逃げ出す不思議な計算。実数の世界に通じるトンネルのようなものかな。計算結果としての有理数、無理数。言葉の遊びとも受け止められるかもしれないけど、大変深い洞察に基づく概念。

<関数名>
  mpDiv —- 多倍長整数同士の除算

<形式>
  int mpDiv(int *q, int *r, int *a, int *b);

<引数>
  q   (出力) 多倍長整数同士の除算の商
  r   (出力) 多倍長整数同士の除算の余り
  a, b (入力) 多倍長整数 (a が被除数、b が除数)

<関数値>
  正常に計算できたときは 0。失敗したときは -1。除数が 0 のときは -2。

<注意事項>
  配列の各要素 ai(i は 1 以上)は1語を表し、1語で表し得る最大の整数は 9999 。語の長さは a0 の値で表す。すなわち、多倍長整数は

      anKn-1+an-1Kn-2+…+a2K+a1

   で表現する。ただし、K=10000、n=a0
  
用例
  本関数以外に、キー入力に 関数 mpStr2Num()数字列を多倍長整数に)、画面表示に 関数 mpNum2Str()多倍長整数を数字列に)も使う。

<関数本体>
  mpDiv.c

<説明>
  除算は四則演算の中に最もやっかいな計算である。ほかの演算と異なる点は、商の各桁の値の「見当をつける」という操作が含まれる点である。なるべく少なく手間で、適切な商の候補をみつけることが、プログラムの繁雑さを増してしまう。

多桁数の整数同士の掛け算についてだ。

<関数名>
  mpMul —- 多倍長整数同士の乗算

<形式>
  void mpMul(int *ret, int *a, int *b);

<引数>
  ret (出力) 多倍長整数同士の乗算の結果(a * b)
  a, b (入力) 多倍長整数

<関数値>
  なし

<注意事項>
  配列の各要素 ai(i は 1 以上)は1語を表し、1語で表し得る最大の整数は 9999 。語の長さは a0 の値で表す。すなわち、多倍長整数は

      anKn-1+an-1Kn-2+…+a2K+a1

   で表現する。ただし、K=10000、n=a0
  
用例
  本関数以外に、キー入力に 関数 mpStr2Num()数字列を多倍長整数に)、画面表示に 関数 mpNum2Str()多倍長整数を数字列に)も使う。

<関数本体>
  mpMul.c

<説明>
  乗算は加減算ほど単純でなく、いろいろ工夫の余地がある。実用上または理論上の観点から興味深い方法がいくつも考えられている。

  乗算について考えよう。a、bをそれぞれm、n語とすると、積c=a*bはm+n 語以下となる。通常の筆算と同様の方法で、乗数bの1語ごとをaに掛け、それらの和は積cとなる。

  この方法では、bのn語をそれぞれaのm語に掛けるので、m*n回の繰り返しとなる。したがって、計算に必要な時間はO(mn)。

多桁数の整数同士の引き算。

<関数名>
  mpSub —- 多倍長整数同士の減算

<形式>
  void mpSub(int *ret, int *a, int *b);

<引数>
  ret (出力) 多倍長整数同士の減算の結果 (a – b)
  a, b (入力) 多倍長整数 (a は b よりも大きいか等しい)

<関数値>
  なし

<注意事項>
   a は必ず b よりも大きいか等しいでなければならない。
  配列の各要素 ai(i は 1 以上)は1語を表し、1語で表し得る最大の整数は 9999 。語の長さは a0 の値で表す。すなわち、多倍長整数は

      anKn-1+an-1Kn-2+…+a2K+a1

   で表現する。ただし、K=10000、n=a0
  
用例
  本関数以外に、キー入力に 関数 mpStr2Num()数字列を多倍長整数に)、画面表示に 関数 mpNum2Str()多倍長整数を数字列に)も使う。

<関数本体>
  mpSub.c

<説明>
  10進数の計算と同じように、下語より引き算を実行する。上の語より「借り」が必要なときは、上の語に1を余分に引く。

どんなに桁数が長くても、整数同士の四則計算等を誤差なくやってくれる関数の紹介。

何百桁とか、長い整数を扱うのにいまのコンピュータは得意ではない。実数でも精度(いわゆる有効桁数)もそれほど高く保もたれていない。皆さんの普段使ってる電卓でもそう。液晶の表示部分は10桁とか、それぐらい。100桁も表示する電卓なんてないし、内部的にも有効桁数を沢山取って計算しているわけでもない。

しかし、われわれ普段習ってる数学では、数の有効桁数とか、使う範囲とかは考えない。理想的なものとしか扱わないから。無限大という数もふつうに使える。コンピュータでは絶対無理だけどね。

つまり、われわれ人間は数を概念的・記号的に思考するのは得意だが、ちょっとした計算、例えば、5,6桁の数同士の掛け算・割り算でもなかなか速くできないし、よく間違う。一方、コンピュータは計算が超得意だけど、記号とかになると苦手になることが多い。そう考えれば、人間とコンピュータとの合体、超高性能なコンピュータを腕時計や携帯のように、いつも持ち歩き、使うくことができれば、あるいは、人体に直に埋め込むことができれば、凄いことになりそう。

<関数名>
  mpAdd —- 多倍長整数同士の加算

<形式>
  void mpAdd(int *ret, int *a, int *b);

<引数>
  ret (出力) 多倍長整数同士の加算の結果(a + b)
  a, b (入力) 多倍長整数

<関数値>
  なし

<注意事項>
  配列の各要素 ai(i は 1 以上)は1語を表し、1語で表し得る最大の整数は 9999。語の長さは a0の値で表す。すなわち、多倍長整数は

     anKn-1+an-1Kn-2+…+a2K+a1

  で表現する。ただし、K=10000、n=a0
  
用例
  本関数以外に、キー入力に 関数 mpStr2Num()数字列を多倍長整数に)、画面表示に 関数 mpNum2Str()多倍長整数を数字列に)も使う。

<関数本体>
  mpAdd.c

<説明>
  10進数の計算と同じように、下語より加えていく。和が10000 を超えたら桁上がりが発生し、上の語に1を余分に加える。