FLYING

〈全日本・紀文豆乳飲料シリーズ「麦芽コーヒー」の500ミリリットルパックを扱う小売店が少ないことに遺憾の意を表明する会〉活動記録

まだまだ多倍長整数

昨日の日記で理論的には無限の数を表現できると書いたけど、桁を扱う変数の制限から、現在の実装では 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億桁もあれば当分困らずに済みそうだな。

*1:今回実装した多倍長整数ライブラリでは位取り記数法を採用しており、この方法で表すことのできる数の最大値は [1つの位で表せる数量]^[確保できる桁数] - 1 で表せる。

*2:一般に、a桁の数とb桁の数を掛けると、最大でa+b桁になるため。