Decimals -> Fraction strings, my solution

David C. Ullrich ullrich at
Thu May 18 20:09:50 CEST 2000

On Wed, 17 May 2000 20:17:28 +0200, Peter Schneider-Kamp
<petersc at> wrote:

>Dave Hansen wrote:
>> A very nice implementation of Euclid's algorithm.  I would suggest a
>> couple small changes to make it more robust.  Shouldn't hurt the
>> efficiency significantly...
>> >
>> >def gcd(a, b):
>>      a = abs(a)
>>      b = abs(b)
>Probably a good idea given Python's implementation of modulo.

	Why does Python's implementation of modulo make
this a good idea? Is there a problem with the "original"

def gcd(a, b):
    while a:
        a, b = b % a, a
    return b

that I've just never found?

	This is identical to a routine I've used for 
quite a while with no problem. (Of course gcd(a,b)
sometimes comes out negative - if that's the problem
what's the problem with that?)

	The reason the counter-quibble seems worth 
mentioning is that the abs makes it much less generic: 
Without the abs you can use the function for any 
objects with a __mod__ method (assuming that a has 
to eventually become false for some reason). For 
example you can use it to find the gcd of two 
polynomials a and b, if you give your polynomials 
an appropriate __mod__. (I don't think there's any
such thing as an appropriate __abs__ for polynomials...)


>>      if b > a:
>>          a, b = b, a
>This is IMHO absolutely unneccessary and just bloats the code.
>Why do you want to check when in the case that b is greater
>than a the first step just reverses the arguments? So in case
>b is greater than a you trade in a division against a
>comparison and more code. In the case that a is already
>greater than b you gain nothing and pay a comparision and
>more code.
>Ha det bra
>Peter Schneider-Kamp          ++47-7388-7331
>Herman Krags veg 51-11        mailto:peter at
>N-7050 Trondheim    

More information about the Python-list mailing list