Language Shootout

[Bengt Richter]

On Tue, 10 Jul 2001 01:01:23 GMT, bokr at accessone.com (Bengt Richter)
wrote:
>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)  ;-)
[...]
>I haven't fine tuned this. It's a close translation of
Oops, several things:
    - That 15 seconds was mostly conversion for printing.
      Actual calculation time was more like 0.8 sec ;-)
    - I should have eliminated an expression

Changes
---
#eliminated this >    fkm1 = fkp1 - fk
>    if n&1:
>        return fkp1*fkp1 + fk*fk, fkp1*( fkp1+fk+fk)
>    else: 
#changed this >        return fk*(fk+fkm1+fkm1), fkp1*fkp1 + fk*fk
         return fk*(fkp1+fkp1-fk), fkp1*fkp1 + fk*fk
---

Sheesh. I also changed the a+a things above to a<<1 but it's in the
noise. Wonder if a**2 is much different from a*a for big longs...

I put in a clock() timer for calculation and printing. This gives
about 380 microseconds +- a few for N=32, and for N=100000:

That took   0.796213 seconds to calculate, and 15.226808 to print.
That took   0.797725 seconds to calculate, and 15.006354 to print.
That took   0.804495 seconds to calculate, and 14.893308 to print.
That took   0.800631 seconds to calculate, and 14.624085 to print.
is representative, again on

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

Given the print time, apparently this recursion beat iteration by
0.8 vs about 15 seconds ((~32 hand timed load, calc, print) -15).

Never say never ;-)

Revised version:
______________________________________________________________

# fibpx.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. 
#
# Updated 2001-07-09 bokr
#
import sys

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

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

import time
def main():
    if len(sys.argv) != 2:
        sys.stderr.write("usage: %s number\n" % sys.argv[0])
        sys.exit(2)
    tStart = time.clock()
    answer = ffib( long(sys.argv[1]) )
    tEnd = time.clock()
    print 'fib(',sys.argv[1],') =\n', answer
    tEndPrint = time.clock()
    print "\nThat took %10.6f seconds to calculate," \
        " and %8.6f to print." % (tEnd-tStart, tEndPrint-tEnd)
if __name__ == "__main__":
    main()
______________________________________________________________