My blogpost at assemblando.com

blogpost.py

def fibo(n):
  if n==0 or n==1:
    return n
  else:
    return fibo(n-1)+fibo(n-2)

def fibo2(n):
    if n==0 or n==1:
        return n
    n -= 1
    previous=1
    current=1
    while n>1:
        previous,current = current, current+previous
        n -= 1
    return current

def pow(b,n):
    if n==1:
        return b
    return b*pow(b,n-1)

def pow2(b,n,acc=1):
    if n==1:
        return b*acc
    return pow2(b,n-1,acc*b)

def pow3(b,n):
    if n==1:
        return b

    if n%2:
        h = pow3(b,(n-1)/2)
        return b*h*h
    else:
        h = pow3(b,n/2)
        return h*h

def pow4(b,n,f=lambda x,y:x*y):
    if n==1:
        return b

    if n%2:
        h = pow4(b,(n-1)/2,f)
        return f(f(h,h),b)
    else:
        h = pow4(b,n/2,f)
        return f(h,h)

def mult_matrix(ma,mb):
    (a,b),(c,d) = ma
    (e,f),(g,h) = mb
    return [[a*e+b*g,a*f+b*h],[c*e+d*g,c*f+d*h]]

fib_matrix = [[1,1],[1,0]]

def fibo3(n):
    if n==0 or n==1:
        return n

    return pow4(fib_matrix, n, mult_matrix)[0][1]