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に なるまで進め, 今度は十進の各桁と順次に括りだすものであった. 大体は 左から右へ処理できたが, 本来のしたたり算法では, 出力できる状態に なると同時に出力するわけで, 次回はその話をしたい.

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までは正しいπの値が得られている.

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

2017年3月30日木曜日

地図のミウラ折り

ミウラ折りの地図が疊まれていく様子は一見なんとも不思議である. 今回はそれを検討した結果を書いてみたい.

下の図は1個の区画が折れ曲るところを描いたもので, 立体座標x,y,zを図のように設定する. 地図の1区画はABCDの形で, ABが前のブログの図の横方向の折り線, ADが左右に少しずつ屈折する縦方向の折り線である. 中の図で見るように∠BADをγとする. (γは鋭角である.)

上は区画が水平面(xy面)内にある場合で, 辺ABはx軸に接している. 辺ADとx軸の角をβとする. 今はβ=γである. これから辺ABをAを中心として時計回りにxz面内に回転し(ADで山折りにし), 辺ABとx軸の角をαということにすると, 今はα=0である.

辺ABを, xz面内で回転している途中が中の図である. αは50°になったところだ. 縦の折り線は山折り同士, 谷折り同士高さが揃っているから, 辺ADはxy面内を回転する. γは一定だから, βは徐々の縮小していき, 図のような形になる.

さらにBを下へ回していくと, Dはますますx軸へ接近し, αが区画の角度γに等しくなった時に, 辺ADはx軸に重なる(βが0になる). それが下の図である.

この区画以外の最初に水平面にあったどの区画も, この図のようにxz面内に収まってしまう.

αが増えるにつれ, βの減る様子は, γが一定だから, α, β, γの関係から分るわけだ.

原点に立つ2個のベクトル(a0,a1,a2)と(b0,b1,b2)のなす角θは

cosθ=(a0×b0+a1×b1+ a2×b2)/(√(a02+a12+a22) √(b02+b12+b22))

で得られる. 上の図でいえば, ABとADの作る面積を考えればよい.

AB=l, AD=sとすると,

a0=l cosα, a1=0 ,a2=l sinα, b0=0, b1= l cosβ ,b2=s sinα

だから

cos γ=(l cos α s cos β)/(l s)= cos α cos β

β = cos-1 (cos γ/cos α)

γが84°の時のαとβの関係は次のようだ.

以上は1区画であったが, 隣接の区画を追加し, 3×3の区画での動きを描いたのが次の図である. 区画の境界点に0から15まで番号をつけた. また山折り谷折りの色もつけた. 地図の周囲は黒で描いてあるが, 縦の境界は地図の中と同様に曲げてある.

上はα=0で, 縦線が屈折しているから平面と見るのは難しいが, 全体は平面である.

中と下はαが53°と83.7°(γになる直前)に対応するものである.

さらに隠面消去したのが次の図である. 境界点の番号は残してある.

私はこれで疊まれ方が理解できたが, どうであろうか. この3×3を疊む動画がhttp://www.iijlab.net/~ew/miurafig.htmlに置いてある.

2017年3月17日金曜日

クイズ

前回のこの話題のブログで, ADの長さは得られたが, 一辺が7の正三角形に外接する円に, 3辺が3, 5, 7の三角形が内接するかが気になっていた.

∠BDEが60°なので, ∠EABが120°ならいいわけだ.

余弦定理によると

cos ∠EAB=(32+52−72)/(2×3×5)=−1/2.

やはり120°であった. すっきりした.

2017年3月16日木曜日

クイズ

電車の中の広告に, 中学受験の問題らしいものがあった.

この図で, BDEは円に内接する一辺7の正三角形. その円周上にAB=CD=5, EA=BC=3となるようにAとCをとる. この時, ADの長さは何か.

中学受験をする子供にこれが解けるのかよく分らぬが, 面白そうなのでやってみた.

この図のようにBからCDと平行にBFを引き, AD上の点をFとする.

