ハノイの塔の話をしたときに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のプリミティブ整数型は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というクラスもあります。
初期の目論見は失敗。プログラミング言語は思ったよりも進んでいました。
ソートまで自分で書かなければならなかった時代からやっていますので、知らないでいることも多いのです。
ただ、整数の扱える範囲をすぐに調べられないのはちょっと困ります。
プログラム
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
整数が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
整数のまま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での計算と同じようです。
ただし、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
丸めが影響しているようにも見えます。
bwbasicが怪しい結果なので、pythonで検証です。
print(2**1023) print(2**1023-1)
実行結果は
898846567431157953864652595394512366808988489471153286367150405788663379027504 8156635423866120376801056005693993569667882939488440720831124642371531973706218 8883946712432742638151109800623047059726541476042502884419075341171231440736956 555270413618581675255342293149119973622969239858152417678164812112068608 898846567431157953864652595394512366808988489471153286367150405788663379027504 8156635423866120376801056005693993569667882939488440720831124642371531973706218 8883946712432742638151109800623047059726541476042502884419075341171231440736956 555270413618581675255342293149119973622969239858152417678164812112068607