Fibonacci Sequence and Long numbers.

[Neil Macneale]

Hi all,

I am using MacPython 1.5.2 on a G3 powerbook,  and I am getting a 
strange result from a fibonachi function. This is what I typed at the 
command line:

>>> cache = []
>>> cache.insert(0, 0L)
>>> cache.insert(1, 1L)
>>> def fib(i):
...    if len(cache) > i:
...       return cache[i]
...    cache.insert(i, fib(i-1) + fib(i-2))
...    return cache[i]
... 
>>> fib(1)
1L
>>> fib(2)
1L
>>> fib(3)
2L
>>> for i in range(10):
...    print fib(i)
... 
0L
1L
1L
2L
3L
5L
8L
13L
21L
34L
>>> fib(100)
354224848179261915075L

All seems good and well to this point.  But when I try:

>>> fib(1000)

I get a whole bunch of recursive erros which tell me there is an Integer 
addition error.  The strangest part is that if I slowely increment, by a 
few hundred, up to 1000,  it works fine.

>>> fib(180)
18547707689471986212190138521399707760L
>>> fib(200)
280571172992510140037611932413038677189525L
>>> fib(220)
4244200115309993198876969489421897548446236915L
>>> fib(400)
1760236806450139664682269453924112507703843833044921918867259928965753450
44216019675L
>>> fib(600)
1104330705729522423464322467677182859425902373575556063800088918752777017
05731473925618404421867819924194229142447517901959200L
>>> fib(1000)
4346655768693745643568852767504062580256466051737178040248172908953655541
7949051890403879840079255169295922593080322634775209689623239873322471161
642996440906533187938298969649928516003704476137795166849228875L

I went up all the way to 5000 this way,  but when I tried fib(7000) I 
got all the same errors again.

What is going on?

Thanks for any insight,  Neil Macneale