Discusión:Algoritmo de Euclides

Para los que quieran las implementaciones en mil y un lenguajes

Por alguna razón la gente que colaboramos en esta enciclopedia, cuando vemos un algoritmo, nos obsesionamos por colocar implementaciones en lenguaje C, Java, PHP, Pascal, C++, Visual Basic, Python, Fortran, Haskell, LUA, Lexico, PL/I, LISP, C# y qué sé yo tantos lenguajes. He optado por la postura de que es preferible usar Pseudocódigo y que las implementaciones no tienen nada de enciclopédico (después de todo Wikipedia no es un libro de programación, en todo caso hay artículos del tema). Por esta razón, antes de que se arme un alboroto. Indico algunas implementaciones en algunos cuantos lenguajes:

Python

En Python (versión tradicional recursiva)

def mcd(a,b):
    if b == 0:
        return a
    else:
        return mcd(b, a % b)

En Python (versión tradicional iterativa)

def mcd(a, b):
    while b != 0:
        (a, b) = (b, a % b)
    return a

En Python 3 (versión extendida recursiva)

def Euclides(a, b):
    if b == 0:
        return (a,1,0)
    else:
        (d, s, t) = Euclides(b, a % b)
        return (d, t, s - (a//b)*t)

En Python (versión extendida iterativa)

def Euclides(a, b):
    (s, t, s1, t1) = (1, 0, 0, 1)
    while b != 0:
        (q, r) = divmod(a, b)
        (a, s, t, b, s1, t1) = (b, s1, t1, r, s - s1*q, t - t1*q)
    return (a, s, t)

Visual Basic

En Visual Basic (versión tradicional recursiva)

Public Shared Function mcd(ByVal a As Integer, ByVal b As Integer) As Integer
	If b = 0 Then
		Return a
	Else
		Return mcd(b, a Mod b)
	End If
End Function

En Visual Basic (versión tradicional iterativa)

Public Shared Function mcd(ByVal a As Integer, ByVal b As Integer) As Integer
	Dim r As Integer
	While b <> 0
		r = a Mod b
		a = b
		b = r
	End While
	Return a
End Function

En Visual Basic (versión extendida recursiva)

Public Shared Function Euclides(ByVal a As Integer, ByVal b As Integer) As Integer()
	Dim r As Integer() = New Integer(2) {a, 1, 0}, r1 As Integer() = New Integer(2) {}
	If b <> 0 Then
		r1 = Euclides(b, a Mod b)
		r(0) = r1(0)
		r(1) = r1(2)
		r(2) = r1(1) - (a\b) * r1(2)
	End If
	Return r
End Function

C/C++

A continuación se muestra un pequeño código aplicado al lenguaje C sobre el propio Algoritmo de Euclides (1) tradicional, el cual ya se ha implementado previamente en pseudocódigo de varias maneras en el apartado anterior. El algoritmo es el siguiente:

int Euclides(int dividendo, int divisor){
    int resto;
    while(divisor!=0){                      //El objetivo del bucle es 
        resto=dividendo%divisor;            //hacer que el divisor siempre 
        dividendo=divisor;                  //divida al resto, y así,
        divisor=resto;                      //cuando este llegue a 0, 
    }                                       //el último divisor será el MCD
    return dividendo;                       //como indica el Algoritmo.
}

También se dispone el Algoritmo extendido de Euclides(2), en lenguaje C:

int EuclidesExtendido(int dividendo,int divisor){
    int s=1;
    int t=0;
    int s2=0;
    int t2=1;
    int coc;
    int resto;
    while(divisor!=0){                      //Se definen previamente las componentes extra de la ecuación
        resto=dividendo%divisor;            //MCD(a,b)=a(s)+b(t); s con 1 y t con 0, ya que es lo que resulta 
        coc=dividendo/divisor;              //al hacer las divisiones correspondientes con el 
        dividendo=divisor;                  //algoritmo tradicional de Euclides.
        s=s2;                               //A partir de este punto, se suceden estas variables de la forma: s2,t2;s3,t3...
        t=t2;                               //hasta llegar al punto de partida(inversión) multiplicando cada s' y t' por 
        divisor=resto;                      //coc(cociente) y sustiruir en la fórmula para calcular el MCD.
        s2=(s-s2)*coc;                      
        t2=(t-t2)*coc;
    }
    return dividendo;                       
}

Este último módulo sólo devuelve el MCD, aunque también podría devolver s y t pásandolos como parámetros de entrada/salida o de referencia en la cabecera del módulo.

Ambos códigos presentados en lenguaje lenguaje C son iterativos, por lo que no son la única manera de poder implementarlos.

También se pueden realizar de forma recursiva.

Algoritmo de Euclides tradicional(1) recursivo:

int EuclidesR(int dividendo, int divisor){   
	int resto;                                    //Se crea una variable resto de tipo entero que en cada llamada recursiva
	if(divisor!=0){                               //tomará el valor del antiguo divisor.   
		resto=dividendo%divisor;                  //Pasará lo mismo a su vez con el divisor, que tomará el del antiguo dividendo.
		dividendo=EuclidesR(divisor,resto);       //Como caso trivial, se establece que el divisor sea 0, con lo que se realizarán
	}                                             //llamadas recursivas hasta que ese divisor sea 0.  
	return dividendo;
}

Algoritmo extendido de Euclides(2) implementado de forma recursiva:

int EuclidesRExtendido(int dividendo, int divisor,int s,int t,int s2,int t2){
	int coc;                                                                   //De la misma forma que en el tradicional, se crea la
	int resto;                                                                 //variable resto, al igual que la variable coc
	if(divisor!=0){                                                            //(cociente). También s, t, s2 y t2 y coc se pasan
		resto=dividendo%divisor;                                               //como parámetros de entrada en forma de operaciones
		coc=dividendo/divisor;                                                 //en cada llamada recursiva. De esta forma, cuando
		dividendo=EuclidesRext(divisor,resto,s2,t2,(s-s2)*coc,(t-t2)*coc);     //el divisor sea 0, queda de resultado el último
	}                                                                          //dividendo del cálculo.
	return dividendo;
}

La ventaja más notable a la hora de implementar estos algoritmos, son las líneas de código que ocupan tanto los recursivos como los iterativos.

Aunque se trata de hacer los algoritmos lo más cortos posibles, también se trata de hacerlos lo más eficientes posibles.

A la hora de hacer el algoritmo iterativo, el bucle simplemente utiliza las variables creadas al principio del módulo. En cambio, cada vez que se hace una llamada recursiva al módulo, lo que estás haciendo es crear un nuevo párametro por cada variable que hayas creado, además de que, cuando ya ha realizado todos sus procesos hasta el caso trivial, ha de invertirse el proceso recursivo para llevarse a cabo el cálculo.

Maxima

En Maxima (usando multiplicacion de matrices)

Euclides(a,b) := block(
    [Q],
    Q : ident(2),
    while b # 0 do block(
        [q,r] : divide(a,b),
        Q : matrix([0,1],[1,-q]).Q,
        [a,b] : [b,r]
    ),
    return([a,Q[1,1],Q[1,2]])
)$

Ejemplo de uso en Maxima:

(%i2) Euclides(x^5 + 2*x^3 + x, x^4 - 1);

(%o2) $\left[-x^{2}-1,-{{x} \over {2}},{{x^{2}} \over {2}}+1\right]\,$

(%i3) ratsimp((x^5 + 2*x^3 + x)*(-x/2) + (x^4 - 1)*(x^2/2+1))

(%o3) $-x^{2}-1\,$

Posible solución al problema

Dado que las distintas implementaciones del problema podrían resultar de interés, pero en un artículo de Wikipedia tienen dudosa cabida, se podría añadir como comentas arriba la solución en pseudocódigo y un enlace a Wikilibros. Pero para hacer esto, habría que ver qué pseudocódigo se usa y también habría que crear un manual en Wikilibros sobre implementaciones, en el que cada capítulo/artículo estuviese dedicado a una función desarrollada en los diversos lenguajes de programación. Akhram (comentarios) 01:16 15 nov 2008 (UTC).

Hacer un wikilibro con todos los algoritmos, sus variantes y sus implementaciones me parece una labor monumental (EXTREMADAMENTE monumental). Hay muchísimos tipos de problemas. Solamente de la clase NP-completo se conocen más de 3000, cada uno con 5 o más algoritmos distintos. Ahora agregarle a eso los de las clases P, ZPP, Co-NP, NP-Difícil, TIEMPOEXP, ESPACIOEXP, etc., con muchos miles de problemas más, algunos con decenas de algoritmos y variantes. Ahora imagina que por cada variante se hace un código en C, C++, C#, Java, PHP, Ruby, Python, Perl, Fortran, Pascal, Visual Basic, LISP, Haskell, LUA, PL/I, Lexico, Delphi, Eifell, Ada, Maxima, R, S, sed, Matlab, SPARKS, etc. ¡Son millones de implementaciones! Pero lo que digo acerca de la manía por colocarlas en los artículos es cierto:

• El artículo algoritmo se supone que sólo debería tener una implementación para ilustrar qué cosa es una implementación, actualmente ya son cuatro y siguen aumentando (en la página de discusión se proponen todavía más).
• El artículo Sucesión de Fibonacci hace no mucho tiempo que lucía de esta manera con once implementaciones de sólo dos variantes y dos propuestas más en la página de discusión.
• Ordenamiento de burbuja ya tiene doce implementaciones de sólo dos variantes y la lista sigue aumentando. . . Francamente este ni siquiera me parece que esté redactado como un artículo de enciclopedia.
• Existen inclusive artículos como Implementación del algoritmo de Floyd en Java y Problema del cambio de palabra (programación dinámica en Java)

Por lo demás, creo que existen los artículos dedicados a Java, C, C++, etc. donde sí tienen cabida las implementaciones como ejemplo del uso correcto del lenguaje. En todo caso, es más factible crear en cada artículo dedicado a un lenguaje de programación, una breve sección donde quede indicado el operador de asignación, los operadores aritméticos y otros operadores de de cadenas listas o arreglos. --$k_{n}\,$ ■ 14:24 18 nov 2008 (UTC)

Pues sí, sería un trabajo arduo, pero no tanto como la creación de la Wikipedia XD. De vez en cuando surgen variantes del mismo problema: todo o nada. La propuesta de crear el wikilibro no significa que haya que empezarlo y terminarlo en un plazo de tiempo determinado, sino que conforme vayan apareciendo implementaciones «fuera de lugar», se envían al wikilibro en lugar de borrarlas. Si con el tiempo, el wikilibro se va tornando más y más pesado, pues ya se planteará si es necesario dividirlo en varios según el lenguaje o a saber qué criterio resulta más adecuado. Más que nada, mi idea es de no perder esa información, que a priori puede parecer trivial, pero a lo mejor hay algún usuario (o varios), que querrían ver una implementación determinada, ¿quién sabe lo que un usuario cualquiera puede necesitar? Eso sí, tendríamos la mejora de que los artículos de wikipedia no parecerían manuales de programación y ganarían en legibilidad. Akhram (comentarios) 12:55 21 nov 2008 (UTC).

Propuesta intermedia: podemos mover las implementaciones a un anexo mientras tanto (recordemos que los anexos deben complementar los artículos), dejando una o dos particularmente relevantes en el texto. Si una implementación es especialmente interesante (no por el lenguaje en que está sino por los conceptos mismos, entonces quizás podría considerarse hacer una artículo sobre esa implementación (explicando porqué esa es relevante). -- m:drini 17:13 22 nov 2008 (UTC)

Historia

Una sección que estaba muy escasa, es la relativa al contexto histórico (cómo ha evolucionado en el tiempo). Dado que es quizá uno de los algoritmos más trascendentes (tanto por sus aplicaciones como su antigüedad, me parece importante expander la sección sobre la sección griega. Me he tomado también el trabajo de transcribir la proposición VII-2 tal cual aparece en Los Elementos, debido a su importancia y relevancia histórica (tanto del algoritmo como de la obra los Elementos). Además ilustra el lenguaje geométrico y rebuscado que usaron los griegos, el cual contrastará con las versiones compactas modernas permitiendo una mayor apreciación de su elegancia. -- m:drini 03:51 23 nov 2008 (UTC)

Por cierto, el Algoritmo de Euclides permite una demostración geométrica de la irracionalidad de ${\sqrt {2}}$ con una esencia completamente diferente a la basada en la divisibilidad por 2, es decir, sin hacer uso de factores primos. La prueba es por contradicción (aplicando el algoritmo de Euclides a la hipotenusa y el cateto de un triángulo rectángulo de lado uno, se demuestra que el proceso no puede acabar y por tanto los segmentos son inconmensurables. En los días posteriores haré los diagramas y añadiré la prueba. -- m:drini 03:55 23 nov 2008 (UTC)

Chequear bien

lo que se dice algoritmo de Euclides extendido no es sino el llamado "teorema de Bezout" en teoría de números. En Internet hay abundante información sobre lo que digo. Consulte y dé la mano a la certeza, que no es huraña si la sabemos cortejar.--190.118.25.100 (discusión) 03:32 10 mar 2014 (UTC)