8
Une façon est de calculer leur GCD et vérifier si elle est 1.Quel est le moyen le plus rapide de vérifier si deux nombres donnés sont en coprime?
est-il un moyen plus rapide?
A
Répondre
12
L'algorithme Euclidien (calcule gcd) est très rapide. Lorsque deux nombres sont tirés au hasard uniformément de [1, n], le nombre moyen d'étapes pour calculer leur gcd est O(log n). Le temps de calcul moyen requis pour chaque étape est quadratique en nombre de chiffres.
Il existe des alternatives qui fonctionnent un peu mieux (c'est-à-dire que chaque étape est sous-quadratique dans le nombre de chiffres), mais elles ne sont efficaces que sur de très grands entiers. Voir, par exemple, On Schönhage's algorithm and subquadratic integer gcd computation.
7
Si vous utilisez une machine pour laquelle la division/le reste est significativement plus cher que les quarts de travail, considérez binary GCD.
+0
Merci, intéressant lecture –
+0
ouais, un très bon article là. – Lazer
+0
Juste implémenté cela en f # et son plus de 2x plus rapide que le GCD Euclid traditionnel, ne peut pas donner de nombres exacts car il y a d'autres codes qui poluent mes mesures, cependant c'est> 2x plus rapide. Bonne trouvaille Jason. – gatapia
Questions connexes
- 1. Quel est le moyen le plus rapide de remplir un tableau avec des nombres en PHP?
- 2. Quel est le moyen le plus rapide de vérifier si un site web est en Perl ou C?
- 3. Quel est le moyen le plus rapide pour combiner deux fichiers xml en un
- 4. Quel est le moyen le plus rapide pour déterminer si une URL existe en PHP?
- 5. Quel est le moyen le plus rapide de détecter un hôte inaccessible en Java?
- 6. Quel est le moyen le plus rapide de vérifier par programme la bonne forme des fichiers XML en C#?
- 7. NSMutableArray. Quel est le moyen le plus rapide pour le convertir en un tableau C simple?
- 8. Quel est le moyen le plus rapide de générer un ensemble unique en .net 2
- 9. Quel est le moyen le plus rapide de naviguer en haut d'une classe dans Visual Studio?
- 10. Quel est le moyen le plus rapide de dédupliquer une chaîne en C# (ASP.net)
- 11. Quel est le moyen le plus rapide d'apprendre l'objectif-c pour un développeur expérimenté en PHP?
- 12. Quel est le moyen le plus rapide pour lire/écrire sur le disque dans .NET?
- 13. Quel est le moyen le plus rapide de commencer avec le framework Kohana PHP?
- 14. Meilleur/le plus simple/le moyen le plus rapide d'obtenir un chemin relatif entre deux fichiers?
- 15. Quel est le moyen le plus simple de vérifier qu'une connexion réseau est disponible?
- 16. Quel est le moyen le plus rapide d'inverser une liste séparée par des virgules dans vim?
- 17. Quel est le moyen le plus rapide de copier mon tableau?
- 18. Le moyen le plus rapide de savoir si SQL Server est disponible
- 19. Quel est le moyen le plus rapide de charger une colonne text ou ntext SQL Server?
- 20. Quel est le moyen le plus rapide d'insérer des données dans une table Oracle?
- 21. Quel est le moyen le plus rapide d'interroger à partir d'une base de données EAV historique?
- 22. Quel est le moyen le plus performant de vérifier l'existence avec une collection d'entiers?
- 23. Quel est le moyen le plus rapide pour télécharger un énorme ensemble de données à appengine?
- 24. Quel est le moyen le plus simple et le plus rapide pour mesurer les performances HD en utilisant Python?
- 25. Dans jQuery, quel est le moyen le plus rapide de sélectionner un groupe d'éléments?
- 26. Le moyen le plus rapide de savoir si l'hôte distant est joignable
- 27. Quel est le moyen le plus rapide de dessiner une image sur une autre image?
- 28. Quel est le moyen le plus rapide de trouver un fichier dans Zend Studio pour Eclipse?
- 29. Quel est le moyen le plus rapide de parcourir un objet Excel Range à l'envers?
- 30. Transfert de 100 000 images vers S3. Quel est le moyen le plus rapide?
Je voudrais commenter que c'est un peu grossier de mesurer la complexité des algorithmes arithmétiques sans prendre en compte les coûts des opérations arithmétiques. –
Le nombre de pas de maléfice est également O (log n), lorsque deux nombres sont des entrées successives dans la séquence de Fibonacci. –
@Pavel Shved: J'ai pris en compte le coût. cf. la phrase "Le temps de calcul moyen requis pour chaque étape est quadratique dans le nombre de chiffres." – jason