Algoritmo de Euclides

De Wikipedia, la enciclopedia libre

El algoritmo de Euclides es un método eficaz para calcular el máximo común divisor (mcd) entre dos números enteros. Consiste en varias divisiones euclidianas sucesivas. En la primera división, se toma como dividendo el mayor de los números y como divisor el otro (se ahorra así un paso). Luego, el divisor y el resto sirven respectivamente de dividendo y divisor de la siguiente división. El proceso termina cuando se obtiene un resto nulo. El mcd es entonces el penúltimo resto del algoritmo.

[editar] Definición

Formalmente, si se llama <math>a</math>, <math>b</math> a los enteros iniciales y <math>r_1,r_2,\dots,r_{n-1},r_n</math> a los restos sucesivos obtenidos mediante el algoritmo de la división (con <math>r_n=0</math>), entonces:

<math>\mathrm{mcd}(a,b) = \mathrm{mcd}(b,r_1)\,</math>, con <math>r_1 = a - (b\times q)</math> (<math>q</math> es el cociente de <math>a</math> por <math>b</math>)

En efecto, los divisores comunes de <math>a</math> y <math>b</math> son los de <math>a-b\times q\,</math> y <math>b\,</math>:

porque si <math>q</math> divide <math>a</math> y <math>b</math>, obviamente divide <math>a-(b\times q)</math> que es una combinación lineal de ambos, y recíprocamente <math>a = (a-b\times q) + b\times q</math> es una combinación lineal de <math>b</math> y <math>a - b\times q</math>.

Luego el menor de los divisores comunes es el mismo, y repitiendo la operación se sigue que

<math>\mathrm{mcd}(b,r_1)=\mathrm{mcd}(r_1,r_2)=\mathrm{mcd}(r_2,r_3)=\dots=\mathrm{mcd}(r_{n-1},r_n)=\mathrm{mcd}(r_{n-1},0) =r_{n-1}</math>

A partir de lo anterior se deduce la función recursiva

<math>\mathrm{mcd}:\mathbb N\times\mathbb N\rightarrow\mathbb N</math>

<math>\mathrm{mcd}(a,b)= \begin{cases} a & \mbox{si } b = 0\\ \mathrm{mcd}(b, a \,\bmod\, b) & \mbox{si } b > 0\\ \end{cases}</math>

Esta función da como resultado 0 si <math>a=0</math> y <math>b=0</math>, pero el máximo divisor de cero no existe. A partir de esta función se puede describir el algoritmo como sigue:

"Para calcular el máximo común divisor de dos números naturales <math>a</math> y <math>b</math>, verifique si <math>b</math> es cero; si es así, entonces <math>a</math> es el máximo común divisor de <math>a</math> y <math>b</math>. Si no, repita el proceso usando (respectivamente) <math>b</math>, y el resto de dividir <math>a</math> entre <math>b</math> (denotado como <math>a \,\bmod\, b</math>)."

Este algoritmo puede ser usado en cualquier contexto donde la división con residuo sea posible. Esto incluye al anillo de polinomios sobre un campo así como el anillo de de los enteros de Gauss, y en general, en cualquier dominio euclídeo.

[editar] Versión recursiva

Utilizando recursión, se puede expresar el algoritmo de manera natural:

función <math>\mathrm{mcd}(a,b)\,</math>

si <math>b=0\,</math>

devolver <math>a\,</math>

si no

devolver <math>\mathrm{mcd}(b, a \,\bmod\, b)</math>

[editar] Versión iterativa

La versión iterativa es más eficiente para la implementación en una computadora:

función <math>\mathrm{mcd}(a,b)\,</math>

mientras <math>a>0\,</math> hacer

<math>t\leftarrow a\,</math>

<math>a\leftarrow b\,\bmod\,a</math>

<math>b\leftarrow t\,</math>

devolver <math>b\,</math>

[editar] Versión original

El algoritmo original descrito por Euclides trataba el problema de manera geométrica; usaba la substracción repetida en lugar del residuo de la división. Esta versión es significativamente menos eficiente:

función <math>\mathrm{mcd}(a,b)\,</math>

mientras <math>b>0\,</math> hacer

si <math>a>b\,</math>

<math>a\leftarrow a-b</math>

si no

<math>b\leftarrow b-a</math>

devolver <math>a\,</math>

[editar] Ejemplos

Se busca el máximo común divisor de <math>a= 1498</math> y <math>b= 980</math>, números escogidos al azar:

<math>\begin{array}{rcl}

