An inverse Fibonacci algorithm?

by

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 2×2 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.

More Related Contents:

  1. Finding out nth fibonacci number for very large ‘n’
  2. Test if a number is fibonacci
  3. Custom Weighted Scale [closed]
  4. Sum a number with divisors to get another number
  5. How to create the most compact mapping n → isprime(n) up to a limit N?
  6. Mapping two integers to one, in a unique and deterministic way
  7. Least common multiple for 3 or more numbers
  8. Is it possible to express “t” variable from Cubic Bezier Curve equation?
  9. Choosing n numbers with fixed sum
  10. Fast way to calculate n! mod m where m is prime?
  11. Need help in mod 1000000007 questions
  12. Check if one integer is an integer power of another
  13. Modulus power of big numbers
  14. Puzzle: Find largest rectangle (maximal rectangle problem)
  15. How can I calculate the age of a person in year, month, days?
  16. 3D Least Squares Plane
  17. Shortest distance between points algorithm
  18. Why is the complexity of computing the Fibonacci series 2^n and not n^2?
  19. The Sieve of Atkin
  20. finding a^b^c^… mod m
  21. Determining if two line segments intersect? [duplicate]
  22. How do you find a point at a given perpendicular distance from a line?
  23. How to find distance from the latitude and longitude of two locations?
  24. Reverse complex 2D lookup table
  25. How do I determine whether my calculation of pi is accurate?
  26. JavaScript: Calculate the nth root of a number
  27. Calculating phi(k) for 1
  28. How to generate a power set of a given set?
  29. determine if a point sits inside an arbitrary shape?
  30. Location of highest density on a sphere

Leave a Comment