No advantage to the closed form for Fibonacci numbers?

482 Views Asked by At

The closed forms for the Fibonacci sequence, such as:

$$F_n=\frac{\varphi^n-\widehat\varphi^n}{\sqrt5}=\frac{\varphi^n}{\sqrt5}-\frac{\widehat\varphi^n}{\sqrt5}\;,$$

the Binet formula, do not seem to offer a calculational advantage. In fact, multiplying an irrational n-times would seem to be even more computationally intensive than simply recursively adding n-times, the normal way the sequence is generated.

Is there any shortcut to generating a Fibonacci number which is easier than adding the standard way?

1

There are 1 best solutions below

2
On

One shortcut is to use the matrix formula for calculating Fibonacci numbers combined with squaring to speed up exponentiation. This way, you only deal with integer arithmetic and you need approximately $\log n$ steps to compute $F_n$.