Differences between revisions 10 and 11
 ⇤ ← Revision 10 as of 2007-09-12 06:50:09 → Size: 1631 Editor: RogerHui Comment: ← Revision 11 as of 2008-12-08 10:45:30 → ⇥ Size: 1614 Editor: anonymous Comment: converted to 1.6 markup Deletions are marked like this. Additions are marked like this. Line 16: Line 16: fib n computes the n-th [:../Fibonacci Sequence:Fibonacci number]. fib n computes the n-th [[../Fibonacci Sequence|Fibonacci number]]. Line 20: Line 20: [http://wikipedia.org/wiki/Fibonacci_number#Relation_to_the_golden_section Binet's formula] [[http://wikipedia.org/wiki/Fibonacci_number#Relation_to_the_golden_section|Binet's formula]] Line 23: Line 23: [[latex($$\;\;F_n = {1\over\sqrt 5} \left( {{1+\sqrt 5}\over 2}\right)^n - \ {1\over\sqrt 5} \left( {{1-\sqrt 5}\over 2}\right)^n$$)]] <> Line 28: Line 28: The first term is [[latex(${\phi ^ n} / \sqrt 5$)]] where [[latex($\phi$)]]is the [http://mathworld.wolfram.com/GoldenRatio.html golden ratio], whence n is the logarithm tobase [[latex($\phi$)]] of [[latex($F_n \sqrt 5$)]] . The first term is <> where <>is the [[MathWorld:GoldenRatio|golden ratio]], whence n is the logarithm tobase <> of <> . Line 52: Line 52: [[BR]] <
> Line 55: Line 55: * [:../Fibonacci Sequence:Fibonacci Sequence] [[BR]] * [:../Fibonacci Sums:Fibonacci Sums] * [[../Fibonacci Sequence|Fibonacci Sequence]] <
> * [[../Fibonacci Sums|Fibonacci Sums]] Line 58: Line 58: [[BR]] <
>

fib=: 3 : 0 " 0
mp=. +/ .*
{.{: mp/ mp~^:(I.|.#:y) 2 2\$0 1 1 1x
)

fib i.10
0 1 1 2 3 5 8 13 21 34
fib 256
141693817714056513234709965875411919657707794958199867

fib n computes the n-th Fibonacci number. Given non-negative integer y , find the index n such that  (fib n)<:y  and  y<fib n+1 .

Binet's formula states that

The second term is less than 0.5 in magnitude for all n and declines exponentially with n ; therefore, for purposes of computing the Fibonacci index we need only consider the first term. The first term is where is the golden ratio, whence n is the logarithm to base of .

phi=: -:1+%:5
fi =: 3 : 'n - y<fib n=. 0>.(1=y)-~>.(phi^.%:5)+phi^.y'

y=: 10 20 40 80 160 5 13
] n=. fi y
6 7 9 10 12 5 7
(fib n),y,:fib 1+n
8 13 34 55 144 5 13
10 20 40 80 160 5 13
13 21 55 89 233 8 21

fi fib 2000 20000
2000 20000
fi 1+fib 2000 20000
2000 20000
fi _1+fib 2000 20000
1999 19999