Faster Recursive Fibonacci Numbers

[geremy condra]

The problem is, it isn't *just* a performance optimization, there is a
semantic difference too. Consider:

True

But using something with more precision:

False


So you get different behaviour between floats and arbitrary precision
numbers.

And this shows up in the above implementation; reimplementing it using
Fractions and a truncated continuing fraction approximation of phi and
the square root of 5 gets us up to about 500, at the cost of a very
long computation time.

Geremy Condra

 

[Chris Angelico]

The problem is, it isn't *just* a performance optimization, there is a
semantic difference too. Consider:

Sure, but I'm thinking here that the "gold standard" is accuracy, with
other types allowing a programmer to forfeit some accuracy in favour
of performance. (Oh, and I should have said "new default numeric
type".)

And, of course, I was thinking in a stupid hypothetical way that's
extremely unlikely ever to happen.

Chris Angelico

 

[Gregory Ewing]

It seems
strange to smoothly slide from native integer to long integer and just
keep on going, and yet to be unable to do the same if there's a
fractional part on it.

The trouble is that if you always compute exact results
by default, the number of digits required can blow up
very quickly.

There's a story that ABC (the predecessor to Python)
calculated everything using rationals. People found that
sometimes a calculation would take an unexpectedly long
time, and it turned out to be because internally it was
creating fractions with huge numerators and denominators.

As a consequence, Guido decided that Python would *not*
use rationals by default.

The same problem doesn't arise with ints, because the
only time you get an int with a large number of digits
is when you genuinely need a large int. So expanding
ints automatically to however many digits is needed
doesn't do any harm.

In Python 2.6 and later, there's a fractions module for
when you need it.

 

[Raymond Hettinger]

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

There are many ways to write this function. The one I like shows-off
a general purpose dynamic programming technique while staying *very*
close to a common textbook definition of a fibonacci number:

@functools.lru_cache()
def fibo(n):
return 1 if n < 2 else fibo(n-1) + fibo(n-2)

Raymond