Essays/Fibonacci Index
< Essays
Jump to navigation
Jump to search
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
See also
Contributed by Roger Hui.