Faster Recursive Fibonacci Numbers

[Ian Kelly]

On Thu, May 19, 2011 at 11:58 PM, Steven D'Aprano
<steve+comp.lang.python at pearwood.info> wrote:
> Sure, which is why the above fib() function will become increasing
> inaccurate beyond some given n, by memory about n=71 or so. Er, at least
> the fib() function that *was* above until you deleted most of it :)
>
> If you want an *accurate* fib() function using exponentiation of φ, you
> need arbitrary precision non-integers.

This seems to work for arbitrary n, although I only tested it out to
about n=2000.

from decimal import Decimal, localcontext
from math import sqrt

def fib(n):
    if n <= 70:
        return fib_float(n)
    else:
        return fib_decimal(n)

phi_float = (1 + sqrt(5)) / 2
def fib_float(n):
    numerator = (phi_float ** n) - (1 - phi_float) ** n
    denominator = sqrt(5)
    return int(round(numerator / denominator))

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())

Cheers,
Ian