fibonacci with O(log(n)) complexity

fib_log.py

# 
from decimal import *

def fib(n):
    return fib_iter(1,0,0,1,Decimal(n))

def fib_iter(a,b,p,q,n):
    nb_iter = 0

    while n != 0:
    	#print(a,b,p,q,n)
        if n%2 == 0:
            p,q = p*p+q*q, (2*p*q)+q*q
            n = int(n/2)
        else:
            a,b = (b*q+a*q+a*p), (b*p+a*q)
            n = n-1
        nb_iter = nb_iter+1
        print(n)
    return b

n = 30000000
fN = fib(Decimal(str(n)))
print("fib({})".format(n))