GCD in standard library?

Blake Garretson blakeg at metalink.net
Thu Mar 13 03:50:39 CET 2003


"Erik Max Francis" wrote...
> > def gcd(x,y):
> >   if x % y == 0: return y
> >   else: return gcd(y,x%y)
>
> I would hope you'd use the iterative form.  Function calls are
> expensive, and can't recurse to arbitrary depths.

Right.  Maybe I'm doing something wrong, but the recursive version appears
faster.  Here's my little test:

### gcd.py  ###
def gcd_iter(a, b):
    while a != 0:
        a, b = b%a, a
    return b

def gcd_rec(a,b):
    r = a%b
    if r == 0: return b
    else: return gcd_rec(b,r)

import profile
x, y = 4502, 950
profile.run('print gcd_iter(x, y)')
profile.run('print gcd_rec(x, y)')
### END FILE ###

This results in:
###
2
         3 function calls in 0.048 CPU seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.003    0.003    0.003    0.003 <string>:1(?)
        1    0.000    0.000    0.000    0.000 gcd.py:1(gcd_iter)
        1    0.045    0.045    0.048    0.048 profile:0(print gcd_iter(x,
y))
        0    0.000             0.000          profile:0(profiler)


2
         10 function calls (3 primitive calls) in 0.003 CPU seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.002    0.002    0.002    0.002 <string>:1(?)
      8/1    0.000    0.000    0.000    0.000 gcd.py:6(gcd_rec)
        1    0.001    0.001    0.003    0.003 profile:0(print gcd_rec(x, y))
        0    0.000             0.000          profile:0(profiler)
###

So I'm thinking the recursive version is faster?  Is that right?

Blake G.






More information about the Python-list mailing list