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

Eric tracker at bugs.pypy.org
Thu Nov 22 11:50:06 CET 2012

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(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>
-------------- next part --------------

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

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

# eof

More information about the pypy-issue mailing list