■Sceme(gauche)でフィボナッチ数列をF(70)までΦの精度で丸めた分数を使って公式で解いてみる。 $ gosh -V Gauche scheme shell, version 0.9.5 [utf-8,pthreads], x86_64-pc-linux-gnu ■小数を分数に直す方法について $ seq 0 9 | awk '{print "echo \047(inexact->exact 1."$1")\047"}' | \ sh | gosh -i | sed -e 's/gosh> //g' | \ awk 'BEGIN{n=0}{print "1."n"="$0;n++}' 1.0=1 1.1=11/10 1.2=6/5 1.3=13/10 1.4=7/5 1.5=3/2 1.6=8/5 1.7=17/10 1.8=9/5 1.9=19/10 ■黄金比Φ(ファイ)について、無理数を精度で丸めた近似値として小数、分数でそれぞれ求めてみる。 phi=(1 + √5)/2 $ echo '(/ (+ 1 (sqrt 5)) 2)' | gosh -i | sed -e 's/gosh> //g' 1.618033988749895 $ echo '(inexact->exact (/ (+ 1 (sqrt 5)) 2))' | gosh -i | sed -e 's/gosh> //g' 165580141/102334155 ■ビネの公式の証明では、 フィボナッチ数列が三項間漸化式であることを利用して, 特性方程式を用いて一般項を求める方法があって、 漸化式 an=(an − 1) + (an − 2) を,a1 = a2 = 1 のもとで解く際に、 Φをαとして x^2 = x + 1 の解を、 α=(1 + √5)/2 、β=(1 - √5)/2 と置き、 an について解くと、 an = (α^n - β^n) / (α - β) だった。 $ cat fib.scm (define (fib n) (let ((alpha (/ (+ 1 (sqrt 5)) 2))) (let ((beta (/ (- 1 (sqrt 5)) 2))) (inexact->exact (round (/ (- (expt alpha n) (expt beta n)) (- alpha beta)) )) )) ) ■また、α+β=1、αβ=-1の性質を利用するので、 β=1-αとして、α=Φをそのまま代入する方式で書いてみると、 $ cat fib2.scm (define (fib n) (let ((phi (/ (+ 1 (sqrt 5)) 2))) (inexact->exact (round (/ (- (expt phi n) (expt (- 1 phi) n)) (sqrt 5)) )) )) ■70までは正しい。精度の限界はこの辺りなので。 $ echo "(fib 70)" | gosh -i -l ./fib.scm | sed -e 's/gosh> //g' 190392490709135 $ echo "(fib 70)" | gosh -i -l ./fib2.scm | sed -e 's/gosh> //g' 190392490709135 ■四捨五入での最初の誤りはfib.scmでは71、fib2.scmでも71。 $ seq 1 100 | awk '{print "echo -n \042F("$1") = \042;echo \042(fib "$1")\042 | \ gosh -i -l ./fib.scm | sed -e \047s/gosh> //g\047"}' | sh > fib3.txt $ sdiff -s fib[13].txt | awk 'NR==1' F(71) = 308061521170129 | F(71) = 308061521170130 $ seq 1 100 | awk '{print "echo -n \042F("$1") = \042;echo \042(fib "$1")\042 | \ gosh -i -l ./fib2.scm | sed -e \047s/gosh> //g\047"}' | sh > fib3.txt $ sdiff -s fib[13].txt | awk 'NR==1' F(71) = 308061521170129 | F(71) = 308061521170130 ■切り捨てでの最初の誤りはfib.scmでは72、fib2.scmでも72。 $ sed -i -e 's/round/truncate/' fib.scm $ seq 1 100 | awk '{print "echo -n \042F("$1") = \042;echo \042(fib "$1")\042 | \ gosh -i -l ./fib.scm | sed -e \047s/gosh> //g\047"}' | sh > fib4.txt $ sdiff -s fib[14].txt | awk 'NR==1' F(72) = 498454011879264 | F(72) = 498454011879265 $ sed -i -e 's/round/truncate/' fib2.scm $ seq 1 100 | awk '{print "echo -n \042F("$1") = \042;echo \042(fib "$1")\042 | \ gosh -i -l ./fib2.scm | sed -e \047s/gosh> //g\047"}' | sh > fib4.txt $ sdiff -s fib[14].txt | awk 'NR==1' F(72) = 498454011879264 | F(72) = 498454011879265 ■floorも切り捨てなので同じく最初の誤りはいずれも72。 $ sed -i -e 's/truncate/floor/' fib.scm $ seq 1 100 | awk '{print "echo -n \042F("$1") = \042;echo \042(fib "$1")\042 | \ gosh -i -l ./fib.scm | sed -e \047s/gosh> //g\047"}' | sh > fib4.txt $ sdiff -s fib[14].txt | awk 'NR==1' F(72) = 498454011879264 | F(72) = 498454011879265 $ sed -i -e 's/truncate/floor/' fib2.scm $ seq 1 100 | awk '{print "echo -n \042F("$1") = \042;echo \042(fib "$1")\042 | \ gosh -i -l ./fib2.scm | sed -e \047s/gosh> //g\047"}' | sh > fib4.txt $ sdiff -s fib[14].txt | awk 'NR==1' F(72) = 498454011879264 | F(72) = 498454011879265 ■四捨五入、切り捨ての違いはさておき、 F(70)まではΦの精度で丸めた分数を使って計算出来た。