2017-09-23 10:01:46 +02:00
|
|
|
def fib(n, c={0:1, 1:1}):
|
|
|
|
|
if n not in c:
|
|
|
|
|
x = n // 2
|
|
|
|
|
c[n] = fib(x-1) * fib(n-x-1) + fib(x) * fib(n - x)
|
|
|
|
|
return c[n]
|
2015-02-20 00:35:01 -05:00
|
|
|
|
2017-09-23 10:01:46 +02:00
|
|
|
fib(10000000) # calculating it takes a few seconds, printing it takes eons
|
