巨大数演算

詳細

Ver.0.3-alpha9

加算と乗算の桁上げ処理を速くした他、桁揃えやゼロ削除専用の関数を追加。

Ver.0.3-alpha8

除算に含まれていたバグを修正。全ブラウザで414桁以上の平方根の計算が保障されます(多分)。ついでに求めた桁数をそのまま出力するのか、指定した桁数に整形して出力するのかを選択する機能を追加。

Ver.0.3-alpha7

平方根の計算時に、最初から目標桁数で計算するのではなく演算精度ギリギリで計算します。結果的に10倍以上高速化。ガウス・ルジャンドルで円周率を求めることができるぐらいの速度になった。

※平方根の計算は現時点ではIE以外でバグが発生します。現在デバグ中。

Ver.0.3-alpha6

マイナーチェンジ。使用ファイル数がやたら多かったので全てを1つにまとめた。

Ver.0.3-alpha5

今までは乗算計算の際、掛ける2数の長さをそれぞれAとBとした場合、AB/56回加算関数を呼び出していたが、筆算を応用しA/7回の呼び出しで計算を終了させられるようになった。

これによって、乗算関数・階乗関数の計算速度が桁違いに上がった。配列云々と言っていたが、これは配列でいかに高速化しようと考えた末に考えた手法で、配列で行っても良かったのだがそのまま現在の文字列型に組み込んだ。配列ならゼロを追加する処理が不要なのでさらに加速できそうだ。

Ver.0.3-alpha4

除算計算時の余分なゼロ減算を省いた結果、計算速度が2倍にアップ。

Ver.0.3-alpha3

累乗の剰余を求める関数を追加。これは素数判定やRSAなど用途色々。この辺りから除算関数の低速性が浮き彫りになってきた。数百桁の素数を判定しようと考えているので、除算は今後重要になるだろう。

乗算の高速化と同じ手法で除算も解決したい考え。

Ver.0.3-alpha2

巨大な10進数を2進数に変換する関数を追加。手元のマシンでは100桁の10進数を0.2秒で2進数に変換。

※36進数に変換するデモがありましたが、理論的に問題があったので削除しました。本当に36進数に変換されているかどうか検証したのち、復活させます。

Ver.0.3-alpha1

本格的な平方根関数を追加、10桁区切り関数を再構成、バグ修正

Ver.0.3-alpha0

マイナーチェンジ。

Ver.0.2-beta3

乗算時に呼び出される加算関数を乗算専用のものに変更。階乗と累乗の計算速度が飛躍的に上昇した。

1000!の計算に10秒もかからない。

Ver.0.2-beta2

階乗計算時に、たかが100かけるのに巨大数演算のライブラリを使わなくていいようにした。

Ver.0.2-beta1

巨大数演算による円周率計算のデモの動作速度を改善。余りを出力する割り算関数を追加。

Ver.0.1-beta1

円周率最優先のため、不完全であるが除算を実装。不完全なのでデモはなし。完全に実装でき次第演算デモをつける予定。また、引き算関数のバグを修正。(円周率が最優先なので、スクリプトには円周率を求めるものが含まれているが、これも最適化されていない)

Ver.0.1-alpha6

階乗計算時に出てくる末尾の0は計算時には余計なループを増やすだけなので0が増え次第削除しループ回数を抑えた。

100!を求めるのにかかった時間(Win32-MSIE6)

100!を求めるのにかかった時間(Win32-MSIE6)

Version	秒数
Ver.0.0.2	32.454sec
Ver.0.0.3	02.484sec
Ver.0.1-alpha1	00.515sec
Ver.0.1-alpha2	00.516sec
Ver.0.1-alpha3	00.156sec
Ver.0.1-alpha4	00.140sec
Ver.0.1-alpha5	00.078sec
Ver.0.1-alpha6	00.062sec

(これらの時間には微妙な誤差がある。)

Ver.0.1-alpha5

掛け算の右の0を代入するループ処理を減らし速度アップ

100!を求めるのにかかった時間(Win32-MSIE6)

Version	秒数
Ver.0.0.2	32.454sec
Ver.0.0.3	02.484sec
Ver.0.1-alpha1	00.515sec
Ver.0.1-alpha2	00.516sec
Ver.0.1-alpha3	00.156sec
Ver.0.1-alpha4	00.140sec
Ver.0.1-alpha5	00.078sec

