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.

  • 5
    $\begingroup$ As a suggestion, the Wikipedia article on Fibonacci numbers has lots of methods. $\endgroup$
    – Pseudonym
    Commented Jan 24, 2015 at 23:52
  • $\begingroup$ cf. stackoverflow.com/questions/14661633/… and links therein and around. $\endgroup$
    – Will Ness
    Commented May 19, 2015 at 23:26
  • $\begingroup$ “Rounding issues” So how much precision do you need? $\endgroup$
    – gnasher729
    Commented Jul 21, 2020 at 16:01

5 Answers 5


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.

  • 3
    $\begingroup$ It's a classic. $\endgroup$
    – dfeuer
    Commented Jan 25, 2015 at 4:52
  • 12
    $\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
    Commented Jan 25, 2015 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))
        return (1, 0)

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

  • 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$ Commented May 19, 2015 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$ Commented May 19, 2015 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$ Commented May 19, 2015 at 21:11
  • $\begingroup$ If you want a summary, write it! $\endgroup$ Commented May 19, 2015 at 21:14

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


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.

  • 7
    $\begingroup$ Better to summarize the ideas instead of just posting links. $\endgroup$
    – augurar
    Commented Jan 26, 2015 at 4:29

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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