4 ms·
Is Binet's formula really that practical a way to calculate the Fibonacci numbers (except asymptotically)? The problem is, you have this nice clean expression,
by LegionMammal978 2y ago
Is Binet's formula really that practical a way to calculate the Fibonacci numbers (except asymptotically)? The problem is, you have this nice clean expression, but you'd still have to implement a bunch of fancy arbitrary-precision arithmetic to approximate the golden ratio through Newton's method. In other words, the formula gives much more information about the structure of the Fibonacci numbers than their actual values.
For evaluating the Fibonacci numbers (as with any other integer linear recurrence), I'd generally prefer the matrix-exponentiation-by-squaring approach, or one of the simplified formulas based on it. Those don't need anything more complicated than bigint multiplication. [And from there, taking the ratio between two values gives you a quick way to approximate the golden ratio!]
- fn-mote 2y agoOnce you have postulated BigInt as available, the mathematician is going to make a rational approximation for phi using the continued fraction expansion that they know by heart (because of its “simplicity”).
- LegionMammal978 2y agoCalculating φ from its continued-fraction expansion is equivalent to just iterating the Fibonacci sequence normally, since its convergents are precisely the ratios between the Fibonacci numbers. At that point, it's totally redundant to use Binet's formula on the approximation, since you have the values already! If you want to beat the O(n^2) runtime of the trivial iteration, you pretty much have to use Newton's method for φ, exponentiation by squaring on the matrix form, or another method with faster-than-linear convergence.