algorithm - tales - propiedades de maximo comun divisor
Complejidad del tiempo del algoritmo de Euclides (9)
Aquí hay una comprensión intuitiva de la complejidad en el tiempo de ejecución del algoritmo de Euclides. Las pruebas formales están cubiertas en varios textos, como Introducción a los algoritmos y TAOCP Vol 2.
Primero piense qué pasaría si tratamos de tomar el gcd de dos números de Fibonacci F (k + 1) y F (k). Puede observar rápidamente que el algoritmo de Euclides itera a F (k) y F (k-1). Es decir, con cada iteración bajamos un número en la serie de Fibonacci. Como los números de Fibonacci son O (Phi ^ k) donde Phi es la proporción áurea, podemos ver que el tiempo de ejecución de GCD era O (log n) donde n = max (a, b) y log tiene base de Phi. A continuación, podemos demostrar que este sería el peor de los casos al observar que los números de Fibonacci producen pares consistentemente donde los restos permanecen lo suficientemente grandes en cada iteración y nunca se vuelven cero hasta que hayas llegado al comienzo de la serie.
Podemos hacer que O (log n) donde n = max (a, b) se vincule aún más. Supongamos que b> = a para que podamos escribir enlazado a O (log b). Primero, observe que GCD (ka, kb) = GCD (a, b). Como los mayores valores de k son gcd (a, c), podemos reemplazar b con b / gcd (a, b) en nuestro tiempo de ejecución, lo que lleva a un límite más estricto de O (log b / gcd (a, b)).
Tengo dificultades para decidir cuál es la complejidad temporal del algoritmo de denominador común más grande de Euclides. Este algoritmo en pseudo-código es:
function gcd(a, b)
while b ≠ 0
t := b
b := a mod b
a := t
return a
Parece depender de a y b . Mi pensamiento es que la complejidad del tiempo es O (a% b). ¿Es eso correcto? ¿Hay una mejor manera de escribir eso?
El peor caso del Algoritmo Euclid es cuando los residuos son los más grandes posibles en cada paso, es decir. durante dos términos consecutivos de la secuencia de Fibonacci.
Cuando n y m son el número de dígitos de ayb, suponiendo n> = m, el algoritmo usa O (m) divisiones.
Tenga en cuenta que las complejidades siempre se dan en términos del tamaño de las entradas, en este caso, el número de dígitos.
El peor caso surgirá cuando tanto n como m sean números de Fibonacci consecutivos.
gcd (Fn, Fn-1) = gcd (Fn-1, Fn-2) = ⋯ = gcd (F1, F0) = 1 y enésimo número de Fibonacci es 1.618 ^ n, donde 1.618 es la Proporción áurea.
Entonces, para encontrar gcd (n, m), el número de llamadas recursivas será Θ (logn).
El teorema de Gabriel Lame limita el número de pasos por log (1 / sqrt (5) * (a + 1/2)) - 2, donde la base del registro es (1 + sqrt (5)) / 2. Esto es para el escenario del peor caso para el algoritmo y ocurre cuando las entradas son números Fibanocci consecutivos.
Un límite ligeramente más liberal es: log a, donde la base del registro es (sqrt (2)) está implícito en Koblitz.
Para fines criptográficos usualmente consideramos la complejidad bit a bit de los algoritmos, teniendo en cuenta que el tamaño del bit está dado aproximadamente por k = loga.
Aquí hay un análisis detallado de la complejidad bit a bit del Algoritmo Euclid:
Aunque en la mayoría de las referencias la complejidad bit a bit del algoritmo Euclid está dada por O (loga) ^ 3 existe un límite más apretado que es O (loga) ^ 2.
Considerar; r0 = a, r1 = b, r0 = q1.r1 + r2. . . , ri-1 = qi.ri + ri + 1,. . . , rm-2 = qm-1.rm-1 + rm rm-1 = qm.rm
observe que: a = r0> = b = r1> r2> r3 ...> rm-1> rm> 0 .......... (1)
y rm es el mayor divisor común de a y b.
Por un Reclamo en el libro de Koblitz (Un curso en Teoría de números y Criptografía) se puede demostrar que: ri + 1 <(ri-1) / 2 ................. ( 2)
De nuevo en Koblitz, el número de operaciones de bits requeridas para dividir un entero positivo de k bits por un entero positivo de 1 bit (suponiendo que k> = l) se da como: (k-l + 1) .l ...... ............. (3)
Por (1) y (2) el número de divisiones es O (loga) y así por (3) la complejidad total es O (loga) ^ 3.
Ahora esto puede reducirse a O (loga) ^ 2 mediante un comentario en Koblitz.
considere ki = logri +1
por (1) y (2) tenemos: ki + 1 <= ki para i = 0,1, ..., m-2, m-1 y ki + 2 <= (ki) -1 para i = 0 , 1, ..., m-2
y por (3) el costo total de las m divisiones está limitado por: SUM [(ki-1) - ((ki) -1))] * ki para i = 0,1,2, ..., m
reordenando esto: SUM [(ki-1) - ((ki) -1))] * ki <= 4 * k0 ^ 2
Entonces, la complejidad bit a bit del algoritmo de Euclides es O (loga) ^ 2.
Hay un gran vistazo a esto en el artículo de wikipedia .
Incluso tiene una buena trama de complejidad para los pares de valores.
No es O (a% b).
Se sabe (ver artículo) que nunca tomará más pasos que cinco veces el número de dígitos en el número más pequeño. Por lo tanto, el número máximo de pasos crece a medida que el número de dígitos (ln b). El costo de cada paso también crece como el número de dígitos, por lo que la complejidad está limitada por O (ln ^ 2 b) donde b es el nubmer más pequeño. Ese es un límite superior, y el tiempo real suele ser menor.
La forma adecuada de analizar un algoritmo es determinar sus peores escenarios. El peor caso de Euclidean GCD ocurre cuando los Pares de Fibonacci están involucrados. void EGCD(fib[i], fib[i - 1]) , donde i> 0.
Por ejemplo, optemos por el caso en el que el dividendo es 55, y el divisor es 34 (recuerde que todavía estamos tratando con números de Fibonacci).
Como puede observar, esta operación costó 8 iteraciones (o llamadas recursivas).
Probemos con los números de Fibonacci más grandes, a saber, 121393 y 75025. Aquí podemos observar que se necesitaron 24 iteraciones (o llamadas recursivas).
También puede observar que cada iteración produce un número de Fibonacci. Es por eso que tenemos tantas operaciones. No podemos obtener resultados similares solo con los números de Fibonacci de hecho.
Por lo tanto, esta vez la complejidad del tiempo se representará con un pequeño Oh (límite superior). El límite inferior es intuitivamente Omega (1): caso de 500 dividido por 2, por ejemplo.
Vamos a resolver la relación de recurrencia:
Podemos decir entonces que Euclidean GCD puede hacer la operación de logaritmo (xy) como máximo .
Mira here .
En particular esta parte:
Lamé mostró que la cantidad de pasos necesarios para llegar al mayor divisor común para dos números menores que n es
Entonces O(log min(a, b)) es un buen límite superior.
Para el algoritmo iterativo, sin embargo, tenemos:
int iterativeEGCD(long long n, long long m) {
long long a;
int numberOfIterations = 0;
while ( n != 0 ) {
a = m;
m = n;
n = a % n;
numberOfIterations ++;
}
printf("/nIterative GCD iterated %d times.", numberOfIterations);
return m;
}
Con los pares de Fibonacci, no hay diferencia entre iterativeEGCD() y iterativeEGCDForWorstCase() donde este último se ve así:
int iterativeEGCDForWorstCase(long long n, long long m) {
long long a;
int numberOfIterations = 0;
while ( n != 0 ) {
a = m;
m = n;
n = a - n;
numberOfIterations ++;
}
printf("/nIterative GCD iterated %d times.", numberOfIterations);
return m;
}
Sí, con pares de Fibonacci, n = a % n y n = a - n , es exactamente lo mismo.
También sabemos que, en una respuesta anterior para la misma pregunta, prevalece un factor decreciente: factor = m / (n % m) .
Por lo tanto, para dar forma a la versión iterativa del GCD Euclidiano en una forma definida, podemos describirlo como un "simulador" como este:
void iterativeGCDSimulator(long long x, long long y) {
long long i;
double factor = x / (double)(x % y);
int numberOfIterations = 0;
for ( i = x * y ; i >= 1 ; i = i / factor) {
numberOfIterations ++;
}
printf("/nIterative GCD Simulator iterated %d times.", numberOfIterations);
}
Basado en el work (última diapositiva) del Dr. Jauhar Ali, el ciclo anterior es logarítmico.
Sí, pequeño Oh, porque el simulador dice la cantidad de iteraciones como máximo . Los pares que no son de Fibonacci tomarían una menor cantidad de iteraciones que Fibonacci, cuando se sondearon en Euclides GCD.
Un truco para analizar la complejidad del tiempo del algoritmo de Euclides es seguir lo que sucede en dos iteraciones:
a'', b'' := a % b, b % (a % b)
Ahora a y b disminuirán, en lugar de solo uno, lo que facilita el análisis. Puedes dividirlo en casos:
- Tiny A:
2a <= b - Tiny B:
2b <= a - Pequeño A:
2a > bperoa < b - Pequeño B:
2b > aperob < a - Igual:
a == b
Ahora mostraremos que cada caso individual disminuye el total a+b por al menos un trimestre:
- Tiny A:
b % (a % b) < ay2a <= b, por lo quebse reduce al menos a la mitad, por lo quea+bdisminuyó en al menos un25% - Tiny B:
a % b < by2b <= a, por lo quease reduce al menos a la mitad, por lo quea+bdisminuyó en al menos un25% - Small A:
bse convertirá enba, que es menor queb/2, disminuyendoa+ben al menos25%. - B pequeño:
ase convertirá enab, que es menor quea/2, disminuyendoa+ben al menos un25%. - Igual:
a+bcae a0, lo que obviamente disminuyea+ben al menos25%.
Por lo tanto, por análisis de casos, cada paso doble disminuye a+b en al menos 25% . Hay una cantidad máxima de veces que esto puede suceder antes de que a+b se vea forzado a caer por debajo de 1 . El número total de pasos ( S ) hasta que lleguemos a 0 debe satisfacer (4/3)^S <= A+B Ahora solo trabajalo:
(4/3)^S <= A+B
S <= lg[4/3](A+B)
S is O(lg[4/3](A+B))
S is O(lg(A+B))
S is O(lg(A*B)) //because A*B asymptotically greater than A+B
S is O(lg(A)+lg(B))
//Input size N is lg(A) + lg(B)
S is O(N)
Entonces, el número de iteraciones es lineal en el número de dígitos de entrada. Para los números que se ajustan a los registros de la CPU, es razonable modelar las iteraciones como tomar un tiempo constante y pretender que el tiempo total de ejecución del gcd es lineal.
Por supuesto, si se trata de enteros grandes, debe tener en cuenta el hecho de que las operaciones de módulo dentro de cada iteración no tienen un costo constante. En términos generales, el tiempo de ejecución asintótico total va a ser n ^ 2 veces un factor poliglotámico. Algo así como n^2 lg(n) 2^O(log* n) . El factor polilogarítmico se puede evitar utilizando en su lugar un gcd binario .