1億桁×1億桁の開発状況報告
いまさらですが、1億桁×1億桁の計算をしなければならない人ってこの世にいるのでしょうか・・・
あまり気にしすぎると体に悪いので、早速解説していきたいと思います
まず1億桁×1億桁の計算に絶対必要なのは多倍長の変数
普通の変数は9桁あたりで限界振り切ってしまいますが多倍長の変数
は何桁までいっても限界を振り切りません
そのためにlongint をプラグインとして使います
まず試しに100万桁×100万桁の掛け算を行います。
#include "longint.hsp"
a=LongInt(1)
repeat 100000;百万桁の数を生成
a*=LongInt("10000000000")
loop
b=LongInt(a);百万桁の数を複製
c=longint(0)
wait 2
mes "掛け算開始"
wait 1
c=a*b
mes "掛け算終了"
・・・・・・・・・・・・コピペして実行してみれば分かりますが
まず百万桁の変数を作るのに1分
百万桁×百万桁に1分10秒
長い・・・・長すぎる・・・
こんなんで1億桁×1億桁の計算をやろうとすると、計算時間が尋常じゃないほど長くなります。
一応どのくらいかかるのかと言うと、桁数100倍より100^2=10000だから
計算時間が1万倍になるので、掛け算部分だけでも700000秒!
日にちにして8.1日かかる!!
これに1億桁の数を生成&複製の計算時間を含めるとさらに長く・・・
これではデバッグだけで1年が過ぎてしまう・・・
結論はつまり、「普通の掛け算」ではダメだということです!!!
何か、計算効率のいい掛け算方法(アルゴリズム)を考えなければいけません!
ちなみにわれわれがよく手動で計算する掛け算の手順
一桁一桁ずつかけて足して・・・という方法はじつはとてつもなく非効率な掛け算方法なのです!
ただ人間にとっては手順が単純明快なので、一番楽な方法として認識されてますが
コンピューターにやらせるのには向いてません
ここで、karatsuba法というけ掛け算アルゴリズムを採用します。
これは多倍長の桁を2分割して掛け算4回分の仕事を掛け算3回分と足し算4回に式変形する方法です。
足し算は掛け算と比べて計算時間が非常に短いのでないものと考えると、1回の分割で計算時間が3/4に減る
ことになります。
すると8回分割で計算時間がなんと10分の1に半減します!
それでもまだ1つの掛け算に40万桁×40万桁の計算が必要なのでさらに5回分割して
1万2千桁×1万2千桁の掛け算になるまで分割すれば、計算時間が(3/4)^13≒0.024
だいたい40分の1くらいに時間が抑えられることになります!
するとなんとたった5時間で、1億桁×1億桁を求められる計算になります!
おおー早い!!
これで、だいたいメドがついてきましたね!
あとはプログラムを打ち込むだけです。
karatsuba法をどうプログラムで再現するか、ここが一番力量が試されるところですが、
何せ計算手順が複雑なのでまだベースプログラムすら出来上がってません・・・
(一応自分が過去にHSPコンテストに出した中で一つkaratsuba法を使った計算プログラムがあるのですが、また新しくプログラムを打ち直すつもりです)
なので詳しいkaratsuba法の計算についてはまたの機会にしたいと思います
次回:技術解説「ババドン」その3 吸引アルゴリズム