[pypy-issue] [issue1330] fib(47) vs fib(48)

[Eric]

New submission from Eric <eric.saintetienne at gmail.com>:

Consider the recursive fibonacci alrgorithm (see code attached) on a 32bit Linux 
machine: fib(47) is much slower than fib(48) (two to three times slower)

This affects pypy 1.9 as well as 1.8

It's worth noting that fib(N) has to be held in a 'long' for N >= 47 and can be 
held in an 'int' otherwise, as illustrated bellow:

fib(45)=1134903170
fib(46)=1836311903
fib(47)=2971215073  > sys.maxint
fib(48)=4807526976  > sys.maxint
fib(49)=7778742049  > sys.maxint

----------
files: fib.py
messages: 5013
nosy: gembrot, pypy-issue
priority: performance bug
release: 1.9
status: unread
title: fib(47) vs fib(48)

________________________________________
PyPy bug tracker <tracker at bugs.pypy.org>
<https://bugs.pypy.org/issue1330>
________________________________________
-------------- next part --------------
N=47

def fib(n):
    if n < 2:
        return n
    return fib(n-1) + fib(n-2)

print "fib(%d)=%d" % (N, fib(N))

# eof