まだまだ多倍長整数
昨日の日記で理論的には無限の数を表現できると書いたけど、桁を扱う変数の制限から、現在の実装では 0 〜 65536^65534 - 1 までしか表せないことに気付いた*1。更に、2つの多倍長数を掛け算する場合は、2数の桁数の合計が 65535 を超えてはいけないことも発覚した*2。
じゃあ、その 65536^65534 - 1 っていくつなのか知りたいと思うんだけど、Windowsの電卓で計算したら無効だと言われてしまった。仕方ないので常用対数を使っておおよその値を調べたら、だいたい10進数で30万桁をオーバーするくらいの数字らしい。微妙に小さいような、でかいような。
表せる数を増やすには、1つの位で表せる数を増やしてやるのが手っ取り早い。現在1つの位の最大値は 65535 (USHRT_MAX) になっているので、これを 4294967295 (ULONG_MAX) にしてやると、全体で表すことのできる最大値は 4294967296^4294967294 - 1 まで増える。これはだいたい10進数で413億桁ぐらいの数。
仮に、その413億桁の数をハードディスクにテキストで保存したとすると、41.3GBぐらいになる。うーん、413億桁もあれば当分困らずに済みそうだな。
