3 ms·
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 p
by 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 agoThe 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 agoand 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 agoThe "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]