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.

$\endgroup$
  • 4
    $\begingroup$ $\lceil 1+\log_{\phi}(x)\rceil$ should be a good starting point. $\endgroup$ – J. M. is a poor mathematician Dec 10 '10 at 12:03
  • $\begingroup$ 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$ $\endgroup$ – kahen Dec 10 '10 at 12:16
  • $\begingroup$ In any event... $\endgroup$ – J. M. is a poor mathematician Dec 10 '10 at 12:23
  • $\begingroup$ @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. $\endgroup$ – Alex B. Dec 10 '10 at 13:31
  • $\begingroup$ math.stackexchange.com/questions/9999/… $\endgroup$ – Qiaochu Yuan Dec 10 '10 at 17:03
11
$\begingroup$

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.$$

$\endgroup$
  • $\begingroup$ Do you have a link? There are two different indices that both have the value of 1, so there can't be any formula that doesn't deal with that special case. $\endgroup$ – Acccumulation Aug 7 at 18:05
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.