(これらの時間には微妙な誤差がある。)

また、ルートXの平方根を求めるプログラムを追加したが方法がかなり古臭いのであまり期待しないでほしい。

Ver.0.1-alpha4

最後に計算結果に含まれる余分な0を削除するためのwhileループの総数を削減しわずかに加速。

100!を求めるのにかかった時間(Win32-MSIE6)

Version	秒数
Ver.0.0.2	32.454sec
Ver.0.0.3	02.484sec
Ver.0.1-alpha1	00.515sec
Ver.0.1-alpha2	00.516sec
Ver.0.1-alpha3	00.156sec
Ver.0.1-alpha4	00.140sec

(これらの時間には微妙な誤差がある。)

また計算とは直接関係ないが詳細なデバッグを装備させた。

Ver.0.1-alpha3

eval()で文字列を数値化する際、文字列の先頭に0が入ると文字列を10進数で数値化できなかった。 この問題を解決するため先頭の0を削除するwhileループを加えていたが、eval()の代わりにparseFloat()を用いて先頭に0があっても10進数に強制変換。 whileループ処理をカットした。結果、加算・減算・乗算の演算速度が平均2倍以上上がった。 又一部のwhileループをswitchに変更した。

100!を求めるのにかかった時間(Win32-MSIE6)

Version	秒数
Ver.0.0.2	32.454sec
Ver.0.0.3	02.484sec
Ver.0.1-alpha1	00.515sec
Ver.0.1-alpha2	00.516sec
Ver.0.1-alpha3	00.156sec

(これらの時間には微妙な誤差がある。)

四則演算プログラムの最適化は最終的に大きな速度アップにつながる。 これ以外の変更点として、8桁×8桁の掛け算に発生する誤差を防ぐため、8桁×7桁にした。 掛け算の演算速度は数％ダウンするが止む終えない処置。

Ver.0.1-alpha2

• 10桁区切りプログラムのバグを修正
• 累乗計算プログラムを追加

足し算・掛け算のプログラムはほとんどalpha1のまま。 唯一whileループをswitchに変えた個所があるのみ。 alpha2のメインは累乗計算で、2¹⁰⁰を手元のMSIE6では0.001秒以下で行います。 関数はAのB乗を計算するInvo(A,B);

Ver.0.1-alpha1

階乗のみを計算するプログラムだけ。具体的な変更は

• 加算関数を15桁区切りで計算→速度1500％アップ
• 乗算関数を6桁→8桁区切りで計算→速度56％アップ
• 階乗関数の動作を100!ごとに区切る→速度300％以上アップ

また、微細ではあるがforループ100万回とwhileループ100万回ではwhileのほうがわずかに速かったので、関数に使用される一部のforループをwhileに変更した。 alpha1.jsに内蔵されている関数についてはalpha1.js参照。

Ver.0.0.3

• 足し算再構成
• 引き算再構成
• 小数点対応
• 掛け算,演算速度36倍
• 階乗計算専用プログラム

6桁同時計算で計算速度を6²、つまり36倍に上昇させた。(100!の計算時間は34sec→2.5sec)実験したい方はMath.jsをダウンロードし外部JSファイルから適当なHTMLに読み込む。

足し算・引き算　Addition(A,B);

掛け算　Multiplication(A,B);

Factorial.jsには階乗計算　Factorial(A);　が内蔵されている。

Ver.0.0.2

デモには100!を計算するものがありますが手元で33秒かかったので注意してください。

Ver.0.0.1

• 足し算実装
• 引き算実装

小数点未対応。負の数も扱える。

1. 2数の符号を判断
2. 符号から加算プログラムを使うか減算プログラムを使うかを判定
3. 1桁ずつループ計算
4. 余分な行を削り符号をつける

Ver.0.0.0

そもそも円周率を求めるでJavaScriptで計算できる桁数に限界があったことから挑戦は始まった。

<計画>

• 足し算実装
• 引き算実装
• 掛け算実装
• 割り算実装
• 累乗計算実装
• 階乗計算実装
• 小数点対応

etc(とりあえずJavaScriptの全てのメソッドを独自のものに置き換える)