最終更新日:2003.11.29
多倍長整数以下の一連の文書では、多倍長整数の実装に用いられる典型的なアルゴリズムを論じ、C言語によって具体的な実装を与える。
多倍長整数とは、コンピュータに巨大な整数を扱わせるための仕組みである。
実在する多くのコンピュータの演算装置は、初めからある程度の大きさまでの整数を演算できるように作られている。例えば、2003年現在個人用としてIntel x86シリーズを搭載したコンピュータが広く普及しているが、これは32bitの整数を演算するための機械語を持っている。しかし、これだけでは十分でないことがある。32bitでは0〜232-1=4294967295の範囲しか表すことができない。本格的な商用計算や科学技術計算、暗号のような特定の処理をするためには4294967295というのは小さすぎるのである。
そこで、何らかの方法で巨大な整数をコンピュータ上に表現し、演算することが必要となる。そのための方法が多倍長整数である。
いくつかのプログラミング言語には、言語処理系の機能として多倍長整数の処理が組みこまれている。あるいは、言語の標準ライブラリとして多倍長整数処理が実装されている。ALGOL系では例えばJavaやPythonやRubyがそうであるし、多くのLisp方言もそうである。
しかし、多倍長整数処理を提供していない言語も多く、そのような言語、例えばC言語では何らかの形で自前で多倍長整数処理を調達しなければならない。
まずは自然数のみを考えるものとする。コンピュータ上で巨大な自然数を表現するためには、通常は適当な基数rを取って、自然数のr進数表記を用いる。このことによって巨大な自然数の演算をコンピュータが直接演算できるような小さい整数の演算に還元することができる。
例えば、我々が日常用いるr=10の10進数では、0,1,2,3,4,5,6,7,8,9という10種類の記号のみを用いて必要なだけこれを並べ、任意に大きな自然数を表したり計算したりすることができる。
r=10というのは恐らく、現在使われるコンピュータにとっては小さすぎる。rが大きすぎるとコンピュータが直接演算できる範囲を逸脱してしまうのだが、それにしてももう少し大きなrを使った方が効率がよい。例えば、上に述べたIntelの32bitアーキテクチャにおいてはr=232とでもするのが適当だろう。232進数で自然数を表したときの各桁は0〜232-1の範囲になるので、演算装置にきちんと計算させることができる。
0〜rを格納できる符号なし整数型digit_tがあったとすると、次のようなイメージである。
struct multiprec_natural
{
size_t len; /* digitsがポイントする配列の要素数 */
digit_t *digits; /* 各桁を表すdigit_tの配列の、先頭へのポインタ */
};
さて、自然数を表現できるようになったところで、今度は負数をどのように表現するかを考える。幾つかの考え方がある。
固定長整数で負数を表すための標準的な方法である。しかし、残念ながらこの方法で多倍長整数を実装しようとすると乗除算のコストがかなり高くなりそうである。
これは人間が10進数で負数を表記するときに、頭に負符号を付けて負数を表現するのと同じである。最も単純な発想であり、比較的安価な考えである。
負数基数、例えば、-232進数を使うというのはなかなか面白そうな考えである。普通r進数と言ったときには基数rには正整数を使うものであるが、基数に負数をとると符号ビットなしで正負の数を統一的に扱うことができる。しかし、一般に正数基数に比べて桁数が2倍程度になってしまう。つまりは、計算にコストがかかると言うことである。
ここでは詳しくは論じないが、Knuthの凖数値算法（下）にはもう少し説明されている。
個人的に負数基数の採用は魅力的な誘惑であるが、ここでは標準的な「符号ビットと絶対値を別に持つ」方式を採用する。
メモリー節約のために、桁数を保持するメンバー.lenの最上位ビットに符号ビットを格納する方法もある。実用上、最上位ビットが必要になるほど桁が長くなることはまずないからである。しかし、ソースコードが読み辛くなるため、ここではそれは採用しない。符号を表す列挙型を定義して符号ビットを格納することにする。
struct multiprec
{
enum {positive_sign=0, negative_sign=1} sign; /* 符号 */
size_t len; /* digitsがポイントする配列の要素数 */
digit_t *digits; /* 各桁を表すdigit_tの配列の、先頭へのポインタ */
};
さて、上のように多倍長整数を表すことのできる構造体が定義できたが、これには一つ難点がある。つまり、演算の結果として桁数が変化した場合にどうするかと言う問題である。例えば、加法の結果として桁数が増えたらどうすればよいか。
これに対する一つの回答はオブジェクトをimmutableにするということである。つまり、加法を行うたびに新しいstruct multiprecインスタンスを確保し、和はその新しいオブジェクトに格納する。このようにすれば、引数として渡された元々の構造体は変化しないのだから、桁数が変化するという問題を考えなくてよい。オブジェクトをimmutableにすることによってその他の面でも実装は単純になるし、ライブラリを使う側としても共有オブジェクトにまつわる様々な問題を考えなくて済むので利点は多い。
例えば、Rubyに組み込まれたBignumクラスや、JavaのBigIntegerクラスなどはこの方式を採用している（Pythonのことはよく知らない）。
一方、オブジェクトをimmutableにすることによって演算を行うたびにたくさんのオブジェクトが生成されることになる。これは実行速度を落としかねない。数値計算における整数の位置づけから言って、かなり多くの演算が行われることは容易に想像できる。こういう検討の結果なのか、GMPではの多倍長整数型mpz_tはmutableである。ここでは、GMPと同様にstruct multiprecをmutableなものとする。
さて、mutableであるからには、先ほどの桁数変化時の問題を別のやり方で何とかしなければならない。単純な発想としては、桁数が変化するたびに.digitsがポイントする動的メモリーを再確保すればよい。しかし、動的メモリーの再確保はかなり時間の掛かる操作であるから、できることなら避けたいところである。
ここでは、安易ではあるが次のような解決法を採用する。つまり、「.digitsがポイントする領域が余っている分にはよいことにする」。そして、.digitsがポイントする長さ.lenの動的配列において、実際に多倍長整数の桁が格納されている部分の長さを.usedというメンバーに別に保持しておくことにする。これにより、動的メモリーの再確保は最低限の回数で済む。
struct multiprec
{
enum {positive_sign=0, negative_sign=1} sign; /* 符号 */
size_t len; /* digitsがポイントする配列の要素数 */
size_t used; /* digitsがポイントする配列のうち、現在使われている要素数 */
digit_t *digits; /* 各桁を表すdigit_tの配列の、先頭へのポインタ */
};
ここでは、C言語による多倍長整数の実装を行ないながらそのアルゴリズムを説明する。その実装をとりあえずYMPと名付けた。
YMPは基本的には「私の趣味」＋「教育用」として書かれている。多倍長整数処理の高速化に使われる極基本的なアイディアは使われているものの、あまりにも技巧的なものはあえて採用しなかった。
YMPは、移植性を無視はしていないが追求もしていない。GNU autotoolを使えばもっと移植性を上げられるのは分かっているが、ソースの簡潔さを優先して採用しなかった。
YMPは主にRedHat Linux上のgccで開発されているが、multiprec.hの数行を書き換えれば次の条件を満たす環境ではコンパイルできるだろう。
YMPの最新版はymp.tar.gzに置いてある。
ライセンスはGPLを適用する。