[Tutor] fib (was recursive factoring)

[Lloyd Hugh Allen]

Of course, an even faster way to compute fibs would be to use

import math
r = (1 + math.sqrt(5))/2
s = (1 - math.sqrt(5))/2
def fib(n):
    return long((r**n - s**n)/math.sqrt(5))

if only Python had infinite precision. This method should break about
where floats run out of digits. Might be able to squeeze out a few more
by using 

((1  +  math.sqrt(5))**n) / (2**n) instead of r**n

or even more if there's an infinite precision math module out there.
Maybe by using continued fractions, unless that would be slower than
using a list-growing technique to "recursively" compute fibs in the
first place.

Lots of info on above relationship @
http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/fib.html

Sometimes (granted, not above, since it breaks--although I'm curious
where) recognizing a general formula is the best way to recurse.

For instance, I would definitely prefer

def sum1(first,last):
    return ((first + last)*(last - first + 1))/2

to some algorithm that first creates a list of the numbers from first to
last and then adds them up.

(last - first + 1) is the number of numbers in the list. If I remembered
it right, the formula is due to Gauss (and if I remembered the formula
wrong, it's my own creation). We usually think of it as the average of
the first and last number, times the number of elements in the list;
however, if you first take the average, you'll lose a .5 when dividing
an odd sum. (I haven't 2.2ed yet, and wouldn't want a groady float
getting in there anyway).

If you want to use this with really big numbers, neither of which are
yet long, it would probably be good to change (first + last) to (first +
long(last)) (which somehow amuses me anyway).

Danny Yoo wrote:
> 
> On Thu, 17 Jan 2002 mikalzet@libero.it wrote:
> 
> > def fibonacci(n):
> >  a = 1L
> >  b = 1L
> >  if n < 2: return 1
> >  else:
> >       z=2
> >       while z <= n:
> >         c = a + b
> >         a, b = b, c
> >           z = z + n
> >         return c
> >