# Decimals -> Fraction strings, my solution

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

On Wed, 17 May 2000 20:17:28 +0200, Peter Schneider-Kamp
<petersc at stud.ntnu.no> 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...)

DU

>
>>      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
>--
>Peter Schneider-Kamp          ++47-7388-7331
>Herman Krags veg 51-11        mailto:peter at schneider-kamp.de
>N-7050 Trondheim              http://schneider-kamp.de
>