普通の演算ブロックでは自然数の範囲で2^53以上になると浮動小数点とかがいろいろあって不正確になります。そこで、筆算などのアルゴリズムをプログラムすることで、何桁でも計算することができます。 Demoは2^4096を計算しています。 モンゴメリ乗算実装したいけどよくわからない。 足し算 ... 筆算 普通に筆算で計算しています。それより速いアルゴリズムは多分ありません。高速化する工夫として、15桁ずつ一気に計算しています。 引き算 ... 筆算 足し算と同じで普通に筆算で計算しています。それより速いアルゴリズムはこれも多分ありません。高速化する工夫として、やっぱり15桁ずつ一気に計算しています。 掛け算 ... カラツバ法 これは筆算より速いカラツバ法という方法で計算しています。例えば2桁x2桁の計算をするときには筆算だと1桁の筆算が4回必要ですが、これが3回になります。( 代わりに足し算や引き算の回数が増えますが、掛け算の方が時間がかかるので、高速化が可能です。) もっと速い方法に「Toom-3」「ショーンハーゲ・ストラッセン法」などがありますが、前者はなんとなく嫌いなので、後者は理解できないので、実装していません。 割り算 ... ニュートン・ラフソン法 割り算も筆算より速い方法があります。逆数関数の微分関数を利用して計算する方法です。筆算より圧倒的に速いです。 更新記録 2021/03/21 v1.0 共有 2021/03/22 v1.1 掛け算は結果が800桁以下なら筆算するように改良 ( @watashida さんの指摘 ) 2021/03/26 v1.2 リストの書き換えより変数の書き換えの方が時間がかからない ( 経験上 ) ので、カラツバ法以外の大部分を変数に変更。掛け算と割り算の右の数が小さい場合、筆算のような方法で計算するように変更。 2021/03/28 v1.3 カラツバ法が思いっきりバグっていたので修正。ついでに剰余を右の項が小さいときに筆算に変更。 2021/05/03 v1.4 平方根を追加。計算方法はニュートン法。
