|
#!/usr/bin/python
# Filename: fib.py
# increase [f(n), f(n+1)] to [f(n+1), f(n+2)]
def __fib_inc(fib_n):
fib_n[1] += fib_n[0]
fib_n[0] = fib_n[1] - fib_n[0]
# convert [f(n), f(n+1)] to [f(2*n), f(2*n+1)]
def __fib_n_2n(fib_n):
a = fib_n[0]
b = fib_n[1]
fib_n[0] = 2 * a * b - a * a
fib_n[1] = b * b + a * a
# get f(n) by recursion
def __fib(n, fib_n):
if n == 1:
return fib_n[0]
else:
__fib(n / 2, fib_n)
__fib_n_2n(fib_n)
if n % 2 == 1:
__fib_inc(fib_n)
return fib_n[0]
# get f(n)
def fib(n):
if n <= 0:
return 0
else:
return __fib(n, [1, 1])
for i in range(0, 21):
print i, ":", fib(i)
|
