けた数が多い数の乗算

はじめに, Rosetta code から 「長いかけ算 (Long multiplication)」を元にし, 長いかけ算の例題を実行してみる.

これは, 任意の精度で整数を取り扱う問題へのアプローチのひとつである.

ここでの例題は 2 の 64乗 = 18446744073709551616 から

18446744073709551616 * 18446744073709551616

という 2の64乗 同士のかけ算を実行し, その結果を確かめる.

340282366920938463463374607431768211456

Rosettacode では, 2の32乗 = 4294967296 = a とし, 「長いかけ算」を実行している. 2の32乗, 64乗, 128乗, 256乗は以下のようになった.

実行結果の例

eui Long_Multiplication.ex
a is 4294967296
a*a is 18446744073709551616
a*a*a*a is 340282366920938463463374607431768211456
a*a*a*a*a*a*a*a is 115792089237316195423570985008687907853269984665640564039457584007913129639936

念のために, かけ算の結果を go 言語でたしかめてみた.

go> Long_multiplication.exe
340282366920938463463374607431768211456
115792089237316195423570985008687907853269984665640564039457584007913129639936

どちらも Rosettacode サイトのソースコードを参考にした, 文字列に変換しながら長大なかけ算を実行するソースとなっている.

ソースサイズ

      1,301   Long_multiplication.ex
      1,508   Long_multiplication.go     

コードは, 15パーセントほど Euphotia の方が短いが, とくにサイズを意識して記述したものではないが, Euphoria の方が少し短く書ける.

Euphoria のコードは, 長いかけ算をどんな具合に計算したのだろうか. それを次に解説する.