0

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

Improve this question
1
  • I wouldn't use recursion to repeat the process, but the while loop to implement this simple algorithm for finding Fibonacci numbers is fine. Commented Sep 9, 2012 at 13:08

5 Answers 5

Reset to default
3

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

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).
@MartijnPieters can you exaplain the use of >> 1 , I am bad with bit shifting. :)
@AshwiniChaudhary: It's basically the same as // 2; division by two by bitshifting.
2

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.

Improve this answer

Comments

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

Improve this answer

1 Comment

I suspect these count as "advanced concepts" and probably are also not in the spirit of the question!
1

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

Improve this answer

5 Comments

That's dijkstra's algorithm. :-) Note that that algorithm uses caching, so there is a memory cost.
Yes, but what I've tried it actually does not cost that much for the speed gain.
The readable version returns different result for fibo(300)
@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...
The difference is in the first digit so I guess there is a bug.
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]
Improve this answer

1 Comment

You really should explain where the efficiency gains of this implementation come from, over the OP's implementation.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.