Essays/Fibonacci Index

From J Wiki
Jump to: navigation, 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

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



Contributed by Roger Hui.