１億桁×１億桁の開発状況報告２
前はkaratsuba法の名前が出てくるところまで話が進んだんですよね？
前も言いましたがlognint.dllとは、ものすごいながい桁数の数値も計算できるようにするためのプラグインです。
これを使います。
ＨＳＰユーザーでこれを使ってる人はなかなか見ないもんで、その技術解説をしているホームページなども見ないので、このブログがＨＳＰユーザーとして一番最初に詳しくlognintについて技術解説することになりそうです！！
なんかうれしい！！
もともと私は四則演算とか（自称）とても得意なんで、一般の人には負けないつもりです！
さてkaratsuba法のプログラムについてですが
ちょっとプログラム的な話ではなく、ほんと数学的な話になりそうですが、まぁ仕方ないですが、許してください
karatsuba法は一言で言うと、とても長い桁数を演算するときに使え、計算手順を効率よくすることで計算時間を短くするという方法の一つです。
実はもっと効率のいい高速フーリエ変換という方法もあるのですが、自分の技術不足でkaratsubaが限界です・・・・
さて実際の手順ですが、
まず四則演算の計算で一番時間がかかるのが掛け算、割り算。
桁数に比例して時間が伸びます。
足し算引き算は、掛け算と比べほとんどゴミのようなものです。
なので、効率化するべきは掛け算です。（割り算は置いておく）
ここでちょっと分かりやすく、１０桁×１０桁の掛け算を考えます。
本当は千桁くらいから使わないと意味がないのですが
例えば１３８４５０１２３９×５６７８２２１０９８の計算
このとき、普通
a=１３８４５０１２３９
b=５６７８２２１０９８
c=a*b
とこうやりますね？
ここで、桁数を最大５桁に制限し変数を分割することを考えます。
a1=１３８４５
a2=１２３９
b1=５６７８２
b2=２１０９８
とし
c=a1*b1*10^10+(a1*b2+a2*b1)*10^5+a2*b2
とこうするとします。
ここで*10^10と*10^5は、変数上でも後ろに0がつくだけなので計算時間がまったくかからないものとします
一つ一つの掛け算が５桁×５桁になったので、１０桁にときと比べると４分の１になったにですが、これでも、掛け算が合計４つになり、結局計算時間的にはなにも変わりません。
ここでやっとkaratsuba法の登場
括弧でくくりまくって
c=(a1*b1)*10^10+(a2*b2)-((a1-a2)*(b1-b2)+(a1*b1)+(a2*b2))*10^5
とこうします。
一見掛け算が増えたように見えますが、a1*b1とa2*b2のところが２箇所ずつあります
だからそこの計算はしなくていいのです。
簡潔に書くと
c1=a1*b1
c2=a2*b2
c=c1*10^10-((a1-a2)*(b1-b2)+c1+c2)*10^5+c2
とこうなります！
よく見てみると*10^10とか省くと、掛け算が３回に減っています！
これが計算の効率化です。
さっきまでずっと、*10^10をの計算時間を省くのを気にしている人がいるかもしれません
が、実際の計算で、計算結果を一つの変数にまとめなければいけないというルールはありません。
１億桁の計算結果を出力するプログラムでは、１万桁ずつ１万個の変数に区切って出力する方法をとっても
なんら問題はおきないのです（当然繰り上がり処理は別途必要になります）
だから、「この変数は10^10が本来かかっている数」として自分の中で考えておけば、わざわざコンピューターに
*10^10の計算をやらせる必要はなくなるのです。
このようにして掛け算が効率化されました。
次のハードルは、karatsuba法の帰納的活用法です。
４回から３回に減った掛け算の中でさらにまたkaratsuba法を適応して計算時間を４分の３に減らします
