2017年4月26日水曜日

したたり算法

この話題の前回のブログでは, 円周率を表すmixed radixの式を示し, 右の項から 正規化しながら十進の小数点以下の数字を求める話を書いた.

通常の計算ならそうするのだが, したたり算法では左から計算したい. それも 可能であって, 次のように計算が進行する.

下のtex出力の図で, 左上の式を見てほしい. 左端のvとuにすべての情報を 記憶させながら, 左側(外側)からかっこをはずす. 話の発端となった円周率の式 は, 左側の2行目のものである. 2+で始まっていたが, 外から1を掛けて標準形に してある.


最初の仕事は左かっこの外にあるvを, かっこ内の2つの項に掛けることだ. 今は 1だから左の3行目のように, vが消えた以外はなにも変らない.

次は先頭に来たuに相当する2を, 1/3の右のかっこの中にいれることである. それには この2に1/3の逆数, 3/1を掛ける. そうして出来た2×(3/1)+2をまとめて8 にする. 下から3行目のように, 1/3(8+ ... が出来て, 標準形であるが, かっこが 外側から1組減った.

また同じように1/3をかっこ内の8と2/5に掛ける. そうして出来た8/3を 2/15の逆数を掛けてかっこ内に入れる. すると右側の上の行のようになる. 後は 一々書かぬが, 同様に進むのである.

これを手でやるのは面倒なので, 以後は計算機にやってもらう. かっこ内は左からu とvと, 標準形の式にあったiの値である. 最後の項が5に相当するところ(4行目)までが 上の出力に見られる.

(8 1/3 2)
(22 2/15 3)
(160/3 2/35 4)
(122 8/315 5)
(1352/5 8/693 6)
(8818/15 16/3003 7)
(8832/7 16/6435 8)
(18782/7 128/109395 9)
(356984/63 128/230945 10)
...
これを更に進めると
(864779799556983658/40970475 67108864/450883717216034179 31)
のようになり, このuとvを掛けると3.1415926533011596になる. 小数点以下9 桁目まで合っている.

これが3.1415...なのは計算機が十進法にしてくれたからで, したたり算法では 自分で計算しなければならない. その過程が次の出力である.


最初の行は, 先程の長々とした分数のuとv, それとiから計算した残りの項 (31/63(2+...))である. u*vの整数部分を計算してみると
(floor->exact
 (*  67108864/450883717216034179
   864779799556983658/40970475)) => 3
と3になるので, 次の2行にわたる式のように, 先頭に3を括りだす. そしてかっこの中から3にvの逆数を掛けたものを引いて辻褄を合せる. かっこ 内を計算したものが最後の行である.

この最後の行のvとuと十進にしたいので10を掛けると, 整数部分に1が得られる. 3.14...の1のことだ.
(floor->exact
(* 10 67108864/450883717216034179
  2615629766097082765349437/2749482034790400)) => 1
ここでもTexで書くのは止め, 計算機にやってもらう. 次々のuとvと出力される 数である.
(2615629766097082765349437/2749482034790400
   67108864/450883717216034179 3)
(1536675519372845944725869/5498964069580800
   671088640/450883717216034179 1)
(58841914244318110336667/5498964069580800
   6710886400/450883717216034179 4)
(437921482322098289538739/109979281391616000
   67108864000/450883717216034179 1)
(136926162079932661882877/219958562783232000
   671088640000/450883717216034179 5)
(196056880918257839392441/10997928139161600000
   6710886400000/450883717216034179 9)
(60341900506756319941901/13747410173952000000
   67108864000000/450883717216034179 2)
(196925612577461046092237/549896406958080000000
   671088640000000/450883717216034179 6)
(48785647745580267174347/2199585627832320000000
   6710886400000000/450883717216034179 5)
(222531979586221607133547/109979281391616000000000
   67108864000000000/450883717216034179 3)
(8569388169424319751667/1099792813916160000000000
   671088640000000000/450883717216034179 3)
今日の計算はまずかっこを取り払い, つまりかっこの次の2を消し, この処理をi=31に なるまで進め, 今度は十進の各桁と順次に括りだすものであった. 大体は 左から右へ処理できたが, 本来のしたたり算法では, 出力できる状態に なると同時に出力するわけで, 次回はその話をしたい.

0 件のコメント: