Language Shootout

[Bengt Richter]

On Mon, 09 Jul 2001 20:53:41 GMT, Paul Winkler <slinkp23 at yahoo.com>
wrote:

>James Logajan wrote:
>> 
>> Paul Winkler wrote:
>> > So basically what that benchmark tells me is: "Don't write recursively in Python
>> > if performance is an issue".
>> 
>> Well yes, this is what benchmarks are useful for.
>
>Right. I didn't know that before I looked at the site, so I'm glad I did.
>
>I just wanted to prevent other people from making my initial mistake - assuming
>that the tests only had to produce the same result. I was surprised how far down
>the list python was on the fibonacci test until I started playing around with
>alternative implementations and realized it was the recursion that was slowing
>it down.
>
I just had a look at the site with the fibonacci
results. N=32 in 19.78 seconds. Python can do
better while still doing it recursively ;-)

I just did a python recursive fib(100000) in
just over 15 seconds, including startup and
printing to screen, by my watch. (Not a typo,
that was 100k). Of course, it might not be the
usual recursive solution (see below)  ;-)

(300mhz P2, 320MB ram, NT4sp3)
Python 2.1 (#15, Apr 16 2001, 18:25:49) [MSC 32 bit (Intel)] on win32

Simple iteration using

def fib(x):
    if x < 3:
        return 1
    f,fm1 = 1L,1L
    for i in xrange(2,x):
        f,fm1 = f+fm1,f
    return f

took over 30 seconds ;-)

I haven't fine tuned this. It's a close translation of
a scheme version I came up with about five years ago.
Dave Ulrich may remember. He pointed out that the next to
last version wasn't doing what I thought. So he helped
nudge it into being. Never did establish what wheel I was
reinventing, but apparently there is something related.

___________________________________________________________

# ffibp.py - fast recursive fibonacci algorithm using pairs 
# Copyright (c) 2001, Bengt Richter. All rights reserved. 
# Use is governed by the GNU GENERAL PUBLIC LICENSE -- see
http://gnu.org 
# NO WARRANTY EXPRESS OR IMPLIED IS GIVEN AS TO CORRECTNESS 
# OR SUITABLILITY FOR ANY PURPOSE. USE AT YOUR OWN RISK. 
#
import sys

def pfib(n):
    if n < 2: return 1L,1L
    if n == 2: return 1L,2L
    k = n / 2L
    fk,fkp1 = pfib(k)   # recursion here
    fkm1 = fkp1 - fk
    if n&1:
        return fkp1*fkp1 + fk*fk, fkp1*( fkp1+fk+fk)
    else: 
        return fk*(fk+fkm1+fkm1), fkp1*fkp1 + fk*fk

def ffib(x):
    if x < 3:
        return 1
    else:
        fxm2,fxm1 = pfib( x - 2L )
        return fxm2+fxm1        

def main():
    if len(sys.argv) != 2:
        sys.stderr.write("usage: %s number\n" % sys.argv[0])
        sys.exit(2)
    print 'fib(',sys.argv[1],') = ', ffib( long(sys.argv[1]) )

if __name__ == "__main__":
    main()
_____________________________________________________________--