1

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?

Rohit Pandey
  • 2,443
  • 7
  • 31
  • 54
  • 2
    As with many similar questions you can get an excellent feel for some aspects of the problem by simply trying it. Try computing the answer using the closed-form phi/psi formulas for larger and larger values and see how it goes. – President James K. Polk Oct 22 '21 at 23:30
  • 1
    Sure. But I don't doubt the guy in the third link I shared who says he runs into overflow problems around n=80. I'm sure I'll hit the same. Just, what is it fundamentally about the matrix exponentiation approach that manages to avoid this (and keep results accurate for longer)? Especially since it seems to be doing the same thing in a cruder way. – Rohit Pandey Oct 22 '21 at 23:47
  • Matrix exponentiation uses pure integer operations and of course cannot avoid "overflow" issues. You must use a big integer package when doing the matrix operations (unless you use a language like python whose ints automatically grow as needed). – President James K. Polk Oct 22 '21 at 23:50
  • I see, so the distinction is that all entries of the matrix are integers and so you're always working with integers instead of the irrational phi and psi? – Rohit Pandey Oct 22 '21 at 23:51
  • 2
    It's not really about matrices vs scalars, it's about what 'scalar' refers to. Phi is an irrational number; one formula requires raising a floating point number precisely to very large powers while *keeping rounding error very low*. The 'matrix' formula just uses integer multiplications. – kcsquared Oct 22 '21 at 23:51
  • 3
    The closed-form solution requires operations on irrational numbers (which IEEE floating point cannot represent exactly), exponentiation to high powers (which will quickly exceed the maximum value representable as IEEE floating point), and subtraction of two very large numbers (resulting in loss of significance). All of these factors contribute to numeric instability. There is an entire field of engineering known as [numerical analysis](https://en.wikipedia.org/wiki/Numerical_analysis) devoted to understanding these factors and working to avoid them. – Raymond Chen Oct 23 '21 at 00:01
  • 2
    @RaymondChen The "closed form" solution subtracts a very small number from a very large one, so numerical instability isn't an issue. (Actually, for all but very small *n*, the second term is smaller than 1/2 so you can ignore it and just round the first term to the nearest integer.) The problem is only imperfect precision of floating point numbers. – kaya3 Oct 25 '21 at 03:13
  • @kaya3 You're right, I missed that phi < 1. – Raymond Chen Oct 25 '21 at 13:08

2 Answers2

2

Note that "In practice" here is referring to competitive programming (in reality, you basically never want to compute massive fibonacci numbers). So, the first reason is that the normal way of calculating fibonacci numbers is way faster to type without making any errors, and less code. Plus, it will be faster than the fancy method for small numbers.

When it comes to big numbers, Fast Matrix multiplication is O(log(n)) if you don't care about precision. However, in competitive programming we almost always care about precision and want the correct answer. To do that, we would need to increase the precision of our numbers. And the bigger n gets, the more precision is required. I don't know the exact formula, but I would imagine that because of the increased precision required, the matrix multiplication which requires only O(log n) multiplications will require something like O(log n) bits of precision so the time complexity will actually end up being somewhat bad (O(log^3 n) maybe?). Not to mention, even harder to code and very slow because you are multiplying arbitrary-precision numbers.

Alex Li
  • 246
  • 4
  • 11
  • 1
    Why you never want to find large fib nums irl? – JobHunter69 Jun 09 '22 at 03:09
  • 1
    @JobHunter69 Knowing the exact value of large Fibonacci numbers are not useful in solving any real world problem that I know of. Maybe one day there will be a reason, but I doubt it. It's an abstract concept which is more useful for theory than practice. – Alex Li Jun 09 '22 at 04:11
  • 1
    A few things pop up when I google fib applications. So the idea that large fib nums are not needed doesn't seem true to me, or at least is an unsubstantiated claim – JobHunter69 Jun 09 '22 at 05:25
  • I don't see anything which actually requires precise large fibonacci numbers, could you give a concrete counter example? It would be quite interesting if it is real – Alex Li Jun 09 '22 at 17:47
  • 1
    if you need large fib nums what makes you think it doesn't need to be precise? – JobHunter69 Jun 10 '22 at 05:07
  • 1
    I mean I want you to prove me wrong; all you need is to provide a counterexample. But to answer the question, generally you don't care about the 1000th digit of precision on things in practice. It's like how engineers don't need to know much more than 3.14159. – Alex Li Jun 10 '22 at 19:10
2

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.

kaya3
  • 47,440
  • 4
  • 68
  • 97