数学ガールを読むぞぉ 7 - フィボナッチ数列の一般項(2)
フィボナッチ数列の一般項の続きです。
フィボナッチの一般項は、
なんですが、(1 + √5)^nの計算が重い。結局n回展開しなければならないため、計算回数は反復の時と変わらなかった。桁落ちしてしまうので、浮動小数点は使いたくないし・・・。
むむぅ・・・と考え。
あ。
あらかじめ展開してやればいいじゃないか！！
ということで、√5をxと置きます。
だいぶスッキリです。
上の部分だけ計算すると、
0 : 1 - 1 = 0 1 : (1 + x) - (1 - x) = 2x 2 : (1 + 2x + x^2) - (1 - 2x + x^2) = 4x 3 : (1 + 3x + 3x^2 + x^3) - (1 - 3x + 3x^2 - x^3) = 6x + 2x^3 4 : ... = 8x + 8x^3 5 : = 10x + 20x^3 + 2x^5 6 : = 12x + 40x^3 + 12x^5
何かパターンがありそうなんだけど見えない。
うぅん。式にどんな性質があるんだろう。とじっと式を眺めてみると。
1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 ^ ^ ^
を2倍したの偶数列。
パスカルの三角形！！
とりあえず計算してみる。6の時、
(12x + 40x^3 + 12x^5) / 2^6x (12 + 40x^2 + 12x^4) / 2^6 (12 + 40 * 5 + 12 * 25) / 2^6 512 / 64 8
フィボナッチが計算出来ました。
二項定理を使えば出てきそうです。
つまり、フィボナッチ数列の一般項は、
とも書けるようだ。
誰も信用してくれないだろうけど、フィボナッチが出るんだよ！！
√5が消えたので、浮動小数点を使わなくて良くなった。
さて、Schemeに直す。
(define (combi n r) (if (= r 0) 1 (* (/ (+ (- n r) 1) r) (combi n (- r 1))))) (define (fib n) (/ (* 2 (apply + (list-tabulate (quotient n 2) (lambda (m) (* (expt 5 m) (combi n (+ 1 (* 2 m)))))))) (expt 2 n))) (fib 10) ; 55
重い・・・階乗の計算をしてるので、二項定理の和が非常に遅い。しかしまだまだ改善できる余地のある形となった。
パスカルの三角形からフィボナッチが出てくるなんて・・・不思議すぎる。
求め方が違うけど、wikipediaにもパスカルの三角形との関係が書かれていた。
パスカルの三角形をずらして、足すと。
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
-------------------------------------
1 1 2 3 5 8 13 ...ちっ。僕の発見じゃなかったか（笑
よく考えてみると二項定理はn回の計算が必要なので、高速化したところで限界が見える。√5を外に出すまで展開しないという条件を付けると、速度的には望めない状況のようだ。
ま、自分の力で二項定理まで辿りつけたので、今回は良しとしとこう。
あ、ちと旅行に出かけます。
