Fibonacci in logarithmic time

fibonacci.py

from collections import namedtuple

class Transform(namedtuple('Transform', 'p q')):
    """
    The value ``Transform(p, q)`` represents the matrix
    ``[[p+q, q], [q, p]]``.
    """

    def __mul__(self, other):
        """Compose two transformations end-to-end."""
        return self.__class__(
                self.p * other.p + self.q * other.q,
                self.p * other.q + self.q * (other.p + other.q))

    def __pow__(self, n):
        """"Exponentiation by squaring! Exclamation marks!"""
        if n == 0:
            return self.__class__(1, 0)
        elif n == 1:
            return self
        elif n % 2 == 0:
            return (self * self) ** (n // 2)
        else:
            return self * (self * self) ** (n // 2)

    def __call__(self, a, b):
        """Left-multiply the column vector ``[a, b]`` by ``self``."""
        return (self.q * b + self.p * a,
                (self.p + self.q) * b + self.q * a)


def fibonacci(n):
    a, b = (Transform(0, 1) ** n)(0, 1)
    return a