Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
879 views
in Technique[技术] by (71.8m points)

math - An inverse Fibonacci algorithm?

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.

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Answer

0 votes
by (71.8m points)

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.


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...