Essays/Fibonacci Index

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

$\;\;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$

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 ${\phi ^ n} / \sqrt 5$ where $\phi$ is the golden ratio, whence n is the logarithm to base $\phi$ of $F_n \sqrt 5$ .

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

Essays/Fibonacci Index

See also