¿Qué es más eficiente para GCD?

26

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;
}
jonaprieto
fuente
3
Creo que esto es demasiado subjetivo y quizás incluso más adecuado para StackOverflow. "La mayoría eficiente en la práctica" depende de muchos factores (incluso impredecibles), tales como el architechture subyacente, jerarquía de memoria, tamaño y forma de la entrada etc.
Juho
55
Este es el mismo algoritmo expresado de forma recursiva e iterativa. Creo que su diferencia es insignificante ya que el algoritmo Euclid converge bastante rápido. Elija uno que se ajuste a su preferencia.
pad
66
Es posible que desee intentar perfilar estos dos. Dado que la versión recursiva es una llamada de cola, no es improbable que el compilador realmente emita casi el mismo código.
Louis
1
esto está mal. debería ser while b! = 0, y luego devolver a. De lo contrario, se divide en división por cero. tampoco use la recursividad si tiene gcds realmente grandes ... obtiene una pila de estados de pila y función ... ¿por qué no simplemente ir iterativo?
Cris Stringfellow
44
Tenga en cuenta que hay algoritmos GCD asintóticamente más rápidos. Por ejemplo, en.wikipedia.org/wiki/Binary_GCD_algorithm
Neal Young el

Respuestas:

21

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: unayosiyoyo

unayo+1=siyosiyo+1=unayometrooresiyo

En la versión imperativa, dejemos que y sean los valores de las variables y al comienzo de la ésima iteración del bucle. unayosiyoabyo

unayo+1=siyosiyo+1=unayometrooresiyo

¿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.unayo=0 0unayo=0 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).

Gilles 'SO- deja de ser malvado'
fuente
8

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í .

qwr
fuente
El enlace realmente no proporciona detalles completos, y ni siquiera define qué es una "extremidad" ...
einpoklum - restablece a Mónica
2

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.

PJTraill
fuente
Qué quiere decir que ahora que sé ? ¿Quiere decir que la especificación del lenguaje no exige esta optimización (sería sorprendente si lo hiciera) o que la mayoría de las implementaciones no la implementan?
PJTraill
1

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.

Florian F
fuente
3
“Evita la recursividad. Es lento ”- presentado como un consejo general, esto es falso. Depende del compilador. Por lo general, incluso con compiladores que no optimizan la recursividad, no es lento, solo consume mucha pila.
Gilles 'SO- deja de ser malvado'
3
Pero para un código corto como este, la diferencia es significativa. Consumir pilas significa escribir y leer desde la memoria. Eso es lento El código anterior se ejecuta en 2 registros. La recursividad también significa hacer llamadas, que es más largo que un salto condicional. Una llamada recursiva es mucho más difícil para la predicción de rama y más difícil de alinear.
Florian F
-2

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 ++)

Por Alexandersson
fuente
No se ve bien. Para b == 1, debería devolver 1. Y GCD [2,1000000000] será lento.
Florian F
Ah, sí, cometí un error. Fijo (creo) y aclarado.
Según Alexandersson el
Normalmente, GCD [a, 0] también debería devolver a. El tuyo bucles para siempre.
Florian F
Estoy votando porque su respuesta solo contiene código. Nos gusta centrarnos en ideas en este sitio. Por ejemplo, ¿por qué% es una operación costosa? La especulación sobre un fragmento de código no es realmente una buena respuesta para este sitio, en mi opinión.
Juho
1
Creo que la idea de que el módulo es más lento que la sustracción puede considerarse folklore. Tiene tanto para enteros pequeños (la resta generalmente toma un ciclo, el módulo rara vez lo hace) como para enteros grandes (la resta es lineal, no estoy seguro de cuál es la mejor complejidad para el módulo, pero definitivamente es peor que eso). Por supuesto, también debe tener en cuenta la cantidad de iteraciones necesarias.
Gilles 'SO- deja de ser malvado'
-2

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. 
Rohit-Pandey
fuente
44
Esto no responde la pregunta. El autor de la pregunta presenta dos versiones de Euclid y pregunta cuál es más rápido. No parece haber notado eso y simplemente declara que la versión recursiva es el único algoritmo de Euclides, y afirma sin evidencia alguna que es más rápido que todo lo demás.
David Richerby