１億桁×１億桁の開発状況報告
いまさらですが、１億桁×１億桁の計算をしなければならない人ってこの世にいるのでしょうか・・・
あまり気にしすぎると体に悪いので、早速解説していきたいと思います
まず１億桁×１億桁の計算に絶対必要なのは多倍長の変数
普通の変数は９桁あたりで限界振り切ってしまいますが多倍長の変数
は何桁までいっても限界を振り切りません
そのためにlongint をプラグインとして使います
まず試しに１００万桁×１００万桁の掛け算を行います。
#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 "掛け算終了"
・・・・・・・・・・・・コピペして実行してみれば分かりますが
まず百万桁の変数を作るのに１分
百万桁×百万桁に１分１０秒
長い・・・・長すぎる・・・
こんなんで１億桁×１億桁の計算をやろうとすると、計算時間が尋常じゃないほど長くなります。
一応どのくらいかかるのかと言うと、桁数１００倍より１００^２=１００００だから
計算時間が１万倍になるので、掛け算部分だけでも７０００００秒！
日にちにして８．１日かかる！！
これに１億桁の数を生成＆複製の計算時間を含めるとさらに長く・・・
これではデバッグだけで１年が過ぎてしまう・・・
結論はつまり、「普通の掛け算」ではダメだということです！！！
何か、計算効率のいい掛け算方法（アルゴリズム）を考えなければいけません！
ちなみにわれわれがよく手動で計算する掛け算の手順
一桁一桁ずつかけて足して・・・という方法はじつはとてつもなく非効率な掛け算方法なのです！
ただ人間にとっては手順が単純明快なので、一番楽な方法として認識されてますが
コンピューターにやらせるのには向いてません
ここで、karatsuba法というけ掛け算アルゴリズムを採用します。
これは多倍長の桁を２分割して掛け算４回分の仕事を掛け算３回分と足し算４回に式変形する方法です。
足し算は掛け算と比べて計算時間が非常に短いのでないものと考えると、１回の分割で計算時間が３／４に減る
ことになります。
すると８回分割で計算時間がなんと１０分の１に半減します！
それでもまだ１つの掛け算に４０万桁×４０万桁の計算が必要なのでさらに５回分割して
１万２千桁×１万２千桁の掛け算になるまで分割すれば、計算時間が（３／４）^13≒0.024
だいたい４０分の１くらいに時間が抑えられることになります！
するとなんとたった５時間で、１億桁×１億桁を求められる計算になります！
おおー早い！！
これで、だいたいメドがついてきましたね！
あとはプログラムを打ち込むだけです。
karatsuba法をどうプログラムで再現するか、ここが一番力量が試されるところですが、
何せ計算手順が複雑なのでまだベースプログラムすら出来上がってません・・・
（一応自分が過去にＨＳＰコンテストに出した中で一つkaratsuba法を使った計算プログラムがあるのですが、また新しくプログラムを打ち直すつもりです）
なので詳しいkaratsuba法の計算についてはまたの機会にしたいと思います
次回：技術解説「ババドン」その３ 吸引アルゴリズム
