12
$\begingroup$

The $n$th Fibonacci number can be computed in linear time using the following recurrence:

def fib(n):
    i, j = 1, 1
    for k in {1...n-1}:
        i, j = j, i+j
    return i

The $n$th Fibonacci number can also be computed as $\left[\varphi^n / \sqrt{5}\right]$. However, this has problems with rounding issues for even relatively small $n$. There are probably ways around this but I'd rather not do that.

Is there an efficient (logarithmic in the value $n$ or better) algorithm to compute the $n$th Fibonacci number that does not rely on floating point arithmetic? Assume that integer operations ($+$, $-$, $\times$, $/$) can be performed in constant time.

$\endgroup$
14
$\begingroup$

You can use matrix powering and the identity $$ \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n = \begin{bmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{bmatrix}. $$ In your model of computation this is an $O(\log n)$ algorithm if you use repeated squaring to implement the powering.

$\endgroup$
  • 1
    $\begingroup$ It's a classic. $\endgroup$ – dfeuer Jan 25 '15 at 4:52
  • 8
    $\begingroup$ You can also use this identity to derive the recurrences $F_{2n-1} = F_n^2 + F_{n-1}^2$ and $F_{2n} = F_n^2 + 2F_{n-1}F_n$. $\endgroup$ – augurar Jan 25 '15 at 5:09
4
$\begingroup$

You can read this mathematical article: A fast algorithm for computing large Fibonacci numbers (Daisuke Takahashi): PDF .

More simple, I implemented several Fibonacci's algorithms in C++ (without and with GMP) and Python. Complete sources on Bitbucket. From the main page you can also follow links to:

  • The C++ HTML online documentation.
  • A little mathematical document: Fibonacci numbers - several relations to implement good algorithms

The most useful formulas are:

  • $F_{2n} = F^2_{n + 1} - F^2_{n - 1} = 2 F_n F_{n - 1} + F^2_n$
  • $F_{2n + 1} = F^2_{n + 1} + F^2_n$

Be careful on algorithm. You must not calculate the same value several times. A simple recursive algorithm (in Python):

def fibonacci_pair(n):
    """Return (F_{n-1}, F_n)"""
    if n != 0:
        f_k_1, f_k = fibonacci_pair(n//2)  # F_{k-1},F_k with k = n/2

        return ((f_k**2 + f_k_1**2,
                 ((f_k*f_k_1)*2) + f_k**2) if n & 1 == 0  # even
                else (((f_k*f_k_1)*2) + f_k**2,
                      (f_k + f_k_1)**2 + f_k**2))
    else:
        return (1, 0)

Its complexity is logarithmic (if the basic operations are in constant time): $O(\log n)$.

$\endgroup$
  • 2
    $\begingroup$ Welcome to Computer Science. Please could you add more information to your answer? At the moment, it's nothing more than two links, so your answer will become meaningless if those links die or the servers they're on are unavailable. Links to more information are fine but the links here are the only information. Also, please note that the question is very definitely about algorithms, not about C++ implementations. Implementations tend to obscure the algorithms behind language-specific details. $\endgroup$ – David Richerby May 19 '15 at 20:23
  • $\begingroup$ David, the first link is a link to a mathematical article. The title A fast algorithm [...] answers to the question "Is there an efficient (logarithmic in the value n or better) algorithm [...]?" The second link is a link to my various implementations, in C++ and Python, and a little mathematical document with several formulas. $\endgroup$ – Olivier Pirson May 19 '15 at 21:07
  • 2
    $\begingroup$ No, the title of the article, which is what your answer contains, answers nothing. The text of the article, which your answer contains almost none of, sounds like it probably does answer the question. But Stack Exchange is a question and answer site, not a link farm. (And, no, I'm not suggesting that you copy-paste the article into your answer. But a summary is needed.) $\endgroup$ – David Richerby May 19 '15 at 21:11
  • $\begingroup$ If you want a summary, write it! $\endgroup$ – Olivier Pirson May 19 '15 at 21:14
0
$\begingroup$

Basic theory and code for computing linear recurrences with constant coefficients in $O(\log_2 n)$ is available from http://www.jjj.de/.

Check the free book Matters Computational and the pari/gp code.

$\endgroup$
  • 5
    $\begingroup$ Better to summarize the ideas instead of just posting links. $\endgroup$ – augurar Jan 26 '15 at 4:29

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.