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

---

See also

• Fibonacci Sequence
  
• Fibonacci Sums

---

Contributed by Roger Hui.