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

• As a suggestion, the Wikipedia article on Fibonacci numbers has lots of methods. Jan 24 '15 at 23:52
• cf. stackoverflow.com/questions/14661633/… and links therein and around. May 19 '15 at 23:26
• “Rounding issues” So how much precision do you need? Jul 21 '20 at 16:01

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

• 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. May 19 '15 at 21:07
• 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.) May 19 '15 at 21:11
• If you want a summary, write it! May 19 '15 at 21:14

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.

• Better to summarize the ideas instead of just posting links. Jan 26 '15 at 4:29

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.

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