Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!aioe.org!feeder.news-service.com!feeder3.cambriumusenet.nl!feed.tweaknews.nl!194.109.133.85.MISMATCH!newsfeed.xs4all.nl!newsfeed6.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=NSC4cat6WzQ8s0Rs6OkprRm8q5viPOV4e8TKGfgDLb1Z20DkuKZ2oLg204hsVgaKng uDr0Uwj8mnHdyoVkB5Kb5nIx8Ha7t9IZWJn+h0A3ckrTxitrhpMCpmMcKvsqSdj4tK9j Gi+xrmHSl7N1K7/vM4nPdl60VDBJvoOqcvpEA=
MIME-Version: 1.0
In-Reply-To: <108ce447-10fa-4cf7-84ef-440ee18dbfd4@22g2000prx.googlegroups.com>
References: <108ce447-10fa-4cf7-84ef-440ee18dbfd4@22g2000prx.googlegroups.com>
From: Ian Kelly <ian.g.kelly@gmail.com>
Date: Tue, 17 May 2011 10:23:48 -0600
Subject: Re: Faster Recursive Fibonacci Numbers
To: Python <python-list@python.org>
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.1678.1305649459.9059.python-list@python.org>
Lines: 42
NNTP-Posting-Host: 82.94.164.166
Xref: x330-a1.tempe.blueboxinc.net comp.lang.python:5574

On Tue, May 17, 2011 at 9:50 AM, RJB <rbotting@csusb.edu> wrote:
> I noticed some discussion of recursion..... the trick is to find a
> formula where the arguments are divided, not decremented.
> I've had a "divide-and-conquer" recursion for the Fibonacci numbers
> for a couple of years in C++ but just for fun rewrote it
> in Python. =A0It was easy. =A0Enjoy. =A0And tell me how I can improve it!
>
> def fibo(n):
> =A0 =A0 =A0 =A0"""A Faster recursive Fibonaci function
> Use a formula from Knuth Vol 1 page 80, section 1.2.8:
> =A0 =A0 =A0 =A0 =A0 If F[n] is the n'th Fibonaci number then
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 F[n+m] =3D F[m]*F[n+1] + F[m-1]*F[n].
> =A0First set m =3D n+1
> =A0 F[ 2*n+1 ] =3D F[n+1]**2 + F[n]*2.
>
> =A0Then put m =3D n in Knuth's formula,
> =A0 =A0 =A0 =A0 =A0 F[ 2*n ] =3D F[n]*F[n+1] + F[n-1]* F[n],
> =A0 and replace F[n+1] by F[n]+F[n-1],
> =A0 =A0 =A0 =A0 =A0 F[ 2*n ] =3D F[n]*(F[n] + 2*F[n-1]).
> """
> =A0 =A0 =A0 =A0if n<=3D0:
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0return 0
> =A0 =A0 =A0 =A0elif n<=3D2:
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0return 1
> =A0 =A0 =A0 =A0elif n%2=3D=3D0:
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0half=3Dn//2
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0f1=3Dfibo(half)
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0f2=3Dfibo(half-1)
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0return f1*(f1+2*f2)
> =A0 =A0 =A0 =A0else:
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0nearhalf=3D(n-1)//2
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0f1=3Dfibo(nearhalf+1)
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0f2=3Dfibo(nearhalf)
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0return f1*f1 + f2*f2

Thanks for posting!  Actually, it looks like this is the same O(n)
algorithm that rusi posted.  There was also a O(log n) algorithm
discussed that is based on vector math.  You might want to take a
look.

Cheers,
Ian