labunix's blog

labunixのラボUnix

Sceme(gauche)でフィボナッチ数列をF(70)までΦの精度で丸めた分数を使って公式で解いてみる。

■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)まではΦの精度で丸めた分数を使って計算出来た。