2011.07.24 Sunday
多倍長演算-掛け算-
掛け算のプログラムを書いた。
基数は4にとってみた。
多分基本的にはこういう感じなんだろう。
コマンドラインの二つの引数(10進数)を掛け算し、結果を4進数で表示する。
4進数を10進数表示にすることもしたかったがまだ出来ていない。
基数は4にとってみた。
多分基本的にはこういう感じなんだろう。
コマンドラインの二つの引数(10進数)を掛け算し、結果を4進数で表示する。
4進数を10進数表示にすることもしたかったがまだ出来ていない。
安直にコマンドライン引数をatoiで変換しているため、受け取れる最大値は
2^31-1=2147483647
である。これに3をかけるため、google先生によると6442450941となるはずである。
4進数では11333333333333331である。きちんと計算できている。
何も考えずにint型で結果を受け取ろうとするとオーバーフローする領域の
掛け算が可能となった。しかも、精度を上げることは簡単である。
単に配列のサイズをどんどん大きくしていくだけだから。
wikipediaで任意精度演算の項目に、「桁の精度がシステムの利用可能なメモリ容量
にのみ制限される計算技法」と書かれているのはこのことだ。
ただ、今回のような愚直なアルゴリズムだと4進数でN桁同士の掛け算の計算量は
O(N^2)となる。計算量の少ないアルゴリズムは色々存在しているらしい。
あと気になるのは小数を二進数でどう扱うかだ。勉強します。
2^31-1=2147483647
である。これに3をかけるため、google先生によると6442450941となるはずである。
4進数では11333333333333331である。きちんと計算できている。
何も考えずにint型で結果を受け取ろうとするとオーバーフローする領域の
掛け算が可能となった。しかも、精度を上げることは簡単である。
単に配列のサイズをどんどん大きくしていくだけだから。
wikipediaで任意精度演算の項目に、「桁の精度がシステムの利用可能なメモリ容量
にのみ制限される計算技法」と書かれているのはこのことだ。
ただ、今回のような愚直なアルゴリズムだと4進数でN桁同士の掛け算の計算量は
O(N^2)となる。計算量の少ないアルゴリズムは色々存在しているらしい。
あと気になるのは小数を二進数でどう扱うかだ。勉強します。