Faster Recursive Fibonacci Numbers

[Ian Kelly]

2011/5/20 Ian Kelly <ian.g.kelly at gmail.com>:
> def fib_decimal(n):
>    with localcontext() as ctx:
>        ctx.prec = n // 4 + 1
>        sqrt_5 = Decimal('5').sqrt()
>        phi = (1 + sqrt_5) / 2
>        numerator = (phi ** n) - (1 - phi) ** n
>        return int((numerator / sqrt_5).to_integral_value())

Note that I believe this is O(n) since the necessary precision grows
linearly with n.