No creo que nadie sepa esto, así que sugiero implementar ambos y probarlos en la práctica en una variedad de plataformas.
Debo decir que espero que la diferencia no sea enorme, ya que el módulo entero es muy rápido en el hardware moderno. También depende de las distribuciones de números de su aplicación, ya que algunos números requieren más iteraciones en el mcd de Euclid que otros. Creo que el peor caso para el algoritmo de Euclides es cuando calculas el mcd de dos números consecutivos de Fibonacci; en ese caso, tiene que procesar a través de toda la cadena de Fibonacci, por lo que los números se reducen en aproximadamente la proporción áurea de cada iteración, en lugar de un factor de dos.
Entonces, para esos números, estoy seguro de que cambiar a un mcd binario es útil, mientras que para otras entradas, la sobrecarga del uso del módulo entero podría compensarse con reducciones mayores.
- ¿Puede una computadora generar un número verdaderamente aleatorio?
- Cómo aumentar mis habilidades en programación dinámica
- ¿Qué es un algoritmo eficiente para el agrupamiento k-means donde k es 2 y la dimensión es una, con o sin pesos?
- ¿Por qué conocer estructuras de datos y algoritmos básicos no es suficiente para descifrar la mayoría de las entrevistas técnicas?
- Para (I = 0; I <3; I ++) fork (), ¿cómo puedo hacer un algoritmo para contar el número de procesos y mostrarlo solo una vez?
También puede pensar en hacer un algoritmo personalizado, por ejemplo, si sus números nunca son demasiado grandes, podría tener un algoritmo que se base en una tabla de búsqueda que asigne cada número a una lista de sus factores primos. Luego puede hacer coincidir esas listas y multiplicar todos los factores que tienen en común.
