import functools def fib_double(n): return _fib_double(n)[1] def _fib_double(n): if n == 0: return (0, 1) else: a, b = _fib_double(n // 2) c = a * (b * 2 - a) d = a * a + b * b if n % 2 == 0: return (c, d) else: return (d, c + d)