連分数を使って黄金比を求めた


2012年 11月 26日

『関数プログラミング』4.5 畳み込み(fold)関数 手習い中
RenbunsuunoFushigi.jpg

ここで、有理数(分数)の計算を色々試してみよう。

*Main Data.Ratio> 1/1+1/2+1/3+1/4+1/5
2.2833333333333332

ここで、/ のうち、1つだけを % にすると、どうなるだろうか。

*Main Data.Ratio> 1/1+1/2+1%3+1/4+1/5
137 % 60

ということで、どうやら % が一つでも入っていると、全体が有理数として計算されるようだ。

前回の黄金比の計算で出てきた無名関数 (\x y -> x+1/y) の除算のところを % に変えてみよう。

*Main Data.Ratio> foldr (\x y -> x+1%y) 1 [1,1,1]

Occurs check: cannot construct the infinite type: a0 = Ratio a0
In the second argument of `(%)', namely `y'
In the second argument of `(+)', namely `(1 % y)'
In the expression: x + (1 % y)

というエラーメッセージが出てきてしまった。
the infinite type ということで、型にうるさいHaskellの型決めの怒りを買ってしまった。

ということで、無名関数は (\x y -> x+1/y) のままにして何とかならないか考えよう。
最初の実験から、どこかに有理数が含まれて入れば、全体を有理数にしてくれるらしい。
だから、foldrの計算で使われる最初の数を有理数にしてしまえば、全体が有理数になるのではないだろうか。

Haskells.jpgのサムネール画像

最初の数は、無名関数の次の引数の1である。
1のままではダメだから、有理数に型変換する関数 toRational を使ってみよう。

*Main Data.Ratio> foldr (\ x y -> x + 1 / y) (toRational 1) [1, 1, 1]
5 % 3

ちゃんと計算できた。(確認は読者に任せた!)

しかし、toRational 1 は長いので、1%1で置き換えてしまおう。

*Main Data.Ratio> foldr (\ x y -> x + 1 / y) (1%1) [1, 1, 1]
5 % 3

[1,1,1] とかで必要個数並べるのは大変なので、takeを使って個数を指定しよう。

*Main Data.Ratio> foldr (\ x y -> x + 1 / y) (1%1) (take 3 [1,1..])
5 % 3
*Main Data.Ratio> foldr (\ x y -> x + 1 / y) (1%1) (take 10 [1,1..])
144 % 89
*Main Data.Ratio> foldr (\ x y -> x + 1 / y) (1%1) (take 20 [1,1..])
17711 % 10946

しかし、俗人には分数のままではよく分からないので、浮動小数点に直してみよう。

*Main Data.Ratio> fromRational (foldr (\ x y -> x + 1 / y) (1%1) (take 10 [1,1..]))
1.6179775280898876
*Main Data.Ratio> fromRational (foldr (\ x y -> x + 1 / y) (1%1) (take 20 [1,1..]))
1.618033985017358
*Main Data.Ratio> fromRational (foldr (\ x y -> x + 1 / y) (1%1) (take 30 [1,1..]))
1.6180339887496482
*Main Data.Ratio> fromRational (foldr (\ x y -> x + 1 / y) (1%1) (take 40 [1,1..]))
1.618033988749895
*Main Data.Ratio> fromRational (foldr (\ x y -> x + 1 / y) (1%1) (take 50 [1,1..]))
1.618033988749895

40項まで取れば、この有効桁数までの精度が得られている気がする。
直接黄金比を計算してみよう。

*Main Data.Ratio> (1+(sqrt 5))/2
1.618033988749895

ということで、黄金比を連分数を使って計算することができた。
しかし、数を正確に計算するとなると、やはりアレを計算しなくては(つづく)

※なお、ここでの計算は、数学の本に書いてある途中までの近似とは違う値になっている。 それは、再帰のラムダ式が楽になるようにしているためであるが、近似が進めば無視できるようになる。 詳しいことは省略。