def fibLoops(num):
    vals = [0,1]
    for i in range(2,num+1):
        vals.append(vals[i-1] + vals[i-2])
    return vals[num]

def fibRecurse(num):
    if num == 0 or num == 1:
        return num
    else:
        return fibRecurse(num-1) + fibRecurse(num-2)
        
def superFibLoops(num):
    lo, hi = 0, 1
    for i in xrange(num):
        lo, hi = hi, lo+hi
    return lo

def superFibRecurse(num):
    def fib_h(a, b, p, q, count):
        if count == 0:
            return b
        elif count % 2 == 0:
            return fib_h(a, b, (p*p)+(q*q), (q*q)+(2*p*q), count/2)
        else:
            return fib_h((b*q)+(a*q)+(a*p), (b*p)+(a*q), p, q, count-1)
            
    return fib_h(1, 0, 0, 1, num)