# 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

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