Primero, date cuenta de esto:
El algoritmo de Euclides se usa ampliamente en la práctica, especialmente para números pequeños, debido a su simplicidad.
A modo de comparación, se puede determinar la eficiencia de las alternativas al algoritmo de Euclides.
Un enfoque ineficiente para encontrar el MCD de dos números naturales ayb es calcular todos sus divisores comunes; El MCD es entonces el mayor divisor común. Los divisores comunes se pueden encontrar dividiendo ambos números por enteros sucesivos de 2 al número más pequeño b . El número de pasos de este enfoque crece linealmente con b , o exponencialmente en el número de dígitos. Otro enfoque ineficiente es encontrar los factores primos de uno o ambos números. Como se señaló anteriormente, el MCD es igual al producto de los factores primos compartidos por los dos números ay b .
Los métodos actuales para la factorización prima también son ineficientes; muchos sistemas modernos de criptografía incluso confían en esa ineficiencia.
En cuanto al rendimiento, recomendaría el algoritmo Binary GCD
El algoritmo reduce el problema de encontrar el MCD aplicando repetidamente estas identidades:
- mcd (0, v ) = v , porque todo divide a cero, y v es el número más grande que divide a v . Del mismo modo, mcd ( u , 0) = u . Normalmente no se define gcd (0, 0), pero es conveniente establecer gcd (0, 0) = 0.
- Si u y v son ambos pares, entonces gcd ( u , v ) = 2 · gcd ( u / 2, v / 2), porque 2 es un divisor común.
- Si u es par y v es impar, entonces mcd ( u , v ) = mcd ( u / 2, v ), porque 2 no es un divisor común. Del mismo modo, si u es impar y v es par, entonces mcd ( u , v ) = mcd ( u , v / 2).
- Si u y v son impares, y u ≥ v , entonces mcd ( u , v ) = mcd (( u – v ) / 2, v ). Si ambos son impares y u < v , entonces mcd ( u , v ) = mcd (( v – u ) / 2, u ). Estas son combinaciones de un paso del algoritmo euclidiano simple, que utiliza la resta en cada paso, y una aplicación del paso 3 anterior. La división por 2 da como resultado un número entero porque la diferencia de dos números impares es par.
- Repita los pasos 2–4 hasta que u = v , o (un paso más) hasta u = 0. En cualquier caso, el MCD es 2 kv , donde k es el número de factores comunes de 2 encontrados en el paso 2.
El algoritmo requiere O (n) el peor de los casos, donde n es el número de bits en el mayor de los dos números. Aunque cada paso reduce al menos uno de los operandos en al menos un factor de 2, las operaciones de sustracción y desplazamiento toman tiempo lineal para enteros muy grandes (aunque todavía son bastante rápidos en la práctica, requiriendo aproximadamente una operación por palabra de la representación )
Knuth proporciona un GCD binario extendido, análogo al algoritmo euclidiano extendido, junto con punteros a otras versiones.
Implementación de BCD GCD:
El algoritmo reduce el problema de encontrar el MCD aplicando repetidamente estas identidades:
gcd (0, v) = v, porque todo divide a cero, y v es el número más grande que divide v. De manera similar, gcd (u, 0) = u. Normalmente no se define gcd (0, 0), pero es conveniente establecer gcd (0, 0) = 0.
Si u y v son ambos pares, entonces gcd (u, v) = 2 · gcd (u / 2, v / 2), porque 2 es un divisor común.
Si u es par y v es impar, entonces mcd (u, v) = mcd (u / 2, v), porque 2 no es un divisor común. Del mismo modo, si u es impar y v es par, entonces mcd (u, v) = mcd (u, v / 2).
Si u y v son impares, y u ≥ v, entonces mcd (u, v) = mcd ((u – v) / 2, v). Si ambos son impares y u
Repita los pasos 2–4 hasta u = v, o (un paso más) hasta u = 0. En cualquier caso, el MCD es 2kv, donde k es el número de factores comunes de 2 encontrados en el paso 2.
El algoritmo requiere O (n2) en el peor de los casos, donde n es el número de bits en el mayor de los dos números. Aunque cada paso reduce al menos uno de los operandos en al menos un factor de 2, las operaciones de sustracción y desplazamiento toman tiempo lineal para enteros muy grandes (aunque todavía son bastante rápidos en la práctica, requiriendo aproximadamente una operación por palabra de la representación )
Knuth proporciona un GCD binario extendido, análogo al algoritmo euclidiano extendido, junto con punteros a otras versiones.
La siguiente es una implementación recursiva del algoritmo en C. La implementación es similar a la descripción del algoritmo dada anteriormente. Utiliza dos argumentos u y v . Todas menos una de las llamadas recursivas son recursivas de cola.
unsigned int gcd (unsigned int u, unsigned int v)
{
// casos simples (terminación)
si (u == v)
volver u;
si (u == 0)
volver v;
si (v == 0)
volver u;
// busca factores de 2
si (~ u & 1) // u es par
{
si (v & 1) // v es impar
devuelve mcd (u >> 1, v);
sino // tanto u como v son pares
return gcd (u >> 1, v >> 1) << 1;
}
si (~ v & 1) // u es impar, v es par
devuelve mcd (u, v >> 1);
// reduce el argumento más grande
si (u> v)
devuelve mcd ((u – v) >> 1, v);
devuelve mcd ((v – u) >> 1, u);
}
Versión iterativa en C
A continuación se muestra una implementación del algoritmo en C, tomando dos argumentos enteros (no negativos) u y v . Primero elimina todos los factores comunes de 2 usando la identidad 2, luego calcula el MCD de los números restantes usando las identidades 3 y 4, y los combina para formar la respuesta final.
unsigned int gcd (unsigned int u, unsigned int v)
{
int shift;
/ * MCD (0, v) == v; MCD (u, 0) == u, MCD (0,0) == 0 * /
if (u == 0) devuelve v;
if (v == 0) devuelve u;
/ * Let shift: = lg K, donde K es la mayor potencia de 2
dividiendo tanto u como v. * /
para (shift = 0; ((u | v) & 1) == 0; ++ shift) {
u >> = 1;
v >> = 1;
}
while ((u & 1) == 0)
u >> = 1;
/ * De aquí en adelante, siempre es extraño. * /
hacer {
/ * eliminar todos los factores de 2 en v – no son comunes * /
/ * nota: v no es cero, así que mientras terminará * /
while ((v & 1) == 0) / * Loop X * /
v >> = 1;
/ * Ahora u y v son ambos impares. Cambie si es necesario para que u <= v,
luego establezca v = v – u (que es par). Para bignums, el
el intercambio es solo movimiento del puntero, y la resta
Se puede hacer en el lugar. * /
si (u> v) {
unsigned int t = v; v = u; u = t;} // Intercambia u y v.
v = v – u; // Aquí v> = u.
} while (v! = 0);
/ * restaurar factores comunes de 2 * /
volver u << turno;
}
El algoritmo reduce el problema de encontrar el MCD aplicando repetidamente estas identidades:
gcd (0, v) = v, porque todo divide a cero, y v es el número más grande que divide v. De manera similar, gcd (u, 0) = u. Normalmente no se define gcd (0, 0), pero es conveniente establecer gcd (0, 0) = 0.
Si u y v son ambos pares, entonces gcd (u, v) = 2 · gcd (u / 2, v / 2), porque 2 es un divisor común.
Si u es par y v es impar, entonces mcd (u, v) = mcd (u / 2, v), porque 2 no es un divisor común. Del mismo modo, si u es impar y v es par, entonces mcd (u, v) = mcd (u, v / 2).
Si u y v son impares, y u ≥ v, entonces mcd (u, v) = mcd ((u – v) / 2, v). Si ambos son impares y u
Repita los pasos 2–4 hasta u = v, o (un paso más) hasta u = 0. En cualquier caso, el MCD es 2kv, donde k es el número de factores comunes de 2 encontrados en el paso 2.
El algoritmo requiere O (n2) en el peor de los casos, donde n es el número de bits en el mayor de los dos números. Aunque cada paso reduce al menos uno de los operandos en al menos un factor de 2, las operaciones de sustracción y desplazamiento toman tiempo lineal para enteros muy grandes (aunque todavía son bastante rápidos en la práctica, requieren aproximadamente una operación por palabra de la representación )
Knuth proporciona un GCD binario extendido, análogo al algoritmo euclidiano extendido, junto con punteros a otras versiones.
