How efficient is this Python Code for the fibonacci sequence?

Question

I wrote this a few days ago and it seems to be working fine, but it is slow. It took 25 seconds to generate the 1 millionth number in the fibonacci sequence. Is there a way to make this more efficient?

def main():
    num1 = 0
    num2 = 1
    var = 0
    num = int(raw_input("What fibonacci number do you want to know? "))
    while 1:
        num3 = num1
        num1 = num1 + num2
        num2 = num3
        var+=1
        if var>=num:
            print num3
            return main()
        else:
            None

main()

Note that I am a beginner in python, so I won't understand advanced concepts

I wouldn't use recursion to repeat the process, but the while loop to implement this simple algorithm for finding Fibonacci numbers is fine. — chepner, Sep 09 '12 at 13:08

Martijn Pieters · Answer 1 · 2012-09-09T15:14:57.757

I've found that using Lucas numbers gives me results fastests:

def powLF(n):
    if n == 1:     return (1, 1)
    L, F = powLF(n//2)
    L, F = (L**2 + 5*F**2) >> 1, L*F
    if n & 1:
        return ((L + 5*F)>>1, (L + F) >>1)
    else:
        return (L, F)

def fib(n):
    if n & 1:
        return powLF(n)[1]
    else:
        L, F = powLF(n // 2)
        return L * F

Like matrix exponention, it has O(NlogN) complexity, but it's constant cost is lower, thus beating it 'on points':

>>> timeit.timeit('fib(1000)', 'from __main__ import fibM as fib', number=10000)
0.40711593627929688
>>> timeit.timeit('fib(1000)', 'from __main__ import fibL as fib', number=10000)
0.20211100578308105

Yes, that's twice as fast.

I can't take credit for the above implementation, nor of the matrix exponention algorithm I compared it with; both were listed on literateprograms.org.

To calculate the 1,000,000th Fibonacci number takes:

>>> timeit.timeit('fib(1000000)', 'from __main__ import fib', number=100)/100
0.09112384080886841

just under a 10th of a second.

Since Fibonacci numbers grow exponentionally, there is no way to compute the nth Fibonacci number in O(log n). Simply storing the result in memory would already be O(n). — Sven Marnach, Sep 09 '12 at 14:41
@MartijnPieters can you exaplain the use of `>> 1` , I am bad with bit shifting. :) — Ashwini Chaudhary, Sep 09 '12 at 19:45
@AshwiniChaudhary: It's basically the same as `// 2`; division by two by bitshifting. — Martijn Pieters, Sep 09 '12 at 19:52

score 2 · Answer 2 · answered Sep 09 '12 at 13:16

Not strictly an answer but a very common habit of new programmers is violating Separation of Concerns.

Much better would be:

def fibonacci(n):
    ...

def main():
    num = int(raw_input("What fibonacci number do you want to know? "))
    print fibonacci(num)

which keeps fibonacci from getting cluttered with user interface code.

score 1 · Answer 3 · answered Sep 09 '12 at 11:49

1

You can use matrix exponention, which is done in O(logn) integer ops, or use the closed form expression, which is done in the speed of your power function. (Beware from numerical errors of using closed form expression).

answered Sep 09 '12 at 11:49

amit

175,853
27
231
333

I suspect these count as "advanced concepts" and probably are also not in the spirit of the question! – Andrew Jaffe Sep 09 '12 at 12:12

Bakuriu · Answer 4 · 2012-09-09T12:10:19.253

If you want to compute fast the fibonacci numbers you should use the closed expression or matrix exponentiation. If you want to be able to generate arbitrarily large numbers, then use the matrix exponentiation.

An example implementation:

>>> def matrix_mul(A, B):
...     return ([A[0][0] * B[0][0] + A[0][1] * B[1][0],
...              A[0][0] * B[0][1] + A[0][1] * B[1][1]],
...             [A[1][0] * B[0][0] + A[1][1] * B[1][0],
...              A[1][0] * B[0][1] + A[1][1] * B[1][1]])
... 
>>> def matrix_exp(A, e):
...     if not e:
...             return [[1,0],[0,1]]
...     elif e % 2:
...             return matrix_mul(A, matrix_exp(A, e-1))
...     else:
...             sq= matrix_exp(A, e//2)
...             return matrix_mul(sq, sq)
... 
>>> def fibo(n):
...     M = [[1,1],[1,0]]
...     return matrix_exp(M, n)[0][0]
>>> fibo(1)
1
>>> fibo(2)
2
>>> fibo(3)
3
>>> fibo(4)
5
>>> fibo(5)
8
>>> fibo(115)
781774079430987230203437L
>>> fibo(123456)
#instantaneus output of a HUGE number

There is also this unreadable version which is a lot faster:

>>> fibs = {0: 0, 1: 1}
>>> def fib(n):
...     if n in fibs: return fibs[n]
...     if n % 2 == 0:
...         fibs[n] = ((2 * fib((n / 2) - 1)) + fib(n / 2)) * fib(n / 2)
...         return fibs[n]
...     else:
...         fibs[n] = (fib((n - 1) / 2) ** 2) + (fib((n+1) / 2) ** 2)
...         return fibs[n]
... 
>>> timeit.timeit('fib(1000000)', 'from __main__ import fib', number=100)/100
0.0012753009796142578     # 1 millisecond for the millionth fibonacci number :O

It's the last one of literateprograms.org(linked in the other answer).

That's dijkstra's algorithm. :-) Note that that algorithm uses caching, so there is a memory cost. — Martijn Pieters, Sep 09 '12 at 12:50
Yes, but what I've tried it actually does not cost that much for the speed gain. — Bakuriu, Sep 09 '12 at 18:50
The readable version returns different result for `fibo(300)` — Andrei, Jul 24 '15 at 11:53
@Andrei Your statement isn't meaningful. Different *from what*? If you mean readable vs unreadable, the unreadable version uses `/` which can return floats, and hence there may be rouding errors... — Bakuriu, Jul 24 '15 at 12:05
The difference is in the first digit so I guess there is a bug. — Andrei, Jul 24 '15 at 12:16

score 0 · Answer 5 · edited Oct 27 '15 at 18:38

0

This is very efficient:

import numpy as np

M = np.matrix([[1, 1], [1, 0]])

def fib(n):
  if n < 2:
    return 1
  MProd = M.copy()
  for _ in xrange(n-2):
    MProd *= M
  return MProd[0,0] + MProd[0,1]

edited Oct 27 '15 at 18:38

Nathaniel Ford

20,545
20
91
102

answered Oct 27 '15 at 18:15

Sam

9
2

You really should explain where the efficiency gains of this implementation come from, over the OP's implementation. – Nathaniel Ford Oct 27 '15 at 18:38

How efficient is this Python Code for the fibonacci sequence?

5 Answers5