Search code examples
sequencedynamic-programmingfibonacci

Why is closed form for fibonacci sequence not used in practice?


There is a closed form for the Fibonacci sequence that can be obtained via generating functions. It is:

f_n = 1/sqrt(5) (phi^n-\psi^n)

For what the terms mean, see the link above or here.

However, it is discussed here that this closed form isn't really used in practice because it starts producing the wrong answers when n becomes around a hundred and larger.

But in the answer here, it seems one of the methods employed is fast matrix exponentiation which can be used to get the nth Fibonacci number very efficiently in O(log(n)) time.

But then, the closed form expression involves a bunch of terms that are raised to the nth power. So, you could calculate all those terms with fast exponentiation and get the result efficiently that way. Why would fast exponentiation on a matrix be better than doing it on scalars that show up in the closed-form expression? And besides, looking for how to do fast exponentiation of a matrix efficiently, the accepted answer here suggests we convert to the diagonal form and do it on scalars anyway.

The question then is - if fast exponentiation of a matrix is good for calculating the nth Fibonacci number in O(log(n)) time, why isn't the closed form a good way to do it when it involves fast exponentiation on scalars?


Solution

  • In the "closed form" formula for computing Fibonacci numbers, you need to raise irrational numbers to the power n, which means you have to accept using only approximations (typically, double-precision floating-point arithmetic) and therefore inaccurate results for large numbers.

    On the contrary, in the "matrix exponentiation" formula for computing Fibonacci numbers, the matrix you are raising to the power n is an integer matrix, so you can do integer calculations with no loss of precision using a "big int" library to do arithmetic with arbitrarily large integers (or if you use a language like Python, "big ints" are the default).

    So the difference is that you can't do exact arithmetic with irrational numbers but you can with integers.