8
Una forma es calcular su mcd y comprobar si es 1.¿Cuál es la forma más rápida de verificar si dos números dados son coprime?
¿Hay alguna forma más rápida?
A
Respuesta
12
El algoritmo euclidiano (calcula gcd) es muy rápido. Cuando dos números se dibujan uniformemente al azar desde [1, n], el número promedio de pasos para calcular su gcd es O(log n). El tiempo promedio de cálculo requerido para cada paso es cuadrático en el número de dígitos.
Existen alternativas que funcionan un poco mejor (es decir, cada paso es subcuadratico en la cantidad de dígitos), pero solo son efectivas en enteros muy grandes. Ver, por ejemplo, On Schönhage's algorithm and subquadratic integer gcd computation.
7
si está ejecutando en una máquina para la cual la división/el resto es significativamente más caro que los turnos, considere binary GCD.
+0
Gracias, interesante lea –
+0
sí, un muy buen artículo allí. – Lazer
+0
Simplemente implementado esto en f # y es más de 2 veces más rápido que el GCD de Euclid tradicional, no puedo dar números exactos ya que hay otro código que contamina mis mediciones, sin embargo es> 2 veces más rápido. Buen hallazgo Jason. – gatapia
Cuestiones relacionadas
- 1. ¿Cuál es la forma más rápida de verificar si dos Tbitmaps son iguales?
- 2. ¿Cuál es la forma más fácil de averiguar si dos archivos son diferentes por programación?
- 3. Comprobando si dos números son permutaciones entre sí?
- 4. La forma más rápida de verificar si existe un objeto
- 5. ¿Cuál es la forma más rápida de verificar si todos los valores en una matriz son numéricos?
- 6. ¿Cuál es la forma más rápida de comparar dos mapas de bits de igual tamaño para determinar si son idénticos?
- 7. ¿Cuál es la mejor y más rápida forma de verificar si la imagen es válida en PHP?
- 8. ¿La forma más rápida de verificar si un tipo es blittable?
- 9. ¿Cuál es la manera más rápida de verificar si hay dígitos duplicados de un número?
- 10. ¿Cuál es la forma más rápida de comparar matrices de dos bytes?
- 11. ¿Cuál es la forma más rápida de grabar varios archivos?
- 12. ¿cuál es la forma más rápida de encontrar el gcd de n números?
- 13. ¿Cuál es la forma más rápida de verificar si la cadena tiene una letra mayúscula en C#?
- 14. ¿Cuál es la forma más rápida de comparar la configuración IIS de dos servidores?
- 15. C manera más rápida de verificar si existe un directorio
- 16. ¿Cuál es la manera más rápida de verificar si una clase tiene una función definida?
- 17. MySQL - La forma más rápida de verificar si los datos en la tabla InnoDB han cambiado
- 18. ¿Cuál es la forma más rápida de comparar dos matrices para la igualdad?
- 19. al codificar cuál es la forma más rápida de determinar si un tipo es IDisposable
- 20. ¿Cuál es la forma más rápida de probar si un objeto es IEnumerable?
- 21. ¿Cuál es la forma más rápida de verificar si una palabra de una cadena está en otra cadena?
- 22. ¿Cuál es la forma más rápida de comparar dos objetos en PHP?
- 23. ¿Cuál es la forma más confiable de verificar si una variable de JavaScript es nula?
- 24. ¿Cuál es la forma más rápida de combinar dos archivos xml en uno
- 25. ¿La forma más rápida de calcular números primos en C#?
- 26. ¿Cuál es la forma más rápida de calcular los dos primeros componentes principales en R?
- 27. La forma más rápida de verificar si se puede analizar una Cadena en Doblar en Java
- 28. ¿Cuál es la forma más rápida de obtener la media de un conjunto de números desde la línea de comando?
- 29. Forma más rápida fusionar dos bases de datos SQLITE
- 30. ¿Cuál es la forma más rápida de saltar a un constructor (es) en una clase?
Me gustaría comentar que es un poco basto para medir la complejidad de los algoritmos aritméticos sin tener en cuenta los costos de las operaciones aritméticas. –
El peor número de pasos es O (log n) también, cuando dos números son entradas sucesivas en la secuencia de Fibonacci. –
@Pavel Shved: Tomé el costo en consideración. cf. la oración "El tiempo promedio de cálculo requerido para cada paso es cuadrático en el número de dígitos". – jason