Hacker News Reader

Comment by gammarator | Hacker News Reader

(Fibonacci numbers have a closed form analytic solution that can be computed in constant time: https://www.evanmiller.org/mathematical-hacker.html)

View on HN

Yep, this is called Binet formula, and actually all linear recurrence sequences have one.

What defines 'linear' here?

The solutions form a vector space

I regret that does not elucidate. Does linear mean additions only? Or non-exponentiation, or something else?

Linear means that f(n) is a linear function of f(n-1)...f(n-k). This means that you can calculate f(n)...f(n-k+1) in terms of a matrix multiply on f(n-1)...f(n-k) (most of the matrix is empty, with ones just off the diagonal). Taking powers of the matrix lets you take more steps. Diagonalizing the matrix lets you take powers in constant time. (You may have to worry about precision. Often rounding to nearest integer after that fixes things though). If you are worried about that, or just don't have floating point, the "fastexp" algorithm turns it into logarithmic time.

If A and B are a solution, then A+B is also a solution. For a constant r, if C is a solution, r*C is also solution.

That's it. The nice closed form of exponentials as solutions is just for linear difference equations with constant coefficients. In that case, you can always find a solution by trying λ^n and seeing what that forces λ to be -- it'll be a root of some polynomial.

Does this work in practice for large values of n? You will be limited by numerical error in phi.

The Fibonacci series grows so fast that for "large" values of N you'll need a arbitrary size integer implementation anyway, so at that point you might as well go for a (non-IEEE) arbitrary size float type and get all the significant digits you need.

You’ll still need to compute the digits of Phi though, and then exponentiate that. My intuition is that using ints is still faster.

It does not! It fails very early (I tested it once in Python, and it failed on something like F(70) or something) and should not ever be used for practical calculation of Fibonacci numbers.

For small values, the iterative version works just fine. For larger values, there are other methods: one obvious one is using the matrix form of the Fibonacci numbers, which just requires you to take an exponent of a 2x2 matrix (which you can do quickly because of exponentiation by squaring).

Calculating powers isn't constant, as far as I know.

Reply on news.ycombinator.com