Program Zero: MCM y MCD – El Algoritmo de Euclides

MCM y MCD – El Algoritmo de Euclides

14:24 • Anotaciones, Matemáticas • 0 comentarios

El algoritmo de Euclides sirve para obtener el máximo común divisor de dos números enteros positivos. Y con el resultado se podrá hallar el mínimo común múltiplo (M.C.M.).

Máximo Común Divisor

El máximo común divisor de dos números enteros positivos a y b es otro número entero positivo c tal que si dividimos a/c y b/c, los restos de las divisiones son 0, y además no existe otro número mayor que c que tenga esta caracterísitica. Como nos decían en el "cole", el máximo común dívisor (mcd) de dos enteros a y b es el mayor entero c que divide exactamente a a y b.
Aunque en el colegio nos enseñan a encontrar el mcd a partir de la descomposición en factores primos de a y b, esa no es una buena forma de obtener el mcd computacionalmente, ya que el algoritmo para descomponer en factores primos es muy costoso, en términos de computación. El algoritmo de Euclides es bastante más eficiente para obtener el mcd, aunque normalmente sorprende un poco cuando tenemos contacto con él por primera vez.
El algoritmo de Euclides es el siguiente.
Algoritmo de EuclidesSiendo a y b dos enteros positivos tales que a>b, comenzamos dividiendo a/b, con lo que obtendremos un resto r₁ y un cociente q₁. Hacemos la operación q₁=a/b, utilizando la división entera, sin decimales.... pero realmente no sólo nos interesa el resultado o cociente de la división, sino que nos interesa también el resto, así que la operación la vamos a reescribir de otra forma.
Es importante que llamemos "a" al mayor de los dos números. Debemos dividir a entre b y obtener un cociente (al que llamaremos q₁) y un resto (al que llamaremos r₁).

a=q₁·b+r₁

