大きな整数の計算

目次

N88-BAISCで2^64の計算

ハノイの塔の話をしたときに64枚のときの手数を計算しようという生徒がいて、電卓でなんか計算できる数でないと忠告したら、筆算でやって持ってきました。64枚はゲームのストーリーの中の移動が終わると世界も終わりになるという数です。今でこそウェブページで検索すると情報がたくさんでてきますが、1988年のお話。

当時のPCはBASICで整数は最大で2バイト。16ビットですから符号なしで使っても2の16乗-1、普通の計算では符号付きですから15乗-1までしか計算できないわけです。浮動小数点数を使って1.84467e+19では筆算を確認することはできません。

そこで、配列を使って10進のレジスタを作って計算しようということにしたのです。

n枚のハノイの塔の移動はn-1枚の移動をしておいて最も下の1枚を動かし、再度n-1まいをその上に移動するのですから、レジスタの足し算を用意すればいいわけです。

もう一つ必要な機能は配列を一つの十進数として表示する部分です。

この2つを ADD, PRT のサブルーチンとして繰り返し呼び出すことにすればよいわけです。

プログラムはBywater BASIC で動かすための改変例で紹介しました。

答えは

18446744073709551615

になります。

前の話の生徒の計算は途中で一箇所間違えていてちょっと残念な結果でした。

プログラムリストによりますと、1990年に2の累乗を計算する部分を追加しています。2nは2倍を繰り返すことですから、つまりは同じものを足すことを繰り返すことでできます。累乗と言いながら足し算で済んでしまいます。ハノイのプログラムのサブルーチンを再利用できるわけです。

最近の言語では普通にできてしまう

これを今勉強中のpythonでやってみようと思って始めたことでしたが、実はpython3 では

print(2**64)

としただけで、正しい結果が出てきます。

FORTRANやBASICの時代は、プログラミング言語の学習は変数の型と使用するバイト数を知るところから始まりました。pythonでは変数宣言をしませんから意識したことはありませんでした。

で、もっと驚いたことに、bwbasicでも

print 2^64

で計算できてしまいます。

十進BASICでも10進1000桁モードにすればできます。十進BASICは演算に十進法を用いて我々の誤差に対する感覚に違和感のない計算ができることを売りにしたいましたが、昔から桁数の多い計算も簡単にできるようになっていました。

ちなみに、二進で計算するから不正確になるという人がいますが、ちょっと短絡すぎるでしょう。ただ0.1や0.2など十進で小数点以下ひと桁で書ける数は0.5以外二進では循環小数となるのは事実です。

yabasicでは 1.84467e+19 となってしまいます。

pythonやbwBASIC、十進BASICでどのような計算方法で出しているのかは、もう少し調べたいと考えています。

javaでは

javaのプリミティブ整数型はint4バイト、long8バイトです。符号付きですから、intで-2147483648から2147483647まで。longで-9223372036854775808から9223372036854775807まで扱えます。longは8バイトということは64ビット。負数があるので2の63乗-1が正の整数の最大値です。2の64乗は計算できません。

javaにはjava.math.BigIntegerというクラスがあります。任意精度の整数とありますが、コンストラクタには

BigInteger(byte[] val)
BigInteger の 2 の補数 2 進表現を含むバイト配列を BigInteger に変換します。

というのがありますから、byteの配列を使って表現しているのでしょう。

十進で計算するjava.math.BigDecimalというクラスもあります。

結論

初期の目論見は失敗。プログラミング言語は思ったよりも進んでいました。

ソートまで自分で書かなければならなかった時代からやっていますので、知らないでいることも多いのです。

ただ、整数の扱える範囲をすぐに調べられないのはちょっと困ります。

付録:BASICで2の累乗の限界を調べる

プログラム

for i=28 to 32
    print i;
    print " : ";
    print 2^i
next i
print "31-1:";
print 2^31-1
print "-----------------------------"
print "   63:";
print 2^63
print "   64:";
print 2^64
print "  100:";
print 2^100
print " 1000:";
print 2^1000
for i=1021 to 1025
    print i;
    print " : "
    print 2^i
next i

yabasicでは

整数が4バイト符号付き整数

それ以上は、浮動小数点数 IEEE754 64ビット の様です。

