2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Well, you don't always need to multiply $n$ times, for example, $x^8 = ((x^2)^2)^2$, so instead of $7$ we have $4$. $\endgroup$ – copper.hat Mar 10 '14 at 19:45
  • $\begingroup$ If you want only an approximation, as far as the floating point type takes you, you compute the approximation in time independent of $n$. If you want an exact result, exponentiation by repeated squaring gets you to the result in $O(\log n)$ steps. (Since $F_n$ has $\Theta(n)$ bits, the overall computation is $O(n)$ or worse.) $\endgroup$ – Daniel Fischer Mar 10 '14 at 19:47
  • $\begingroup$ Computers don't need to multiply $a$ to itself $b$ times to calculate $a^b$. $\endgroup$ – blue Mar 10 '14 at 19:48
  • $\begingroup$ chaos.org.uk/~eddy/craft/Fibonacci.html $\endgroup$ – Carsten S Mar 10 '14 at 19:48
  • $\begingroup$ I realize you're only asking about computational efficiency, but I thought it might be useful to point out that one can get useful properties of the Fibonacci numbers from the Binet formula. For example, the $n$'th Fibonacci number is $\frac{1}{\sqrt{5}}\left(\frac{1 + \sqrt{5}}{2}\right)^{n}\left[1 - \left(\frac{1 - \sqrt{5}}{1 + \sqrt{5}}\right)^{n}\right],$ which for large $n$ is approximately $\frac{1}{\sqrt{5}}\left(\frac{1 + \sqrt{5}}{2}\right)^{n},$ which in turn is approximately $(0.447)(1.618)^{n}.$ $\endgroup$ – Dave L. Renfro Mar 10 '14 at 20:22
6
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ For biggish $n$, the later steps are kind of expensive. $\endgroup$ – André Nicolas Mar 10 '14 at 20:06
  • $\begingroup$ Yes, but any algorithm is going to have to deal with very large numbers which will end up being expensive at every step. Even the individual additions in the traditional algorithm will take $O(n)$ time by the end when computing $F_n$. For very large values of $n$ you would want to use some improved multiplication algorithm ( e.g., FFT), but since the numbers you deal with double in length each step, the vast majority of the pain is not until the very very end. $\endgroup$ – Aaron Mar 10 '14 at 20:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.