多倍長整数の掛け算

プログラム言語で使える整数の変数は通常はサイズが決まっており、それ以上の大きさの整数を扱うことができない。例えばC++のint型は通常32bitなので2^32 - 1 = 4294967295(ゼロを含むので-1がある)までしか扱えない。signedなら負の値も使うのでその半分までである。もしそれを超えるような大きな整数を計算したい場合は色々と工夫が必要です。

私が初めて多倍長整数の掛け算を実装したのは確か中学生のころだったと思われる。何を計算したかったかは忘れてしまったが単純に大きな数字が見たかっただけかもしれない。当時使っていた言語はN88Basicで、当時の私にメモリの概念や知識が殆どなく、配列の一つ一つに10進数の桁の値を入れて普通に筆算を計算していた。なお実装で一番苦労したのは計算そのものよりその表示だった覚えがある。その後、また実装する機会があった(例によって理由は覚えていない)のだが、その時は10進数である必要がないことに気が付いて１万進数とかで計算していた。10進数ベースなところが相変わらずメモリ構造とか知識がなかったようだ。

さて、最近になってまた実装する機会ができた。理由はLucas–Lehmer primality testを実装してみたくなったから。現在ではメモリ構造とかの知識があるのでより効率的な実装ができた。しかし試しにpythonで簡単に作ったLucas–Lehmer primality testに比べて桁外れに遅かったことに疑問を覚えた(ちなみにpythonはdefaultで多倍長整数になっており扱える整数の上限がないので実装が簡単。同時に普通の整数演算が遅い原因でもある)。いろいろと調べて分かったことだが、多倍長整数の掛け算はいろいろ研究されており、通常の筆算ならO(N^2)の計算量があるのに対し、例えばカラツバ法という計算方法ならO(N^long2(3))ですむ。pythonの整数計算ではカラツバ法が使われているらしく、それで計算時間に大きな差があったらしい。

多倍長整数の掛け算でよく使われるアルゴリズムはカラツバ法の他にショーンハーゲ・ストラッセン法という方法がある。桁が大きくなってくるとこちらの方が速いらしい。というわけでこちらの実装を試そうと思ったがなかなか難しい。原理は理解したが環の選び方等、細かい部分の理解が足りず実装できずにいる。わざわざ自分で実装せずともGMP等のライブラリが存在するのだが、試しにGMPを使ってみたがおそらくSIMDやThread並列は使われておらずまだまだ速くする余地はありそうである。なのでやはり自作してみることにする。