[Tutor] fibonacci

[Gregor Lingl]

Jayprasad J. Hegde schrieb:

>On Wed, Feb 12, 2003 at 07:51:33PM +1100, Alfred Milgrom wrote:
>[ snip ] 
>  
>
>>Just as an exercise, I was unable to create a one-line recursive fibonacci 
>>generator, but the following works correctly for all values of n greater 
>>than 2.
>>
>>def fib(n):
>>    return (n<5)*(n-2) or fib(n-1) + fib(n-2)
>>    
>>
>
>I would not recommend creating a second order (containing two recursive elements e.g. "fib (n - 1)" and  "fib (n - 2)" ) recursive function like this. 
>It would be best if you can find...
>1. a recursive function with a single recursive element, or
>2. sticking to an iterative variant. 
>  
>

Ok. Somtimes one has a lot of work to do and nevertheless wastes time
for some questionable - if not useless - task. So I arrived at this:

def fib1liner(n, f=[0,1]):
    return(n+1>len(f))and[(lambda x:f.append(f[-2]+f[-1]))(i)for i in 
range(n+1-len(f))]and 0 or f[n]

I would not have posted it here if it had not a remarkable property ;-)
it is about a factor 50 faster than the (also iterative) classic from the
tutorial (as already  posted in this thread) :

def fib(n):
    a,b=0,1
    for i in range(n):
        a,b=b,a+b
    return a

from the turorial.

This can be seen  using:

from time import clock

def test(afib, n = 500):
    a = clock()
    for i in range(n):
        x = afib(i)
    b = clock()
    print b-a
    print x

to measure the time for calculating the first 1000 fibonacci numbers
(I use Python 2.2, which converts automtically to longints if needed):

 >>> test(fib)
3.64362016859
26863810024485359386146727202142923967616609318986952340123175997617981700247881689338369654483356564191827856161443356312976673642210350324634850410377680367334151172899169723197082763985615764450078474174626
 >>> test(fib1liner)
0.0725899317958
26863810024485359386146727202142923967616609318986952340123175997617981700247881689338369654483356564191827856161443356312976673642210350324634850410377680367334151172899169723197082763985615764450078474174626

Isn't this nice? (If you don't have to care about use of memory on your 
machine  ;-) )

Gregor

P.S.: ... and look, with time fib1liner becomes even faster:

 >>> test(fib1liner)
0.0172815211761
26863810024485359386146727202142923967616609318986952340123175997617981700247881689338369654483356564191827856161443356312976673642210350324634850410377680367334151172899169723197082763985615764450078474174626
 >>>