Language Shootout

[Bengt Richter]

On Tue, 10 Jul 2001 13:54:47 GMT, ullrich at math.okstate.edu (David C.
Ullrich) wrote:

>On Tue, 10 Jul 2001 01:18:16 -0400, "Tim Peters" <tim.one at home.com>
>wrote:
>
>>[Bengt Richter]
>>> ...
>>> I just did a python recursive fib(100000) in
>>> just over 15 seconds, including startup and
which turned out to be mostly str conversion for
the print, so I thought I'd try recursion on that...
(see below ;-)
[...]
>(Took a minute to find fib.py just now, because it was filed 
>under "MatrixTypes". I calculate fib(100000) in 1.7 
>seconds this way; for comparison, str(fib(100000)) takes 
>8.0 seconds.)
Hi Dave ;-)  

Try strL for comparison. It's recursive, and faster than str
for big numbers. I got
 >>> len(strL.strL(ffib(100000)))
 20899

so you can type in 10L**20899 on the command line
for a number in the same ballpark as the fib, for a test.
On my system I get

[18:47] C:\pywk\fib>strL.py str  10L**20899
str took 13.601617 seconds

[18:47] C:\pywk\fib>strL.py strL 10L**20899
strL took  1.044989 seconds

Recursion rides again ;-)

BTW, how do you put everything inside the strL def
to hide names, and how do you recurse inside without
a warning message?

A couple of lines wrapped...
_______________________________________________________________
# strL.py -- recursive long to decimal string conversion
# 2001-07-10 bokr
#
p10d={}
def p10(n):
    if not p10d.has_key(n):
        p = p10d[n] = 10L**n
        return p
    return p10d[n]

def strLR(n,w=0):   # w>0 is known width, w<0 is searching guess
    if w == 0: return []
    if w > 0:
        if w <=9: return [('%0'+chr(w+48)+'d') % n]
        wr = w/2
        nl,nr = divmod(n,p10(wr))
        return strLR(nl,w-wr)+strLR(nr,wr)
    else:
        nl,nr = divmod(n,p10(-w))
        if nl:
            return strLR(nl, 2*w) + strLR(nr,-w)
        else:
            if w >= -9:
                return ['%d' % n]
            else:
                return strLR(nr,w/2)

def strL(n):
    if n<0:
        return ''.join(['-']+strLR(-n,-9))
    else:
        return ''.join(strLR(n,-9))


from time import clock
import sys
def main():
    def pr(x):
        print x

    def psl(x):
        s = strL(x)
        sys.stdout.write(s)
        sys.stdout.write('\n')
        

    dt={'str':str,'strL':strL,'repr':repr, 'print':pr, 'printStrL':psl
}

    try:
        x=long( eval(sys.argv[2]) )
        fn=sys.argv[1]
        fcn=dt[fn]
    except:
        sys.stderr.write("usage: %s [str strL repr print printStrL]
<const expr>\n" % sys.argv[0])
        sys.exit(2)
    
    t0=clock()
    fcn(x)
    t1=clock()
    print "%s took %9.6f seconds" % (fn,t1-t0)

if __name__ == "__main__":
    main()
_______________________________________________________________