Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!aioe.org!feeder.news-service.com!xlned.com!feeder5.xlned.com!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:date:message-id:subject:from:to :cc:content-type:content-transfer-encoding; b=qvKJB0oQh6fEW8aU8fNSG6puIhHBVnndisps7lbhqqGdabVd6i7Z1UaZOCM8H01QED jqb+LVNaElu1RTPMNDvCPo32Nwz6/Usdcdl+bzDj6LpnGr4w97d3ZppfBBArA1xMlyeG QdVF2e17ZNGuMSlr4c/a5wciE8Jtxiy2uST/8=
MIME-Version: 1.0
In-Reply-To: <9d9c163b-14fd-4131-81bb-105c3b97c432@h36g2000pro.googlegroups.com>
References: <108ce447-10fa-4cf7-84ef-440ee18dbfd4@22g2000prx.googlegroups.com> <9d9c163b-14fd-4131-81bb-105c3b97c432@h36g2000pro.googlegroups.com>
Date: Tue, 17 May 2011 10:02:21 -0700
Subject: Re: Faster Recursive Fibonacci Numbers
From: geremy condra <debatem1@gmail.com>
To: rusi <rustompmody@gmail.com>
Content-Type: text/plain; charset=ISO-8859-7
Content-Transfer-Encoding: quoted-printable
Cc: python-list@python.org
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.1680.1305651743.9059.python-list@python.org>
Lines: 83
NNTP-Posting-Host: 82.94.164.166
Xref: x330-a1.tempe.blueboxinc.net comp.lang.python:5581

On Tue, May 17, 2011 at 9:36 AM, rusi <rustompmody@gmail.com> wrote:
> On May 17, 8:50=A0pm, RJB <rbott...@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 =A0If F[n] is the n'th Fibonaci number then
>> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0F[n+m] =3D F[m]*F[n+1] + F[m-1]*F=
[n].
>> =A0 First set m =3D n+1
>> =A0 =A0F[ 2*n+1 ] =3D F[n+1]**2 + F[n]*2.
>>
>> =A0 Then put m =3D n in Knuth's formula,
>> =A0 =A0 =A0 =A0 =A0 =A0F[ 2*n ] =3D F[n]*F[n+1] + F[n-1]* F[n],
>> =A0 =A0and replace F[n+1] by F[n]+F[n-1],
>> =A0 =A0 =A0 =A0 =A0 =A0F[ 2*n ] =3D F[n]*(F[n] + 2*F[n-1]).
>> """
>> =A0 =A0 =A0 =A0 if n<=3D0:
>> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 return 0
>> =A0 =A0 =A0 =A0 elif n<=3D2:
>> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 return 1
>> =A0 =A0 =A0 =A0 elif n%2=3D=3D0:
>> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 half=3Dn//2
>> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 f1=3Dfibo(half)
>> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 f2=3Dfibo(half-1)
>> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 return f1*(f1+2*f2)
>> =A0 =A0 =A0 =A0 else:
>> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 nearhalf=3D(n-1)//2
>> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 f1=3Dfibo(nearhalf+1)
>> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 f2=3Dfibo(nearhalf)
>> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 return f1*f1 + f2*f2
>>
>> RJB the Lurkerhttp://www.csci.csusb.edu/dick/cs320/lab/10.html
>
> -------------------------------------------------------------
> Its an interesting problem and you are 75% there.
> You see the halving gives you logarithmic behavior and the double
> calls give exponential behavior.
>
> So how to get rid of double calls? =A0Its quite simple: Just define your
> function in terms of return pairs of adjacent pairs ie (fib(n), fib(n
> +1)) for some n rather then a single number fib(n)
>
> Here's a straightforward linear function:
>
> def fp(n): =A0#fibpair
> =A0 =A0if n=3D=3D1:
> =A0 =A0 =A0 =A0return (1,1)
> =A0 =A0else:
> =A0 =A0 =A0 =A0a,b =3D fp(n-1)
> =A0 =A0 =A0 =A0return (b, a+b)
>
> def fib(n):
> =A0 =A0a,b =3D fp(n)
> =A0 =A0return a
>
> ---------------
> Now use this (pairing) idea with your (halving) identities and you
> should get a logarithmic algo.
>
> [If you cant do it ask again but yes its fun to work out so do
> try :-) ]
> --
> http://mail.python.org/mailman/listinfo/python-list
>

or O(1):

=F6 =3D (1 + sqrt(5)) / 2
def fib(n):
    numerator =3D (=F6**n) - (1 - =F6)**n
    denominator =3D sqrt(5)
    return round(numerator/denominator)

Testing indicates that it's faster somewhere around 7 or so.

Geremy Condra