Antoon Pardon wrote:
> On 2005-08-08, Bengt Richter <[EMAIL PROTECTED]> wrote:
>
>>On 7 Aug 2005 17:31:02 -0700, "Jordan Rastrick" <[EMAIL PROTECTED]> wrote:
>>
>>
>>>Good point. I suppose I'd only ever seen it implemented with the if
>>>test, but you're right, the plain while loop should work fine. Silly
>>>me.
>>>
>>>def gcd(a,b):
>>> while b != 0:
>>> a, b = b, a%b
>>> return a
>>>
>>>Even nicer.
>>>
>>
>>what is the convention for handling signed arguments? E.g.,
>
>
> As far as I understand the convention is it doesn't make
> sense to talk about a gcd if not all numbers are positive.
>
> I would be very interested if someone knows what the gcd
> of 3 and -3 should/would be.
Within the integers, common definitions of gcd don't distinguish
positive from negative numbers, so if 3 is a gcd of x and y then
-3 is also a gcd. That's using a definition of gcd as something
like "g is a gcd of x and y if g|x and g|y and, for any h such
that h|x and h|y, h|g", i.e., a gcd is a common divisor and is
divisible by any other common divisor. The word "greatest" in
this context is wrt the partial ordering imposed by | ("divides").
(Note that "|" in the above is the mathematical use as a|b if
there is an (integral) c such that ac=b, i.e., b is divisible
by a. These definitions generalize to rings other than the
integers, without requiring a meaningful < comparison on the
ring.)
All of that said, it would be reasonable when working in the
integers to always report the positive value as the gcd, to
make gcd a simpler function. For some applications, it won't
matter if you choose positive or negative, so going positive
does no harm, and others might be simplified by assuming gcd>0.
-- James
--
http://mail.python.org/mailman/listinfo/python-list
