def fib1(n):
def fib_inner(n):
'''Returns F[n] and L[n]'''
if n == 0:
return 0, 2
m = n >> 1
u, v = fib_inner(m)
q = -2 if (m & 1) == 1 else 2
u, v = u * v, v * v - q
if n & 1 == 1:
u1 = (u + v) >> 1
return u1, 2*u + u1
else:
return u, v
if n <= 0:
return 0
m = n >> 1
u, v = fib_inner(m)
if (n & 1) == 1:
u1 = (u + v) >> 1
return u*u + u1*u1
else:
return u * v
def fib2(n):
def fib_inner(n):
'''Returns F[n] and F[n+1]'''
if n == 0:
return 0, 1
m = n >> 1
u, v = fib_inner(m)
if (n & 1) == 1:
return u*u + v*v, v * (2*u + v)
else:
return u * (2*v - u), u*u + v*v
if n <= 0:
return 0
m = n >> 1
u, v = fib_inner(m)
if (n & 1) == 1:
return u*u + v*v
else:
return u * (2*v - u)
def fib3(n):
def fib_inner(n):
'''Returns F[n-1] and F[n]'''
if n == 0:
return 1, 0
m = n >> 1
u, v = fib_inner(m)
if (n & 1) == 1:
return v * (2*u + v), u*u + 2*v*(u + v)
else:
return u*u + v*v, v * (2*u + v)
if n <= 0:
return 0
m = n >> 1
u, v = fib_inner(m)
if (n & 1) == 1:
return u*u + 2*v*(u + v)
else:
return v * (2*u + v)
def fib4(n):
def fib_inner(n):
'''Returns F[n] and F[n+1]'''
if n == 0:
return 0, 1
m = n / 3
u, v = fib_inner(m)
q = -3 if (m & 1) == 1 else 3
if n%3 == 0:
return u*(5*u*u + q), v*v*v + u*u*(3*v - u),
if n%3 == 1:
return v*v*v + u*u*(3*v - u), v*v*(v + 3*u) + u*u*u
else:
return v*v*(v + 3*u) + u*u*u, v*(5*v*v - q)
if n <= 0:
return 0
m = n / 3
u, v = fib_inner(m)
q = -3 if (m & 1) == 1 else 3
if n%3 == 0:
return u*(5*u*u + q)
if n%3 == 1:
return v*v*v + u*u*(3*v - u)
else:
return v*v*(v + 3*u) + u*u*u
from timeit import timeit
runs = 10
for test in ['fib1', 'fib2', 'fib3', 'fib4']:
print test, 'small values:',
print timeit(
setup = 'from __main__ import %s'%test,
stmt = 'for n in range(10000): %s(n)'%test,
number = runs)/runs, 'secs per run'
print test, 'large values:',
print timeit(
setup = "from __main__ import %s\n"%test +
"from random import seed, randint\n" +
"seed('fibonacci')",
stmt = '%s(randint(1000000, 2000000))'%test,
number = runs)/runs, 'secs per value'
print