GCD in standard library?
Blake Garretson
blakeg at metalink.net
Wed Mar 12 21:50:39 EST 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