4 ms·

There is, actually, an even simpler formula. While the explicit formula for the n-th Fibbonacci number is indeed F_n = 1/sqrt5 * [ ((1+sqrt5)/2)^n - ((1-sqrt5)

by osoba 12y ago

There is, actually, an even simpler formula. While the explicit formula for the n-th Fibbonacci number is indeed F_n = 1/sqrt5 * [ ((1+sqrt5)/2)^n - ((1-sqrt5)/2)^n ] or F_n = (1.6180^n + 0.6180^n)/2.2361 you can notice that the -((1-sqrt5)/2)^n = 0.6180^n term tends to 0, and is in fact smaller than 0.5 even for n=2, which gives us an even simpler formula for F_n = ceil(1.6180^n/2.2361). This would also take care of the limited precission of the float point numbers.

pavpanchekha 12y ago
What do you mean, take care of the limited precision? The formula you gave is only correct for n = [1, 3, 5, 7, 9, 10, 11, 12, 13, 14, 15, 16, 17] The reason the explicit floating point formula doesn't get used is because you need as many bits of floating point as you expect to get bits of answer. Which means that you get the wrong answer pretty quickly. If the goal was to calculate an approximation to the fibonacci numbers, sure, but then you don't need the (ceil) call.
- osoba 12y ago
  Oh yeah you're right Although, wouldn't variable overflow be the case for any algorithm, since already the 100th or so Fibonacci number takes more space than 2^64 And if you were to use the full float precision of sqr5 (and not just 4 digits like I did), you would run into 64bit float overflow way before that algorithm stops being accurate
  - TheLoneWolfling 12y ago
    Everything else is talking about bigints. If you were dealing with fixed-length integers, just use a lookup table. Also, you're wrong regarding floating-point. On my machine, fib(101) is off from your approximation by ~2 million (!). Well before hitting the limits of a 64-bit float. It starts erroring at n=71, and only gets worse from there. Worse, the relative delta grows as n increases.
    - osoba 12y ago
      Hmm ok Thanks for actually testing it
      - TheLoneWolfling 12y ago
        Python is wonderful for that sort of thing.

by osoba 12y ago

pavpanchekha 12y ago

What do you mean, take care of the limited precision? The formula you gave is only correct for n = [1, 3, 5, 7, 9, 10, 11, 12, 13, 14, 15, 16, 17] The reason the explicit floating point formula doesn't get used is because you need as many bits of floating point as you expect to get bits of answer. Which means that you get the wrong answer pretty quickly. If the goal was to calculate an approximation to the fibonacci numbers, sure, but then you don't need the (ceil) call.

osoba 12y ago
Oh yeah you're right Although, wouldn't variable overflow be the case for any algorithm, since already the 100th or so Fibonacci number takes more space than 2^64 And if you were to use the full float precision of sqr5 (and not just 4 digits like I did), you would run into 64bit float overflow way before that algorithm stops being accurate
- TheLoneWolfling 12y ago
  Everything else is talking about bigints. If you were dealing with fixed-length integers, just use a lookup table. Also, you're wrong regarding floating-point. On my machine, fib(101) is off from your approximation by ~2 million (!). Well before hitting the limits of a 64-bit float. It starts erroring at n=71, and only gets worse from there. Worse, the relative delta grows as n increases.
  - osoba 12y ago
    Hmm ok Thanks for actually testing it
    - TheLoneWolfling 12y ago
      Python is wonderful for that sort of thing.