Los lenguajes de programación suelen tener un operador para efectuar la división entera (con lo que obtendremos q₁. Por ejemplo, en C#: "q1=a/b;"), y otro para obtener el resto o módulo de la división (con lo que obtendremos r₁. Por ejemplo, en C#: "r1=a%b;").
A partir de esa primera división, es necesario repetir un proceso:

dividir el dividendo del paso anterior entre el resto del paso anterior
despreciar el cociente
si el resto es 0, el mcd es el divisor de esta operacion, es decir, el último resto no nulo (recordemos que el divisor de esta operación fué el resto en la anterior.
Si el resto no es 0, ir al primer paso

Es un poco engorroso la primera vez, pero realmente es un algoritmo muy sencillo.
Siguiendo con el ejemplo, en la segunda iteración, dividiríamos b/r₁ obteniendo un resto r₂(hacemos la operación de división para obtener el cociente, al que llamamos q₂ y la de obtener el resto, al que llamamos r₂), de tal manera que se cumpla lo siguiente:

b=q₂·r₁+r₂

En la tercera iteración, dividimos r_1/r₂obteniendo un resto r3

r₁=q₃·r₂+r₃

Y se continúa así hasta obtener un resto 0. El último resto r_k distinto de cero es el mcd.

r_k-2=qk·r_k-1+r_k
r_k-1=q_k+1·r_k+0

r_k es el mcd(a,b)

Es decir, empezamos dividiendo un número entre otro (obteniendo el resto también, no sólo el cociente), y a partir de ahí, seguimos dividiendo el número más pequeño entre el resto que nos ha salido... y continuamos dividiendo por el resto anterior una vez y otra hasta que en ese proceso repetitivo obtengamos un resto que sea 0. ¡Ya lo tenemos!. El mcd es es resto anterior (que no es cero).
Como comentábamos al principio, es muy sencillo implementarlo iterativamente. Basta tener en cuenta que en cada vuelta del bucle, y siempre a partir de la segunda iteración hay que hacer que el divisor sea el resto de la iteración anterior y el dividendo sea el divisor de la iteración anterior.
Observa este código en C#.
En él vamos a utilizar dos variables enteras i1 e i2, que inicialmente van a contener los valores de los dos enteros a y b que se pasen como parámetros, de tal manera que i1 tendrá al mayor de los dos, e i2 al más pequeño... y a partir de ahí nos metemos en un bucle. La dinámica es siempre la misma: obtenemos el resto de la división, y si no es 0, debemos hacer otra repetición. Pero antes de la siguiente repetición, desplazamos los valores: lo que contenía i1 ya no nos sirve. Metemos en i1 lo que tiene i2, y en i2 el resto que hemos obtenido....

static int EuclidesMCD(int a, int b) {
int iaux; //auxiliar
   a = Math.Abs(a); //tomamos valor absoluto
   b = Math.Abs(b);
int i1=Math.Max(a,b); //i1 = el más grande
   int i2=Math.Min(a,b); //i2 = el más pequeño
   do
{
iaux = i2;  //guardar divisor
      i2 = i1 % i2; //resto pasa a divisor
      i1 = iaux;  //divisor pasa a dividendo
   } while (i2 != 0);
return i1; //ultimo resto no nulo
}

Al principio cuesta un poco de coger... te recomiendo hacer una traza mentalmente (o mejor, ayudándote de papel).

Te darás cuenta de cómo se van "desplazando los valores" a medida que vamos dividiendo hasta obtener el resto 0... aunque, realmente... no estamos utilizando los cocientes, sino sólo los restos ;-)

Aunque en la introducción hemos mencionado la división ("/"), realmente no es del todo cierto... sólo queremos los restos, no el cociente...(operador módulo o resto: "%" en C#). Hemos introducido esta pequeña mentira en la explicación (pero no en el código) porque cuando dividimos "a mano", realmente en la misma operación de división obtenemos dos resultados a la vez: por un lado el cociente y por otro, el resto. Sin embargo, los lenguajes de programación hacen cada una de esas cosas por separado: pueden obtener un cociente sin necesidad de obtener un resto y al revés, obtener un resto sin necesidad de dividir... así que en nuestro algoritmo no dividimos realmente: sólo obtenemos el resto. Si lo hiciéramos "a mano", tendríamos que dividir, con lo que obtendríamos el cociente y el resto simultáneamente, pero despreciaríamos el cociente y nos quedaríamos sólo con el resto.

Mínimo Común Múltiplo.

Muy relacionado con el máximo común divisor está el mínimo común múltiplo (mcm).

El mcm de dos enteros positivos a y b es un valor c entero y positivo tal que al dividir c/a y c/b el resto es 0, y además no existe otro número menor que c que cumpla esta condición.

Hay una relación muy sencilla entre mcm y mcd. Es ésta:

mcm(a,b)=(a·b)/mcd(a,b)

Así pues, también podemos obtener el mcm mediante el algoritmo de Euclides.

static int EuclidesMCM(int a, int b)
{
return (a / EuclidesMCD(a, b)) * b;
}

NOTA: Observa que primero se divide a entre el mcd, en lugar de multiplicar a*b. Esto se hace para evitar un posible desbordamiento al multiplicar a*b.

EN RESUMEN

En general, los algoritmos 1 y 2 no son muy apropiados para implementarse directamente en un lenguaje de programación, especialmente porque consumen mucha memoria. Si no se necesitan los valores intermedios, y sólo se desea calcular el máximo común divisor de dos números enteros, conviene usar estas variantes:

Algoritmo de Euclides tradicional implementado de manera recurrente

Función mcd(a,b):

Si b = 0 entonces:

El resultado es a

En otro caso:

El resultado es mcd(b,amod b)

Algoritmo de Euclides tradicional implementado de manera iterativa

Función mcd(a,b):

Mientras $b\ne0$ haga lo siguiente:

$(a,b)\gets(b,a\bmod b)$

El resultado es a

Algoritmo de Euclides extendido implementado de manera recurrente

Función Euclides(a,b):

Si b = 0 entonces:

El resultado es (a,1,0)

En otro caso:

$(d,s,t)\gets{\it Euclides}(b,a\bmod b)$

El resultado es $(d,t,s-(a\div b) t)$

Algoritmo de Euclides extendido implementado de manera iterativa

Función Euclides(a,b):

$(s,t,s^\prime,t^\prime)\gets(1,0,0,1)$

Mientras $b\ne0$ haga lo siguiente:

Divida a entre b para obtener un cociente q y un residuo r

$(a,s,t,b,s^\prime,t^\prime)\gets(b,s^\prime,t^\prime,r,s-s^\prime q,t-t^\prime q)$

El resultado es (a,s,t)

Algoritmo de Euclides extendido implementado de manera iterativa con matrices

Función Euclides(a,b):

$Q\gets\begin{pmatrix}1&0\\0&1\end{pmatrix}$

Mientras $b\ne0$ haga lo siguiente:

Divida a entre b para obtener un cociente q y un residuo r

$Q\gets\begin{pmatrix}0&1\\1&-q\end{pmatrix}\times Q$

$(a,b)\gets(b,r)$

El resultado es (a,Q₁₁,Q₁₂)

Acerca de la notación empleada:

$x\gets y$ significa "asigne a la variable x el valor actual de y". En lenguajes como C, Java, C#, Python y Visual Basic esto significa simplemente x = y. En otros lenguajes como Pascal se traduce en a := b, en Maxima es a : b, en R, S y Ocaml es x <- y, e inclusive se utiliza la flecha x ← y como el caso de APL.
$(x,y,z)\gets(a,b,c)$ significa que primero se evalúan los valores a,b,c y luego se asigna $x\gets a,y\gets b,z\gets c$ , etc. En lenguajes como Python, Ruby o Maxima esta instrucción tiene una estructura muy similar, como por ejemplo en Python: (x,y,z) = (a,b,c). En otros lenguajes es necesario el uso de variables auxiliares, como por ejemplo en lenguaje C: aux1 = b; aux2 = c; x = a; y = aux1; z = aux2;.
$a\div b$ significa "el cociente de dividir a entre b". A esta operación se le conoce también como la división truncada porque trunca la parte fraccionaria del número. En muchos lenguajes de programación esto se implementa simplemente como a/b. Otras maneras son a\b (Visual Basic) , a div b (Pascal) o bien a//b (Python 3).
amod b significa "el residuo de dividir a entre b". A esta operación se le conoce simplemente como módulo. En muchos lenguajes de programación se implementa como a % b, mientras que en otros es a mod b (Visual Basic o Pascal) o bien a rem b (Ada).