fibonacci.py

def kombiner(Fam, Fa, Fbm, Fb):
    Fbp = Fbm + Fb
    
    return (Fam*Fbm + Fa*Fb, Fam*Fb + Fa*Fbp)

# funksjon som returnerer fibonaccitall n-1 og n
def nth_fibonacci(n):
    if n == 1:
        return (0, 1)
    else:
        # fibonaccitall x-1 og x hvor x=n/2 (rundet ned)
        (Fxm, Fx) = nth_fibonacci(n // 2)
        # fibonaccitall 2x-1 og 2x funnet ved [ kombinere (Fx,Fx1) med seg selv
        (Fam, Fa) = kombiner(Fxm, Fx, Fxm, Fx)
        if n % 2 == 1:
            # Hvis n var et oddetall må vi regne ut ett steg til
            return (Fa, Fam + Fa)
        else:
            return (Fam, Fa)