fib.py

def fib_recursive_squaring(n):
    def __multi(f1, g1, h1, f2, g2, h2):
        return f1 * f2 + g1 * g2, f1 * g2 + g1 * h2, g1 * g2 + h1 * h2

    def __fib(n):
        if n == 1:
            return 0, 1, 1

        f, g, h = __fib(int(n / 2))
        t1, t2, t3 = __multi(f, g, h, f, g, h)

        if n % 2 == 1:
            t1, t2, t3 = __multi(t1, t2, t3, 0, 1, 1)

        return t1, t2, t3

    return __fib(n)[1]