math - An inverse Fibonacci algorithm?

Question

There are dozens of ways of computing F(n) for an arbitrary n, many of which have great runtime and memory usage.

However, suppose I wanted to ask the opposite question:

Given F(n) for n > 2, what is n?

(The n > 2 restriction is in there since F(1) = F(2) = 1 and there's no unambiguous inverse).

What would be the most efficient way of solving this problem? It's easy to do this in linear time by enumerating the Fibonacci numbers and stopping when you hit the target number, but is there some way of doing this any faster than that?

EDIT: currently, the best solution posted here runs in O(log n) time using O(log n) memory, assuming that mathematical operations run in O(1) and that a machine word can hold any number in O(1) space. I'm curious if it's possible to drop the memory requirements, since you can compute Fibonacci numbers using O(1) space.

Answer 1

Since OP has asked about matrix solution not involving any floating point computations, here it is. We can achieve O(logn) complexity this way, assuming numeric operations have O(1) complexity.

Let's take 2x2 matrix A having following structure

1 1
1 0

Now consider vector (8, 5), storing two consecutive fibonacci numbers. If you multiply it by this matrix, you'll get (8*1 + 5*1, 8*1 + 5*0) = (13, 8) - the next fibonacci number.
If we generalize, A^n * (1, 0) = (f(n), f(n - 1)).

The actual algorithm takes two steps.

1. Calculate A^2, A^4, A^8, etc. until we pass desired number.
2. Do a binary search by n, using calculated powers of A.

On a side note, any sequence of the form f(n) = k1*f(n-1) + k2*f(n-2) + k3*f(n-3) + .. + kt*f(n-t) can be presented like this.