El Algoritmo de Euclides

En la entrada enterior vimos un sencillo algoritmo para el cálculo del máximo común divisor de dos números enteros. En esta ocasión vamos a ver el Algoritmo de Euclides, que es una manera fácil, elegante, y rápida de calcular el máximo común divisor. El algoritmo de Euclides se basa en la siguiente propiedad:

Si a y b son dos números enteros cualesquiera, entonces MCD(a, b) = MCD(a-b, b).

Podríamos hacer unos cuantos ejemplos a mano (¡ánimo, hágalo!) para convencernos a nosotros mismos de que esta propiedad es cierta, y aquellos lectores que sean más hábiles con las matemáticas, podrían incluso intentar dar una demostración formal. Pero en realidad no hace falta complicarse la vida tanto. Sólo tenemos que pensar un poco qué es lo que realmente significa esta propiedad para darnos cuenta de que la idea es trivial.

Imaginemos que tenemos dos barras de acero de longitudes a y b respectivamente, y que queremos medirlas utilizando para ello una pequeña regla de madera. Si la regla de madera nos da un número entero de medidas en una de las barras es porque la regla es un divisor de dicha barra. Si después de medir nos sobra un poquito de barra, es porque la regla no es un divisor. De entre todas las reglas que miden a ambas barras a y b nos quedamos con la que tenga una longitud mayor, que será precisamente el máximo común divisor (véase la siguiente figura).

Ahora bien, si encontramos una regla que divide a la barra b, para ver si también divide a la barra a bastaría con comprobar que divide a aquella parte de la barra a que sobresale de la barra b (es decir b-a), ya que la otra parte ya ha sido medida. Si ahora cortamos lo que sobresale de la barra a, podríamos repetir de nuevo el proceso pero utizando la barra cortada b-a y la barra b. Se trataría de resolver el mismo problema pero invertidos los papeles de las barras.

Basándonos en esta idea, podemos escribir el siguiente Algoritmo de Euclides: la idea consiste en ir cortando alternativamente de la barra más larga la parte que sobresale de la barra más pequeña, hasta que ambas barras tengan exactamente la misma logitud, que será el máximo común divisor. El algoritmo puede ser mejorado todavía un poco más, utilizando para ello la función módulo que hemos en una entrada anterior, pero esta mejora se la dejo propuesta al lector como ejercicio.

A diferencia del algoritmo anterior donde conocíamos a priori el número de iteraciones que teníamos que realizar sobre el bucle (desde 1 hasta min), en este caso no conocemos cuantas iteraciones serán necesarias antes de dar con el máximo común divisor, ya que depende de los cortes que realicemos, por eso utilizamos un bucle de tipo mientras. La condición es que mientras las barras tengan longitudes diferentes tenemos que seguir cortando, y en el momento que sean iguales paramos (nos salimos del bucle), porque ese es el máximo común divisor.

leer(a)
leer(b)
mientras a != b hacer
    si a < b entonces
        a := a - b
    sino
        b := b - a
    finsi
fin mientras
escribir(a)

La genalidad del algoritmo de Euclides quizás no sea tan geneial si la vemos desde un punto de vista histórico. Me explico. No es que quiera restarle mérito al que es, probablemente, el primer algoritmo de la historia. Pero en la época de Euclides los matemáticos dedicaban gran parte de su tiempo a estudiar las razones entre las cosas, sobre todo entre figuras geométricas (recordemos que la razón entre dos cosas es el número de veces que contiene la una a la otra). Así, el máximo común divisor era entendido en términos geométricos, como la razón máxima común a dos segmentos dados. En este contexto es más natural que surga este algoritmo. Hoy en día, las razones (en ambos sentidos de la palabra) ya no son tan importantes, somos más dados a la solución algebráica de los problemas, y en este contexto, la idea subyacente al alogritmo de Euclides nos resulta más complicada de entender.