Shubham - 3 months ago 22
C++ Question

How to find index of a given Fibonacci number

I tried to use the following formula

$n = \bigg\lfloor \log_\varphi \left(F\cdot\sqrt{5} + \frac{1}{2} \right)\bigg\rfloor$

to find the index of a fibonacci number($F(0) = 1, F(1) = 1,...$) 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.

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
``````

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