Path: csiph.com!x330-a1.tempe.blueboxinc.net!newsfeed.hal-mli.net!feeder1.hal-mli.net!feeder.news-service.com!newsfeed.xs4all.nl!newsfeed5.news.xs4all.nl!xs4all!post.news.xs4all.nl!not-for-mail
DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :content-type:content-transfer-encoding; b=czi2JqcXWfXo4Fr3AfvfCgSO72LmguLkIXIlbl0y7teUsIt25Ds+H+KvMuam9a1Jiv 2kPQYPCn63OJTAFV1OarF4zyBYXKt39j1hxL9gJ/5QF11RHaYEgeqTDzr3tUHamSDqcM 1EsOFThG7jKAVhH4d4C5IGYn7YTXsz18jX3eY=
MIME-Version: 1.0
In-Reply-To: <4dd602ec$0$29996$c3e8da3$5496439d@news.astraweb.com>
References: <108ce447-10fa-4cf7-84ef-440ee18dbfd4@22g2000prx.googlegroups.com> <9d9c163b-14fd-4131-81bb-105c3b97c432@h36g2000pro.googlegroups.com> <mailman.1680.1305651743.9059.python-list@python.org> <4dd59e1e$0$29996$c3e8da3$5496439d@news.astraweb.com> <mailman.1806.1305848281.9059.python-list@python.org> <4dd602ec$0$29996$c3e8da3$5496439d@news.astraweb.com>
From: Ian Kelly <ian.g.kelly@gmail.com>
Date: Fri, 20 May 2011 01:26:49 -0600
Subject: Re: Faster Recursive Fibonacci Numbers
To: Python <python-list@python.org>
Content-Type: text/plain; charset=ISO-8859-7
Content-Transfer-Encoding: quoted-printable
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.1829.1305876440.9059.python-list@python.org>
Lines: 38
NNTP-Posting-Host: 82.94.164.166
Xref: x330-a1.tempe.blueboxinc.net comp.lang.python:5835

On Thu, May 19, 2011 at 11:58 PM, Steven D'Aprano
<steve+comp.lang.python@pearwood.info> wrote:
> Sure, which is why the above fib() function will become increasing
> inaccurate beyond some given n, by memory about n=3D71 or so. Er, at leas=
t
> the fib() function that *was* above until you deleted most of it :)
>
> If you want an *accurate* fib() function using exponentiation of =F6, you
> need arbitrary precision non-integers.

This seems to work for arbitrary n, although I only tested it out to
about n=3D2000.

from decimal import Decimal, localcontext
from math import sqrt

def fib(n):
    if n <=3D 70:
        return fib_float(n)
    else:
        return fib_decimal(n)

phi_float =3D (1 + sqrt(5)) / 2
def fib_float(n):
    numerator =3D (phi_float ** n) - (1 - phi_float) ** n
    denominator =3D sqrt(5)
    return int(round(numerator / denominator))

def fib_decimal(n):
    with localcontext() as ctx:
        ctx.prec =3D n // 4 + 1
        sqrt_5 =3D Decimal('5').sqrt()
        phi =3D (1 + sqrt_5) / 2
        numerator =3D (phi ** n) - (1 - phi) ** n
        return int((numerator / sqrt_5).to_integral_value())

Cheers,
Ian