fib.py

def fibo(n):
    if n == 0:
        return 0

    x = [0, 1]
    if n < 2:
        return sum(x)

    for i in range(2, n):
        x.append( x[i-1] + x[i-2] )

    print x
    return sum(x)

print fibo(40)


#wang[10:43][/tmp]$ time python fibo.py 
#[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368,
#75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169,
#63245986]
#165580140
#
#real	0m0.017s
#user	0m0.016s
#sys	0m0.004s

#wang[10:46][/tmp]$ cat /proc/cpuinfo | grep "model name"
#model name	: Intel(R) Core(TM) i5-2430M CPU @ 2.40GHz
#model name	: Intel(R) Core(TM) i5-2430M CPU @ 2.40GHz
#model name	: Intel(R) Core(TM) i5-2430M CPU @ 2.40GHz
#model name	: Intel(R) Core(TM) i5-2430M CPU @ 2.40GHz