Efficient algorithm to compute the $n$th Fibonacci number

Question

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.

Answer 1

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.

Answer 2

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

Answer 3

We should first note that Fibonacci numbers $(F_n)$ grow very fast with $n$ and cannot be represented in 64-bits for $n$ larger than 93. So a program for computing them for such $n$ needs to use additional mechanisms to operate on these large numbers. Now, considering only the count of (large-number) operations, the algorithm to sequentially compute them will require linear number of operations.

We can benefit from the below identity about Fibonacci numbers:

$ F_{2m} = 2F_mF_{m+1}−{F_m}^2$

$ F_{2m+1}={F_m}^2+ {F_{m+1}}^2 $

So, if we know $F_m$ and $F_{m+1}$, we can directly compute $F_{2m}$ and $F_{2m+1}$.

Consider the binary representation of $n$. Observe that starting with $x=1$, we can make $x=n$ by iteratively doubling and possibly adding 1 to $x$. This can be done by iterating over the bits of $n$, and checking if it is 0 or 1.

The idea is that, we can maintain $F_x$ in sync with $x$. In each such iteration, as we double $x$ and possibly add 1 to $x$, we can also compute the new value of $F_x$ using the earlier value of $F_x$ and $F_{x+1}$, with above equations.

Since the number of iterations will be logarithmic in $n$, the total (large-number) operations are also logarithmic in $n$.

For further details, please refer section "Improved Algorithm" of this article (written by me).

Answer 4

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.

Answer 5

If you have to perform q queries asking fib(n) for multiple n values, you can use dynamic programming to solve it in O(n + q).

int dp[100];

int fib(int n){
    if(dp[n] != 0) return dp[n];
    dp[n] = fib(n - 1) + fib(n - 2);
    return dp[n];
}

The idea is to store already processed values so if the recurrence call that value, if returns in O(1).