GCD in standard library?
Jp Calderone
exarkun at intarweb.us
Wed Mar 12 22:44:35 EST 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