Fibonacci Sequence and Long numbers.

[ABS Support]

"Neil Macneale" <macneale at cats.ucsc.edu> wrote in message
news:macneale-A294A5.15354305102000 at news.scruznet.com...
> 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.

I tried on WinNT w/2.0b2 and got:  "RuntimeError: Maximum recursion depth
exceeded" as the last line of the errors.  Seems to be some sort of max
recursion depth.  Probably some guru knows more about this and the
why-fors.

> 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.

When you go up by 100 at a time you are only going 100 deep on your
recursion before hitting the top of the
cache.  The largest jump I could make was 988 (ie fib(1000) then fib(1988)),
a larger step blew up.

Is this a bug or a feature?

newbie-ly,
                Tim