Fibonacci Sequence and Long numbers.

[Alex Martelli]

"Will Ware" <wware at world.std.com> wrote in message
news:G1zo3M.Fzw at world.std.com...
> Neil Macneale (macneale at cats.ucsc.edu) wrote:
> > I am using MacPython 1.5.2 on a G3 powerbook,  and I am getting a
> > strange result from a fibonachi function.
>
> You might have better luck with a dictionary than a list, something
> like this:
>
> cache = { }
> cache[0] = 0L
> cache[1] = 1L
>
> def fib(i):
>     try: return cache[i]
>     except KeyError: pass
>     cache[i] = fib(i-1) + fib(i-2)
>     return cache[i]
>
> print fib(1000)
>
> Oddly, when I try fib(10000) on a Linux box (Red Hat 6.2), I get a
> segmentation fault and core dump. That's a pretty rare thing to get
> from Python, it might suggest a fault in the long-integer arithmetic
> module. Never having looked at it, and having no idea whose toes I'm
> stepping on by suggesting this possibility, I'll now duck back into
> the woodwork.

Hmmm, maybe a stack overflow?  Using 0.0 and 1.0 for the original
cache entries (so that floating-point arithmetic is involved rather
than long-integers) gives me exactly the same huge-traceback (no
segfault in either case) on Python 2.0b2 (IDLE, Win/NT 4 SP6).

I suspect that in this case recursion does need to be truly
eliminated, if you need computations as deep as fib(10000).  And
in this case, you might as well go for the lower overhead of a
list of cached (memoized) results rather than a dictionary.
Performance gets REALLY better...!

Consider this little module prova.py:

cache = { }
cache[0] = 0L
cache[1] = 1L

def fibd(i):
    try: return cache[i]
    except KeyError: pass
    cache[i] = fibd(i-1) + fibd(i-2)
    return cache[i]

lcac = [0L, 1L]

def fibl(i):
    try: return lcac[i]
    except IndexError: pass
    now_have = len(lcac)
    but_need = i+1
    lcac.extend([0]*(but_need-now_have))
    for j in range(now_have, but_need):
        lcac[j]=lcac[j-1]+lcac[j-2]
    return lcac[i]

import profile
profile.run('prova.fibd(500)')
profile.run('prova.fibl(500)')


Results of a "reload(prova)" are:

         1001 function calls (3 primitive calls) in 0.160 CPU seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.159    0.159 <string>:1(?)
        0    0.000             0.000          profile:0(profiler)
        1    0.001    0.001    0.160    0.160 profile:0(prova.fibd(500))
    999/1    0.159    0.000    0.159    0.159 prova.py:5(fibd)


         3 function calls in 0.005 CPU seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.004    0.004 <string>:1(?)
        0    0.000             0.000          profile:0(profiler)
        1    0.001    0.001    0.005    0.005 profile:0(prova.fibl(500))
        1    0.004    0.004    0.004    0.004 prova.py:13(fibl)


<module 'prova' from 'D:\Python20\prova.py'>

And, of course...:

>>> prova.fibl(10000)
3364476487643178326662161200510754331030214846068006390656476997468008144216
6662368155595513633734025582065332680836159373734790483865268263040892463056
4318873545443695598274916066020998841839338646527313000888302692356736131351
1757929743785441375213052050434770160226475831890652789085515436615958298727
9682987510631200575428783453215515103870818298969791613127856265033195487140
2142875326981879620469360978799003509623022910263681314931952756302278376284
4154036058440257211433496118002309120828704608892396232883546150577658327125
2546093591128203925285393434620904245248929403901706233888991085841065183173
3604374707379085526317643257339937128719375877468974799263058370657428301616
3740896917842637862421283525811282051637029808933209990570792006436742620238
9783111470054074998459250360633560933883831923386783056136435351892133279732
9081337326426526339897639227234078829281779535805709936910491754708089318410
5614632233821746563732124822638309210329770164805472624384237486241145309381
2206564914032751086643394517512161526545361333111314042436854805106765843493
5238369596534280717687753283482343455573667197313927462736291082106792807847
1803532913117677892465908993863545932789452377767440619224033763867400402133
0343297496902028328145933418826817683893072003634795623117103101291953169794
6076327375892535307725523759437884345040677155557790564504430166401194625809
7221672975861502696844314695203461493229110597067624326851599283470989128470
6740862008587135016260312071903172086094081298321581077282076353186624611278
2455372085323653057759564300725177443150515396009051686032203491632226408852
4885243315805153484962243484829938090507048348244932745373262456775587908918
7190803662058009594743150052402532709746995318770724376825907419939632265984
1474981936092852239450397071654431564213281576889080587831834049174345562705
2022356484649519611246026831397097506938264870661326450766507461151267752274
8621598642530711298441182622661057163515069260029861704945425047491378115154
1399415506712562711971332527636319396069028956502882686083622410820505624307
01794976171121233066073310059947366875L
>>>


Alex