Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #5581

Re: Faster Recursive Fibonacci Numbers

Show key headers only | View raw

On Tue, May 17, 2011 at 9:36 AM, rusi <rustompmody@gmail.com> wrote:
> On May 17, 8:50 pm, 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.  It was easy.  Enjoy.  And tell me how I can improve it!
>>
>> def fibo(n):
>>         """A Faster recursive Fibonaci function
>> Use a formula from Knuth Vol 1 page 80, section 1.2.8:
>>            If F[n] is the n'th Fibonaci number then
>>                    F[n+m] = F[m]*F[n+1] + F[m-1]*F[n].
>>   First set m = n+1
>>    F[ 2*n+1 ] = F[n+1]**2 + F[n]*2.
>>
>>   Then put m = n in Knuth's formula,
>>            F[ 2*n ] = F[n]*F[n+1] + F[n-1]* F[n],
>>    and replace F[n+1] by F[n]+F[n-1],
>>            F[ 2*n ] = F[n]*(F[n] + 2*F[n-1]).
>> """
>>         if n<=0:
>>                 return 0
>>         elif n<=2:
>>                 return 1
>>         elif n%2==0:
>>                 half=n//2
>>                 f1=fibo(half)
>>                 f2=fibo(half-1)
>>                 return f1*(f1+2*f2)
>>         else:
>>                 nearhalf=(n-1)//2
>>                 f1=fibo(nearhalf+1)
>>                 f2=fibo(nearhalf)
>>                 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?  Its 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):  #fibpair
>    if n==1:
>        return (1,1)
>    else:
>        a,b = fp(n-1)
>        return (b, a+b)
>
> def fib(n):
>    a,b = fp(n)
>    return 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):

φ = (1 + sqrt(5)) / 2
def fib(n):
    numerator = (φ**n) - (1 - φ)**n
    denominator = sqrt(5)
    return round(numerator/denominator)

Testing indicates that it's faster somewhere around 7 or so.

Geremy Condra

Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Faster Recursive Fibonacci Numbers RJB <rbotting@csusb.edu> - 2011-05-17 08:50 -0700
  Re: Faster Recursive Fibonacci Numbers Ian Kelly <ian.g.kelly@gmail.com> - 2011-05-17 10:23 -0600
  Re: Faster Recursive Fibonacci Numbers rusi <rustompmody@gmail.com> - 2011-05-17 09:25 -0700
  Re: Faster Recursive Fibonacci Numbers rusi <rustompmody@gmail.com> - 2011-05-17 09:36 -0700
    Re: Faster Recursive Fibonacci Numbers geremy condra <debatem1@gmail.com> - 2011-05-17 10:02 -0700
      Re: Faster Recursive Fibonacci Numbers Jussi Piitulainen <jpiitula@ling.helsinki.fi> - 2011-05-17 20:19 +0300
        Re: Faster Recursive Fibonacci Numbers geremy condra <debatem1@gmail.com> - 2011-05-17 11:56 -0700
          Re: Faster Recursive Fibonacci Numbers Wolfram Hinderer <wolfram.hinderer@googlemail.com> - 2011-05-17 14:04 -0700
            Re: Faster Recursive Fibonacci Numbers geremy condra <debatem1@gmail.com> - 2011-05-17 14:59 -0700
            Re: Faster Recursive Fibonacci Numbers rusi <rustompmody@gmail.com> - 2011-05-17 21:43 -0700
      Re: Faster Recursive Fibonacci Numbers Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-05-19 22:47 +0000
        Re: Faster Recursive Fibonacci Numbers Chris Angelico <rosuav@gmail.com> - 2011-05-20 09:37 +1000
          Re: Faster Recursive Fibonacci Numbers Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-05-20 05:58 +0000
            Re: Faster Recursive Fibonacci Numbers Chris Angelico <rosuav@gmail.com> - 2011-05-20 16:06 +1000
              Re: Faster Recursive Fibonacci Numbers harrismh777 <harrismh777@charter.net> - 2011-05-20 01:26 -0500
                Re: Faster Recursive Fibonacci Numbers Chris Angelico <rosuav@gmail.com> - 2011-05-20 16:54 +1000
                Re: Faster Recursive Fibonacci Numbers Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-05-20 17:07 +0000
                Re: Faster Recursive Fibonacci Numbers geremy condra <debatem1@gmail.com> - 2011-05-20 11:43 -0700
                Re: Faster Recursive Fibonacci Numbers Chris Angelico <rosuav@gmail.com> - 2011-05-21 10:44 +1000
              Re: Faster Recursive Fibonacci Numbers Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2011-05-21 20:49 +1200
            Re: Faster Recursive Fibonacci Numbers Ian Kelly <ian.g.kelly@gmail.com> - 2011-05-20 01:26 -0600
            Re: Faster Recursive Fibonacci Numbers Ian Kelly <ian.g.kelly@gmail.com> - 2011-05-20 01:32 -0600
              Re: Faster Recursive Fibonacci Numbers SigmundV <sigmundv@gmail.com> - 2011-05-20 03:53 -0700
        Re: Faster Recursive Fibonacci Numbers geremy condra <debatem1@gmail.com> - 2011-05-19 17:03 -0700
  Re: Faster Recursive Fibonacci Numbers Raymond Hettinger <python@rcn.com> - 2011-05-24 16:44 -0700

csiph-web