$ yabasic pwpw2.bas 
28 : 268435456
29 : 536870912
30 : 1073741824
31 : 2.14748e+09
32 : 4.29497e+09
31-1:2147483647
-----------------------------
   63:9.22337e+18
   64:1.84467e+19
  100:1.26765e+30
 1000:1.07151e+301
1021 : 2.24712e+307
1022 : 4.49423e+307
1023 : 8.98847e+307
1024 : inf
1025 : inf

bwbasicでは

整数のまま21023まで計算し続けます。

$ bwbasic pwpw2.bas 
Bywater BASIC Interpreter/Shell, version 2.20 patch level 2
Copyright (c) 1993, Ted A. Campbell
Copyright (c) 1995-1997, Jon B. Volkoff
 
 28 :  268435456
 29 :  536870912
 30 :  1073741824
 31 :  2147483648
 32 :  4294967296
31-1: 2147483647
-----------------------------
   63: 9223372036854775808
   64: 18446744073709551616
  100: 1267650600228229401496703205376
 1000: 107150860718626732094842504906000181056140481170553360744375038837035105
1124936122493198378815695858127594672917553146825187145285692314043598457757469
8574803934567774824230985421074605062371141877954182153046474983581941267398767
559165543946077062914571196477686542167660429831652624386837205668069376
 1021 :  2247116418577894884661631488486280917022471223677883215917876014471658
4475687620391588559665300942002640014234983924169707348721101802077811605928829
9342655472209866781081856595377774501557617649316353690106257211047688352928078
6018423913881760340464541881383557328727999340574230996453810441954120302801715
2
 1022 :  4494232837155789769323262976972561834044942447355766431835752028943316
8951375240783177119330601884005280028469967848339414697442203604155623211857659
8685310944419733562163713190755549003115235298632707380212514422095376705856157
2036847827763520680929083762767114657455998681148461992907620883908240605603430
4
 1023 :  8988465674311579538646525953945123668089884894711532863671504057886633
7902750481566354238661203768010560056939935696678829394884407208311246423715319
7370621888839467124327426381511098006230470597265414760425028844190753411712314
4073695655527041361858167525534229314911997362296923985815241767816481211206860
8
 1024 :  inf
 1025 :  inf

2^1023までは整数で計算します。python3での計算と同じようです。

bwbasicの不具合??

ただし、2^1023と2^1023-1は同じになります。普通にintではないようです。

print "2^1023:"
print 2^1023
print "2^1023-1:"
print 2^1023-1

こうなります

2^1023:
 898846567431157953864652595394512366808988489471153286367150405788663379027504
8156635423866120376801056005693993569667882939488440720831124642371531973706218
8883946712432742638151109800623047059726541476042502884419075341171231440736956
555270413618581675255342293149119973622969239858152417678164812112068608
2^1023-1:
 898846567431157953864652595394512366808988489471153286367150405788663379027504
8156635423866120376801056005693993569667882939488440720831124642371531973706218
8883946712432742638151109800623047059726541476042502884419075341171231440736956
555270413618581675255342293149119973622969239858152417678164812112068608

累乗指数を減らしてテストすると、-1が計算結果に影響するのは254あたりからでした。

x=2^54
for i=0 to 9
    print i;
    print " : ";
    print x-i
next i

この結果は、

 0 :  18014398509481984
 1 :  18014398509481984
 2 :  18014398509481982
 3 :  18014398509481980
 4 :  18014398509481980
 5 :  18014398509481980
 6 :  18014398509481978
 7 :  18014398509481976
 8 :  18014398509481976
 9 :  18014398509481976

丸めが影響しているようにも見えます。

python3では

bwbasicが怪しい結果なので、pythonで検証です。

print(2**1023)
print(2**1023-1)

実行結果は

 898846567431157953864652595394512366808988489471153286367150405788663379027504
8156635423866120376801056005693993569667882939488440720831124642371531973706218
8883946712432742638151109800623047059726541476042502884419075341171231440736956
555270413618581675255342293149119973622969239858152417678164812112068608
 898846567431157953864652595394512366808988489471153286367150405788663379027504
8156635423866120376801056005693993569667882939488440720831124642371531973706218
8883946712432742638151109800623047059726541476042502884419075341171231440736956
555270413618581675255342293149119973622969239858152417678164812112068607