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.
No hay comentarios:
Publicar un comentario