5 ms·

Great writeup! I only wish the author had benchmarked the approximate algorithm with phi and floating points too, because it's often 'good enough' >>> fib

• omaranto 12y ago
  factorial(n) is an odd choice of name for the nth Fibonacci number. You should at the very least provide a doc string! :)
  • arh68 12y ago
    Thank you. The 'code' is bad enough, would never pass review ;)
• ddlatham 12y ago
  Agreed, a benchmark would be cool. From what I've read before it ends up taking longer than the integer methods anyway because you still need to keep log n bits of precision in the floating point values around to get the correct answer. Perhaps if you had a use case for approximate values of very large fibonacci numbers it would be useful? I'd love to hear that use case.
• jules 12y ago
  That only works for the first 20 or so Fibonacci numbers due to limited floating point precision, so then you could also use a 20 entry lookup table.
• nayuki 12y ago
  It would be incomparable because the 4 algorithms described on the page produce exact integer results, whereas a floating-point algorithm will not have enough precision to represent larger numbers.
  • xyzzyz 12y ago
    The Binet formula operates on noninteger numbers, but it does not need to be implemented using floating points. One can operate in a field Q(sqrt(5)), and represent elements using two rational numbers, obtaining exact results. See example implementation: https://github.com/xyzzyz/FibBinet https://github.com/xyzzyz/FibBinet
    • jordigh 12y ago
      and the same thing in Python: http://ideone.com/9dHQV9 http://ideone.com/9dHQV9 Edit: implemented binary squaring: http://ideone.com/NWQe38 http://ideone.com/NWQe38
    • Chinjut 12y ago
      The "fast doubling" approach IS the natural calculation in Q(sqrt(5)). That is, let φ^2 = φ + 1 (so φ = (1 + sqrt(5))/2). Then (a + bφ)^2 = (a^2 + b^2) + (2ab + b^2)φ. Furthermore, (a + bφ) * φ = b + (a + b)φ. Finally, we have that φ^n = F(n - 1) + F(n)φ. Thus, we can extract the n-th Fibonacci number from the n-th power of φ, which we can compute in the form a + bφ by "repeated squaring" using the above rules, which is precisely what the "repeated doubling" approach of the linked-to page is effectively doing. [Note that, by representing a + bφ in terms of its individual a and b components, we can just directly extract the components when we need them, instead of having to extract the coefficient of φ in x as (x - conj(x))/(φ - conj(φ)) [where conj(a + bφ) = a + b(1 - φ); note that this conjugation operator distributes across multiplication], which is what Binet's formula does to extract the coefficient of φ in φ^n]
• 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
• leephillips 12y ago
  I go into this a liitle bit at http://lee-phillips.org/lispmath/ http://lee-phillips.org/lispmath/