Shubham - 1 year ago 88

C++ Question

I tried to use the following formula

to find the index of a fibonacci number() 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 Source

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.