Shubham Shubham - 2 months ago 12
C++ Question

How to find index of a given Fibonacci number

I tried to use the following formula

formula

to find the index of a fibonacci number(text) in a programming question and all the smaller test cases passed but some cases in which F was close to 10^18 failed. I did some dry-run and found out that if F = 99194853094755497 (82nd Fibonacci number) the value of n according to the above formula is 81. I coded this in Python and C++ which can be found here and here respectively. I want to know whether the formula works for every value of F or has some limitations?

Note: After doing some more tests, I found out that the code is giving correct answers till 52nd fibonacci number.

Update: The question has t test cases that's why I used a for loop. The given number F might not necessarily be a Fibonacci number. For ex- If F = 6, then it lies between two fibonacci numbers 5 and 8. Now the index of '5' in the fibonacci sequence is 4 so the answer is 4.

Answer

The formula works just fine:

import math
n = 99194853094755497
print math.log(n * math.sqrt(5) + 0.5) / math.log(1.61803398875) - 1

Output:

82.0

A remark on your code:

  • Using int(...) for rounding off to an integer might cause trouble if the floating point result is very close to 82.0. Numerical issues might cause it to be slightly larger, even though mathematically it would be smaller.