連分数を使って黄金比を求めた
2012年 11月 26日
『関数プログラミング』4.5 畳み込み(fold)関数 手習い中
ここで、有理数（分数）の計算を色々試してみよう。
*Main Data.Ratio> 1/1+1/2+1/3+1/4+1/5
2.2833333333333332ここで、/ のうち、１つだけを % にすると、どうなるだろうか。
*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の計算で使われる最初の数を有理数にしてしまえば、全体が有理数になるのではないだろうか。
最初の数は、無名関数の次の引数の１である。
１のままではダメだから、有理数に型変換する関数 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.61803398874989540項まで取れば、この有効桁数までの精度が得られている気がする。
直接黄金比を計算してみよう。
*Main Data.Ratio> (1+(sqrt 5))/2
1.618033988749895ということで、黄金比を連分数を使って計算することができた。
しかし、数を正確に計算するとなると、やはりアレを計算しなくては（つづく）
※なお、ここでの計算は、数学の本に書いてある途中までの近似とは違う値になっている。 それは、再帰のラムダ式が楽になるようにしているためであるが、近似が進めば無視できるようになる。 詳しいことは省略。
＃人気の記事
＃タグ
