4
$\begingroup$

The problem:

               Given a Fibonacci number,find its index. 

I am aware of the standard solution 'generate-hash-find'. I am just curious if there is some inverse system of matrix exponentiation or some other mathematical method that gives the solution.

  • 0
    http://math.stackexchange.com/questions/9999/checking-if-a-number-is-a-fibonacci-or-not2010-12-10

2 Answers 2

11

From wikipedia: "Similarly, if we already know that the number F is a Fibonacci number, we can determine its index within the sequence by

$n = \bigg\lfloor \log_\varphi \left(F\cdot\sqrt{5} + \frac{1}{2} \right)\bigg\rfloor.$

2

Using this other my answer
Using integers only, I would use Binary Search. Certainly you can compute $F_n$ only with integers, the simplest way is matrix exponentiation. Using Binary Search you can find numbers ``near'' your number $x$ and you will find $x = F_n$ (and $n$). I suppose this method is generic for anything monotone you can compute fast. To initiliaze the binary search, just keep doubling $ F_{2n} $

Binary search allows you to search for a number x in a sorted "array" F[] (in the programming sense). Use this method to search for your number. When you need F[n] just compute $F_n$. This will work because the sequence is strictly increasing except for the initial 1,1.