On Thu, May 19, 2011 at 11:58 PM, Steven D'Aprano
<steve+comp.lang.pyt...@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
--
http://mail.python.org/mailman/listinfo/python-list