すると, ∠DEB=60° 弦BDに立つ円周角だから∠DAB=∠DEB=60°. 四辺形ABCDは等脚台形だから, ∠ADC=60°. CDとBFは平行だから, ∠AFB=60°. 従ってABFは正三角形. AF=5; BCDFは平行四辺形だからFD=3. AD=8.

小学6年生にはかなり難しいのではないだろうか. Cは何のためにあるかがヒントになるが.

2017年3月11日土曜日

地図のミウラ折り

ミウラ折りをした時の出来上がりの大きさは次のように計算出来る.

図の下寄りの横長の長方形が, 元の紙の最上段である. この下に続く横長の部分は, 山折り谷折りの繰り返しで, この裏にぴったりと隠れてしまい, この部分と一緒に折られていくから, 出来上がりの大きさには関係しない.

前回のこのブログの最初の図で, 95, 85, 92,...などと数値で長さが記入してあるのが, この図ではa, b, c,...と文字にしてある. 上下の縁や折り目には, 左から0, 1, ..., 7と番号をつける.

ダッシュが付いている番号は, 折る前の位置を示す.

左端から見ていくと, 最初の折り目1-1までの長さが上下で違うから, この折り目は傾く. その傾きをθとする.

θ=tan-1(a-b)/c

である. するとこの折り目と下の縁との角は, 左が∠R+θ, 右が∠R-θである.

次の折り目, 2'-2'は, 折り目1-1で折り返すと, 2-2の位置へ来る. この時, 下の012の角は, 2θになる. 下の2と下の1との横方向, 縦方向の差を図のようにe, fとすると, 1,2の長さをdとして,

e=d cos 2θ
f=d sin 2θ

である. 従って, 下の2の位置は, 下の0を原点とすると,

(b-e, f )

これに横方向のdを足すと3の位置が得られ, 横方向からeを引き, 縦方向にfを足すと4が得られる. 以後この作業を繰り返し, 最後は横方向にaを足す. 上の縁の座標も同様にして得られる.

まとめると

θ=tan-1(a-b)/c,
e=d cos 2θ
f=d sin 2θ

上の座標
0 0, c
1 a, c
2 a-e, c+f
3 a-e+d, c+f
4 a-2e+d, c+2f
5 a-2e+2d, c+2f
6 a-3e+2d, c+3f
7 a-3e+2d+b, c+3f
下の座標
0 0, 0
1 b, 0
2 b-e, f
3 b-e+d, f
4 b-2e+d, 2f
5 b-2e+2d, 2f
6 b-3e+2d, 3f
7 b-3e+2d+a, 3f

前回の地図の値をいれて計算すると

(define a 95) (define b 85) (define c 92)
(define d 80) (define theta (atan (/ (- a b) c)))
(define e (* d (cos (* 2 theta))))
(define f (* d (sin (* 2 theta))))
(+ a (* -3 e) (* 2 d) b) => 105.60485754320413
(+ c (* 3 f)) => 143.56468939747782
ところで近所の体育館で下のような大宮アルディージャの選手名鑑みたいなものを貰った. やや! これはミウラ折りではないか? 山折り谷折りの関係もそっくりである.

しかしこれは上の図のθが0になっている. 従って上の図の横から見た時, 2,4,6が同一点になり, ミウラ折りとは似てはいるが, ミウラ折りではない.

前回の後, もう1枚の地形図をミウラ折りにした.

今回, 山折りのところは, 裏面にも折り目を記入して, 裏から谷折りにしたが, やはり手間は増えた. もう少し能率のよい方法はないだろうか.

2017年3月9日木曜日

フィボナッチ数の話題

前回, この話題では Fn+1Fn-1-Fn2 =(-1)n を証明したが, 実はもっと簡単の単であった.

n=1の時は

1·0 -1·1=-1
つまり(-1)1 だ.

n+1の時の式は

Fn+2Fn - Fn+12

このFn+2とFn+1の一つを定義により前の2項の和に書き換える.

(Fn+1+Fn)Fn - Fn+1(Fn+Fn-1) = Fn2 - Fn+1Fn-1 = -(-1)n = (-1)n+1