GCD in standard library?

Jp Calderone exarkun at intarweb.us
Thu Mar 13 04:44:35 CET 2003


On Wed, Mar 12, 2003 at 08:08:18PM -0700, Steven Taschuk wrote:
> Quoth Blake Garretson:
> > [...] I'm just guessing it is very common
> > for people to have to add this to their programs:
> > 
> > def gcd(x,y):
> >   if x % y == 0: return y
> >   else: return gcd(y,x%y)
> 
> I for one haven't needed this in Python yet, but if I did I'd do
> it this way:
> 	def gcd(a, b):
> 		while b:
> 			a, b = b, a % b
> 		return abs(a)
> which (1) avoids the unnecessary recursion, (2) gives the right
> answer for zero operands, and (3) gives a predictable and
> defensible, if not obviously right, answer for negative operands.

  FWIW, tuple packing/unpacking is wasting time in that loop.  I'd do it
with a temporary variable, even though it looks nicer without one :)

  Jp

-- 
 up 9 days, 19:59, 9 users, load average: 0.00, 0.02, 0.00





More information about the Python-list mailing list