Faster Recursive Fibonacci Numbers

[RJB]

On May 17, 9:36 am, rusi <rustompm... at gmail.com> wrote:
> On May 17, 8:50 pm, RJB <rbott... at 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 :-) ]

Thank you!  Very cool and clear.  I
hoped that there was something that Python made natural I couldn't see
after 50 years in other languages.

I'd like to work on combining both approaches.  It may take a while...