2017年4月13日木曜日

したたり算法

ことし(2017年)3月にオックスフォード大学のGibbons君が研究所のセミナーで話をしてくれることになった. 彼の話は面白いものもあるが, 難解なものも多いので, 少し昔の研究だが, Spigot Algorithmで円周率を計算する話をして貰った.

Spigot Algorithmとは, 円周率πや自然対数の底 e のような長い小数を, 頭の方から次々と出力する計算法である. これはちょうど水道の栓から水が一滴一滴したたり落ちる様子に似ているので, 水栓という意味のSpigotを使い, Spigot Algorithmという. 水栓算法というのが直訳だが, 殺風景なので, ここでは「したたり算法」といおう.

日本で電子計算機が使えるようになった1960年頃, あまり速くもなく, 記憶装置も少なかった当時の機械で, eの値を計算することが各センター間で流行した. 東大高橋研のパラメトロン計算機PC-1の記憶装置(18ビット512語)と計算速度(加算400マイクロ秒)では, eは小数点以下1000桁くらいがほどほど計算できる限界であり, eの多項式展開の460の階乗分の1くらいまで使えば1000桁の精度が得られると分ってそういう計算をしていた. まず十進1000桁に相当する値を二進で計算し, その後二進十進変換して2.7182...を出力した.

このように通常は何桁計算するかを初めに決めるのである. これに対してしたたり算法では普通には得ようとする桁を前もっては決めない. eの計算では, 長い時間かけて計算が進行し, 暫くは出力が現れないが, したたり算法ではいきなり出力が始まって見ていて楽しい. しかしそうなにもかも上手くいく筈はなく, 段々と疲れてきたが如く出力が遅くなる傾向がある.

前口上はこのくらいにして, Gibbons流の算法を何回かに分け, 少しずつ説明したい.

eの計算には e=1+1/1!+1/2!+1/3!+... を使うのが常識である. 解析概論でもこれを使ってeの値を計算してみせる(1953年版 p.75).

一方円周率には公式が山のようにあって, どれを使うか迷うが, その昔ENIACで2035桁まで計算した時はMachinの公式

π/4=4 arctan 1/5-arctan 1/239
arctan x=∑n=0(-1)nx2n+1/ (2n+1)

を使ったといわれている. (城,牧之内「計算機械」p.105.)

さて式が徐々に複雑になるので, 以後はTexで書いたものを見ていただく. Gibbonsの計算の式は下のTex出力の一番上のものである. これはeの式のように簡単には得られない. Wolframのページを見ると, その下のarctan xの式が見付かる. この式のxに1を代入すると, arctan 1 は45度つまりπ/4になる. xが1なら, x2n+1は1になり, (1+x2)n+1 は 2n+1になる.

πにするにはこの式を4倍にするわけで, それには22nを22n+2にする. 一方分母には2n+1があるので, 結局2の羃は2n+1になる. それが途中のhttp:...の行の下の式だ. このnに0, 1, 2, 3を代入して書いてみるとその下のようになり, 各項の共通の因子を前に出すと, その下の括弧の式になる.

ここでn=4の項を書くと, 一番下のようになる. 左にある分数は階乗の展開で, これをみると, 前に現れる共通因子 1/3, 2/5, 3/7は赤線で消したように消える. また青線のように分母の8, 6, 4, 2は分子の4, 3, 2, 1と右の5個の2のうちの4個とキャンセルし, 結局右辺にある4/9×2が残り, 一番上の式になった.

また次のTexの出力を見てほしい. 一番上は円周率π=3.1415...の十進法を強調して描いたものである. 1桁下る度の1/10の重みで足されることを示す.

その次は前の式で, 1桁下る度のその桁の値は常に2であることを示す. ただし重みは10ではなく, 3, 5/2, 7/3, ...と変っていく. 十進法をdecimal radixというが, 各桁で重みが変るのはmixed radixという.

mixed radixというと意外かも知れないが, 1日は24時間, 1時間は60分, 1分は60秒, 1秒は1000ミリ秒とか, 1里は36町, 1町は60間, 1間は6尺, 1尺は10寸とかなど身近になくはない.

πの場合はmixed radixではあるが, i番目の重みが(2i+1)/iと決っているのが有難く, その各桁の値が2に固定されているのが味噌である.

従ってもうπの値は分ったようなものだが, やはり十進でないと気がすまないから, mixed radixからdecimal radixへと基数変換(radix conversion)する必要がある.

上の出力で, Mixed radix to decimal conversionとある下が基数変換である. 最初はπの展開式を第5項までとったものだ. それでまずこれを10倍する. つまり 各桁の値を10倍する. それが次の行である.

十進の場合の各桁が0から9までの値しか取れないように, このmixed radixでも, 第i桁は2iまでしかとることができない. 従って下の桁から, 2iを越えていれば, 正規化する必要がある. (20)の下の方に1,9と見えるのは, 20を分母の11で除したときの商が1, 剰余が9であることを示す. つまりこの桁は正規化すると, 1が繰上がって9になるわけだ.

繰上がった1は, 分子の5を掛けて, 5として繰上がり, その桁の20と足して25になる. 次はその25を分母の9で除し, 商2, 剰余7になる. 商2に分子の4を掛け, 8を20に足し, 次の桁では28を正規化する.

これを繰り返すと, 第1桁では32を正規化し, 商10に分子1を掛けた10が繰上がり, 20と足して30になる. つまり円周率の10倍の整数部は30ということが分った.

各桁の値は剰余で置き換え, それを10倍すると, 300から始まる行のようになる.

これは最初の取った項数が少いし, 10倍と正規化も1回しかしていないので, 様子が分り難いが, 100項くらい取って, この操作を何回も繰り返したのが, 最後の数列である. この先頭がπを何回も10倍したもので, 3141592653までは正しいπの値が得られている.

今回の説明はこのくらいで.

0 件のコメント: