# Efficient algorithm to compute the $n$th Fibonacci number

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.

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.

• It's a classic. – dfeuer Jan 25 '15 at 4:52
• 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$. – augurar Jan 25 '15 at 5:09

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

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