¿Qué es más eficiente para GCD?

Sé que el algoritmo de Euclides es el mejor algoritmo para obtener el GCD (gran divisor común) de una lista de enteros positivos. Pero en la práctica, puede codificar este algoritmo de varias maneras. (En mi caso, decidí usar Java, pero C / C ++ puede ser otra opción).

Necesito usar el código más eficiente posible en mi programa.

En modo recursivo, puedes escribir:

static long gcd (long a, long b){
    a = Math.abs(a); b = Math.abs(b);
    return (b==0) ? a : gcd(b, a%b);
  }

Y en modo iterativo, se ve así:

static long gcd (long a, long b) {
  long r, i;
  while(b!=0){
    r = a % b;
    a = b;
    b = r;
  }
  return a;
}

También existe el algoritmo binario para el GCD, que puede codificarse simplemente así:

int gcd (int a, int b)
{
    while(b) b ^= a ^= b ^= a %= b;
    return a;
}

Sus dos algoritmos son equivalentes (al menos para los enteros positivos, lo que sucede con los enteros negativos en la versión imperativa depende de la semántica de Java para la %que no sé de memoria). En la versión recursiva, deje que y sean el argumento de la ésima llamada recursiva: $a_i$$b_i$$i$

En la versión imperativa, dejemos que y sean los valores de las variables y al comienzo de la ésima iteración del bucle. $a'_i$$b'_i$ab$i$

¿Notas un parecido? Su versión imperativa y su versión recursiva están calculando exactamente los mismos valores. Además, ambos terminan al mismo tiempo, cuando (resp. ), por lo que realizan el mismo número de iteraciones. Hablando algorítmicamente, no hay diferencia entre los dos. Cualquier diferencia será una cuestión de implementación, altamente dependiente del compilador, el hardware en el que se ejecuta, y posiblemente el sistema operativo y los otros programas que se ejecutan simultáneamente.$a_i=0$$a'_i=0$

La versión recursiva solo realiza llamadas recursivas de cola . La mayoría de los compiladores para lenguajes imperativos no los optimizan, por lo que es probable que el código que generan desperdicie un poco de tiempo y memoria construyendo un marco de pila en cada iteración. Con un compilador que optimiza las llamadas de cola (los compiladores para lenguajes funcionales casi siempre lo hacen), el código de máquina generado puede ser el mismo para ambos (suponiendo que armonice esas llamadas abs).

Para números que son pequeños, el algoritmo binario GCD es suficiente.

GMP, una biblioteca bien mantenida y probada en el mundo real, cambiará a un algoritmo especial de medio GCD después de pasar un umbral especial, una generalización del algoritmo de Lehmer. Lehmer's usa la multiplicación de matrices para mejorar los algoritmos euclidianos estándar. Según los documentos, el tiempo de funcionamiento asintótico de HGCD y GCD es O(M(N)*log(N)), donde M(N)es el tiempo para multiplicar dos números de N-extremidades.

Los detalles completos sobre su algoritmo se pueden encontrar aquí .

Como sé, Java no admite la optimización de recursión de cola en general, pero puede probar su implementación de Java para ello; Si no lo admite, un forbucle simple debería ser más rápido, de lo contrario, la recursión debería ser igual de rápida. Por otro lado, estas son optimizaciones de bits, elija el código que cree que es más fácil y más legible.

También debo señalar que el algoritmo GCD más rápido no es el algoritmo de Euclides, el algoritmo de Lehmer es un poco más rápido.

Primero, no use la recursividad para reemplazar un circuito cerrado. Es lento. No confíe en el compilador para optimizarlo. Segundo, en su código, llama a Math.abs () dentro de cada llamada recursiva, lo cual es inútil.

En su ciclo, puede evitar fácilmente variables temporales e intercambiar ayb todo el tiempo.

int gcd(int a, int b){
    if( a<0 ) a = -a;
    if( b<0 ) b = -b;
    while( b!=0 ){
        a %= b;
        if( a==0 ) return b;
        b %= a;
    }
    return a;
}

El intercambio con a ^ = b ^ = a ^ = b acorta la fuente pero requiere muchas instrucciones para ejecutar. Será más lento que el aburrido intercambio con una variable temporal.

Para números pequeños ,% es una operación bastante costosa, quizás la más simple recursiva

GCD[a,b] := Which[ 
   a==b , Return[a],
   b > a, Return[ GCD[a, b-a]],
   a > b, Return[ GCD[b, a-b]]
];

es mas rapido? (Lo siento, código de Mathematica y no C ++)

El algoritmo de Euclides es más eficiente para calcular GCD:

Estático largo mcd (largo a, largo b)
{
si (b == 0)
devolver a;
más
devuelve mcd (, a% b);
}

ejemplo:-

Deje A = 16, B = 10.
MCD (16, 10) = MCD (10, 16% 10) = MCD (10, 6)
MCD (10, 6) = MCD (6, 10% 6) = MCD (6, 4)
MCD (6, 4) = MCD (4, 6% 4) = MCD (4, 2)
MCD (4, 2) = MCD (2, 4% 2) = MCD (2, 0)


Como B = 0, GCD (2, 0) devolverá 2.