Faster Recursive Fibonacci Numbers

[Ian Kelly]

On Tue, May 17, 2011 at 9:50 AM, RJB <rbotting 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

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