1498&=&980\times1+518\\ 980&=&518\times1+462\\ 518&=&462\times1+56\\ 462&=&56\times8+14\\ 56&=&14\times4+0 \end{array}</math>

entonces <math>\mathrm{mcd}(1498,980) = 14</math> (el último resto no nulo). Como segundo ejemplo, se tiene números de tamaños parecidos a los anteriores, <math>a = 1597</math> y <math>b = 987</math>:

<math>\begin{array}{rcl}

1597&=&987\times1+610\\ 987&=&610\times1+377\\ 610&=&377\times1+233\\ 377&=&233\times1+144\\ 233&=&144\times1+89\\ 144&=&89\times1+55\\ 89&=&55\times1+34\\ 55&=&34\times1+21\\ 34&=&21\times1+13\\ 21&=&13\times1+8\\ 13&=&8\times1+5\\ 8&=&5\times1+3\\ 5&=&3\times1+2\\ 3&=&2\times1+1\\ 2&=&1\times2+0 \end{array}</math> entonces <math>\mathrm{mcd}(1597,987) = 1</math> (el último resto no nulo).

El segundo ejemplo es sustancialmente más largo que el primero, y esto se debe a que todos los cocientes valen 1. Aquí <math>a</math> y <math>b</math> no fueron escogidos al azar: son dos términos consecutivos de la sucesión de Fibonacci; es el peor de los casos para este algoritmo.

[editar] Implementación

En lenguaje C (versión recursiva):

unsigned int mcd(unsigned int a, unsigned int b){
    return (b == 0)? a : mcd(b, a % b);
}

En lenguaje Logo (versión recursiva):

para mcd :a :b
 sisino :b = 0 [
  devuelve :a
 ] [
  devuelve mcd :b resto :a :b
 ]
fin

En lenguaje C (versión iterativa):

unsigned int mcd(unsigned int a, unsigned int b){
    unsigned int t;
    while (a > 0){
        t = a;
        a = b % a;
        b = t;
    }
    return b;
}

En lenguaje Logo (versión iterativa):

para mcd :a :b
 mientras [:a > 0] [
  haz "t :a
  haz "a resto :b :a
  haz "b :t
 ]
 devuelve :b
fin

En lenguaje Visual Basic 8 (versión iterativa):

Public Function mcd(a As UInteger, b As UInteger) As UInteger
    Dim t As UInteger
    While a > 0
        t = a
        a = b Mod a
        b = t
    End While
    Return b
End Function

En lenguaje Haskell (versión recursiva):

mcd::Int->Int->Int
mcd a 0 = a
mcd a b = mcd b (mod a b)

[editar] Complejidad del algoritmo

Imagen:Euclidean algorithm running time X Y.png

Si se considera que las operaciones aritméticas son operaciones elementales, sin pérdida de generalidad se supone que <math>b\geq a</math>, entonces la complejidad del algoritmo está en el orden de <math>O(\log n)\,</math> donde <math>n = b\,</math>. Para ver esto, primero se considera que para cualesquiera dos enteros <math>a,b</math> tales que <math>b\geq a</math>, siempre se cumple

Esto es porque:

Si <math>a>\frac{b}{2}</math>, entonces <math>1\leq\frac{b}{a}<2</math>, por lo tanto <math>b\div a = 1</math>, lo cual implica que <math>b\,\bmod\,a=b-a\times(b\div a)=b-a<b-\frac{b}{2}=\frac{b}{2}</math>
Si <math>a\leq\frac{b}{2}</math> entonces <math>b\,\bmod\,a<a\leq \frac{b}{2}</math>

Como se considera que las operaciones aritméticas son operaciones elementales, entonces la complejidad del algoritmo es del orden exacto del número de veces que se usa el ciclo mientras de la versión iterativa. Considérese a <math>a</math> y <math>b</math> después de pasar dos veces por el ciclo suponiendo que el algoritmo no se detiene antes. Sean <math>a_0</math> y <math>b_0</math> los valores de entrada al algoritmo. Después de la primera iteración <math>a=b_0\,\bmod\,a_0</math> y seguidamente, en la segunda iteración <math>b</math> toma ese valor.

De lo anterior, <math>b</math> se ha vuelto más pequeño que <math>\frac{b_0}{2}</math>. Es decir que <math>b</math> se dividido al menos por dos después de dos pasadas por el ciclo. Además sigue siendo cierto que <math>b\geq a</math> y por lo tanto se puede aplicar el mismo razonamiento. La conclusión es que a lo mucho, se pasará por el ciclo aproximadamente <math>2\log b\,</math> veces.

