# Finding index of a Fibonacci number: any mathematical solution possible?

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.

• $\lceil 1+\log_{\phi}(x)\rceil$ should be a good starting point. – J. M. is a poor mathematician Dec 10 '10 at 12:03
• To expand a bit on J.M.'s comment, the idea is to (1) find an $n$ such that $F_n \leq x \leq F_{n+k}$ for some small $k$ - i.e. you want your first guess to be good - (2) use the matrix multiplication method to compute $F_n$ and $F_{n+1}$ and (3) if you haven't hit $x$ yet, then just keep computing $F_{n+2},F_{n+3},\ldots, F_{n+k}$ until you hit $x$ – kahen Dec 10 '10 at 12:16
• In any event... – J. M. is a poor mathematician Dec 10 '10 at 12:23
• @J.M. As for the downvote on this question: I downvoted it, because I expect the asker to do some rudimentary research before posting a question. A question about Fibonacci numbers that can be answered within 2 minutes by looking up the term "Fibonacci number" on Wikipedia is, in my mind, a bad question. I have flagged your comment by the way. – Alex B. Dec 10 '10 at 13:31
• math.stackexchange.com/questions/9999/… – Qiaochu Yuan Dec 10 '10 at 17:03

$$n = \bigg\lfloor \log_\varphi \left(F\cdot\sqrt{5} + \frac{1}{2} \right)\bigg\rfloor.$$
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.