多倍長整数の演算

コンピュータが一度に処理できる整数の最大桁には，CPUが一度に扱える情報量に依存した限界がある。一度に扱える桁数を超える演算を行う一つの方法として，10を基数とした多倍長整数（以下，多倍長整数という）を用いる方法がある。

〔多倍長整数の加減算〕

多倍長整数の演算では，整数の桁ごとの値を，1の位から順に1次元配列に格納して管理する。例えば整数123は，要素数が3の配列に{3, 2, 1}を格納して表現する。

多倍長整数の加算は，“桁ごとの加算”の後，“繰り上がり”を処理することで行う。456＋789を計算した例を図1に示す。

クリックで拡大

図1　456＋789を計算した例

“桁ごとの加算”を行うと，配列の内容は{15, 13, 11}となる。1の位は15になるが，15は10×1＋5なので，10の位である13に1を繰り上げて{5, 14, 11}とする。これを最上位まで繰り返す。最上位で繰り上がりが発生する場合は，配列の要素数を増やして対応する。減算も同様に“桁ごとの減算”と“繰り下がり”との処理で計算できる。

〔多倍長整数の乗算〕

多倍長整数の乗算については，計算量を削減するアルゴリズムが考案されており，その中の一つにカラツバ法がある。ここでは，桁数が2のべき乗で，同じ桁数をもった正の整数同士の乗算について，カラツバ法を適用した計算を行うことを考える。桁数が2のべき乗でない整数や，桁数が異なる整数同士の乗算を扱う場合は，上位の桁を0で埋めて処理する。例えば，123×4は0123×0004として扱う。

〔ツリー構造の構築〕

カラツバ法を適用した乗算のアルゴリズムは，計算のためのツリー構造（以下，ツリーという）を作る処理と，ツリーを用いて演算をする処理から成る。ツリーは，多倍長整数の乗算の式を一つのノードとし，一つのノードは3個の子ノードをもつ。

M桁×M桁の乗算の式について，乗算記号の左右にある値を，それぞれM/2桁ずつに分けてA，B，C，Dの四つの多倍長整数を作る。これらの整数を使って，①A×C，②B×D，③(A＋B)×(C＋D)の3個の子ノードを作り，M/2桁×M/2桁の乗算を行う層を作る。(A＋B)，(C＋D)は多倍長整数の加算の結果であるが，ここでは“桁ごとの加算”だけを行い，“繰り上がり”の処理はツリーを用いて行う演算の最後でまとめて行う。生成した子ノードについても同じ手順を繰り返し，1桁×1桁の乗算を行う最下層のノードまで展開する。

1234×5678についてのツリーを図2に示す。図2の層2の場合，①は12×56，②は34×78，③は46×134となる。③の(C＋D)は，“桁ごとの加算”だけの処理を行うと，10の位が5＋7＝12，1の位が6＋8＝14となるので，12×10＋14＝134となる。

クリックで拡大

図2　1234×5678についてのツリー

この図の中に空欄 ア・イ があります

注記　この例では層3が最下層となる。

〔ツリーを用いた演算〕

ツリーの最下層のノードは，整数の乗算だけで計算できる。最下層以外の層は，子ノードの計算結果を使って，次の式で計算できることが分かっている。ここで，α，β，γは，それぞれ子ノード①，②，③の乗算の計算結果を，Kは対象のノードの桁数を表す。

α×10^K ＋ （γ－α－β）×10^(K/2) ＋ β　……(1)

図2のルートノードの場合，K＝4，α＝672，β＝2652，γ＝6164なので，計算結果は次のとおりとなる。

672×10000＋(6164－672－2652)×100＋2652＝7006652

〔多倍長整数の乗算のプログラム〕

桁数が2のべき乗の多倍長整数val1，val2の乗算を行うプログラムを作成した。

プログラム中で利用する多倍長整数と，ツリーのノードは構造体で取り扱う。構造体の型と要素を表1に示す。構造体の各要素には，構造体の変数名.要素名でアクセスできる。また，配列の添字は1から始まる。

多倍長整数の操作を行う関数を表2に，プログラムで使用する主な変数，配列及び関数を表3に，与えられた二つの多倍長整数からツリーを構築するプログラムを図3に，そのツリーを用いて演算を行うプログラムを図4に，それぞれ示す。表2，表3中のp，q，v1，v2の型は多倍長整数である。また，図3，図4中の変数は全て大域変数である。

注記　図4中のエには，図3中のエと同じ字句が入る。