xsnippet logotype

xsnippet

Fast doubling Fibonacci algorithm [ Python ]

by Guest
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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)