Por lo tanto, la complejidad de <math>\mathrm{mcd}(m,n)\,</math> con <math>n\geq m</math> está en orden de <math>O(\log n)\,</math>.

Sin embargo, si se considera que las operaciones aritméticas no son operaciones elementales, entonces el número de operaciones está acotado por <math>O(n^2)</math> - inferior a <math>An^2</math> con A una constante - donde n es el número de cifras del más pequeño entre a y b.

[editar] Fracciones continuas

Las divisiones euclidianas del algoritmo son idénticas a las que permiten hallar la expresión en fracción continua de <math>\frac a b</math>

En efecto, <math> a = bq_1 + r_1</math> se puede escribir <math>\frac a b = q_1 + \frac {r_1} b</math>. Del mismo modo, <math> b = r_1 q_2 + r_2 \,</math> se escribe <math>\frac b {r_1} = q_2 + \frac {r_2} {r_1}</math> y si lo inyectamos en la igualdad anterior obtenemos <math> \frac a b = q_1 + \frac 1 {q_2 + \frac {r_2} {r_1}}</math> y el proceso se repite hasta utilizar todas las divisiones euclidianas, y da lugar a fracciones con muchos "pisos". Los dos ejemplos numéricos del párrafo anterior dan:

Este proceso funciona también con valores irracionales de a/b (con a y b reales). en tal caso, el algoritmo no se para, lo que da una fracción continua infinita. Son de especial interés estas fracciones, como en los casos de π y e.

Volviendo al caso <math>a</math> y <math>b</math> enteros, el algoritmo de Euclides permite encontrar los coeficientes enteros <math>u</math> y <math>v</math> de la identidad de Bézout <math>au+bv=\mathrm{mcd}(a, b)</math> de fundamental importancia en la aritmética.

[editar] Generalización a los polinomios

Este algoritmo sólo precisa de la división euclidiana, y por consiguiente se extiende a todos los dominios donde existe tal división: es el caso de las álgebras de polinomios, como <math>\mathbb Q[x]</math> o <math>\mathbb R[x]</math>, (polinomios con coeficientes racionales o reales respectivamente). Obviamente, los cálculos se vuelven mucho más largos. Un ejemplo no demasiado complicado, pero tampoco trivial:

Sea <math>P=x^3-6x^2-63x+392\quad</math> un polinomio que se cree que tiene una raíz doble.

como resolver una ecuación de tercer grado no es evidente, para hallar la raíz múltiple empleamos la propiedad que dice las raíces múltiples son las en común entre el polinomio y su polinomio derivado.

Para simplificar las divisiones, nos permitimos multiplicarlos por factores constantes no nulos, en fin de cuentas el <math>\mathrm{mcd}</math> de dos polinomios está definido módulo un factor multiplicativo, así que esta manipulación no altera el resultado.

El polinomio derivado de <math>P</math> es <math> \frac{\mathrm{d}}{\mathrm{d} x}P=3x^2-12x-63\,</math> que se puede simplificar por 3, según lo dicho anteriormente.

Tomemos entonces <math>Q=\frac 1 3 \frac{\mathrm{d}}{\mathrm{d} x}P=x^2-4x-21</math> y efectuemos el algoritmo con <math>P</math> y <math>Q</math>.

<math>P=(x-2)Q-50x+350\,</math>. El resto se factoriza en <math>-50(x - 7)\,</math>: tomemos entonces <math>R=x-7\,</math>

[editar] Referencias

Brassard, Gilles; Bratley, Paul: "Análisis de algoritmos", en Fundamentos de Algoritmia.- Madrid: PRENTICE HALL, 1997.- ISBN 84-89660-00-X

El contenido de este artículo incorpora material de una entrada de la Enciclopedia Libre Universal, publicada en castellano bajo la licencia GFDL.

ar:خوارزمية إقليدس

bg:Алгоритъм на Евклид ca:Algorisme d'Euclides cs:Euklidův algoritmus de:Euklidischer Algorithmus en:Euclidean algorithm fi:Eukleideen algoritmi fr:Algorithme d'Euclide hu:Euklidészi algoritmus id:Algoritma Euklidean it:Algoritmo di Euclide ja:ユークリッドの互除法 ko:유클리드 호제법 lt:Euklido algoritmas lv:Eiklīda algoritms nl:Algoritme van Euclides no:Euklids algoritme pl:Algorytm Euklidesa pt:Algoritmo de Euclides ru:Алгоритм Евклида sl:Evklidov algoritem sr:Еуклидов алгоритам sv:Euklides algoritm vi:Giải thuật Euclid zh:輾轉相除法