B.3. Algoritmo de Euclides Python

En el ejemplo anterior, computamos la suma de 5=6 + 5=6 y obtuvimos 60=36.

Es correcto, pero no es la mejor forma de representar la respuesta. Para reducir la fracción a su expresión mas simple, hemos de dividir el numerador y el denominador por el máximo común divisor (MCD) de ambos, que es 12.

El resultado sería 5=3.

En general, siempre que creamos un nuevo objeto Fracción, deber³amos reducirlo dividiendo el numerador y el denominador por el MCD de ambos. Si la fracción ya esta reducida, el MCD es 1.
Euclides de Alejandr³a (aprox. 325{265 a. C.) presento un algoritmo para encontrar el MCD de dos números enfermos m y n:

Si n divide a m sin resto, entonces n es el MCD. De lo contrario, el MCD es el MCD de n y el resto de dividir m entre n. Esta definición recursiva puede expresarse concisamente como una función:

   1: def mcd (m, n):

   2:     if m % n == 0:

   3:         return n

   4:     else:

   5:         return mcd(n, m%n)

En la primera l³nea del cuerpo, usamos el operador de modulo para comprobar la divisibilidad. En la ultima l³nea, lo usamos para calcular el resto de la división.

Dado que todas las operaciones que hemos escrito creaban un nuevo objeto Fracción para devolver el resultado, podemos reducir todos los resultados modificando el método de inicialización.

   1: class Fracción:

   2:     def __init__(self, numerador, denominador=1):

   3:         m = mcd (numerador, denominador)

   4:         self.numerador = numerador / m

   5:         self.denominador = denominador / m

Ahora siempre que creemos una Fracción quedara reducida a su forma canoníca:

>;>> Fracción(100,-36)

-25/9

Una característica estupenda de mcd es que si la fracción es negativa, el signo menos siempre se trasladara al numerador.