Python code to generate the nth Fibonacci number in logarithmic time.

fibonacci_logarithmic.py

# Calculates the nth Fibonacci number using a logarithmic algorithm.
def fibonacci(n):
    # Helper function: returns True if n is an even number.
    even = lambda n: (n % 2 == 0)

    (current, next, p, q) = (0, 1, 0, 1)    

    while (n > 0):
        if (even(n)):
            (p, q) = (p**2 + q**2, q**2 + 2*p*q)
            n /= 2
        else:
            (current, next) = (p*current + q*next, q*current + (p+q)*next)
            n -= 1
    
    return current