8
Un modo è quello di calcolare la loro GCD e verificare se è 1.Qual è il modo più veloce per verificare se due numeri dati sono coprimi?
C'è qualche modo più veloce?
A
risposta
12
L'algoritmo Euclideo (calcola gcd) è molto veloce. Quando due numeri vengono disegnati in modo uniforme a caso da [1, n], il numero medio di passaggi per calcolare il loro gcd è O(log n). Il tempo medio di calcolo richiesto per ogni passaggio è quadratico nel numero di cifre.
Esistono alternative che offrono prestazioni migliori (ad esempio, ogni passaggio è subquadratico nel numero di cifre), ma sono efficaci solo su numeri interi molto grandi. Vedi, ad esempio, On Schönhage's algorithm and subquadratic integer gcd computation.
7
se si esegue su una macchina per cui la divisione/resto è significativamente più costosa rispetto ai turni, prendere in considerazione binary GCD.
+0
Grazie, interessante lettura –
+0
sì, un ottimo articolo lì. – Lazer
+0
L'ho appena implementato in f # e più di due volte più veloce del tradizionale GCD di Euclid, non è possibile fornire numeri esatti in quanto vi sono altri codici che inquinano le mie misurazioni, tuttavia è> 2x più veloce. Buona scoperta, Jason. Aggiornamento – gatapia
Problemi correlati
- 1. Qual è il modo più veloce per verificare se due Tbitmap sono uguali?
- 2. Qual è il modo più veloce per verificare se Input String è un'espressione RPN corretta?
- 3. Qual è il modo migliore e più veloce per verificare se l'immagine è valida in PHP?
- 4. Il modo più veloce per verificare se esiste un oggetto
- 5. Qual è il modo più veloce per verificare se una classe ha una funzione definita?
- 6. Controllare se due numeri sono permutazione l'uno dell'altro?
- 7. Qual è il modo più veloce per calcolare i primi due componenti principali in R?
- 8. Qual è il modo più veloce per verificare se una stringa contiene caratteri ripetuti in Python 3?
- 9. Qual è il modo più veloce per ottenere frequenze di numeri interi in un vettore?
- 10. Il modo più veloce per verificare se un tipo è blittabile?
- 11. Qual è il modo più veloce per verificare se un punto si trova all'interno di un poligono in python
- 12. Qual è il modo più veloce per verificare le cifre duplicate di un numero?
- 13. Qual è il modo più veloce per confrontare due array di byte?
- 14. Qual è il modo più veloce per confrontare due array per l'uguaglianza?
- 15. Qual è il modo più rapido per verificare se tutti i valori in una matrice sono numerici?
- 16. Qual è il modo più veloce per unire due elenchi in python?
- 17. Qual è il modo più veloce per verificare che la voce esista nel database?
- 18. Qual è il modo più veloce per confrontare due oggetti in PHP?
- 19. Qual è il modo più affidabile per verificare se una variabile JavaScript è nullo?
- 20. Qual è il modo più veloce per combinare due file xml in uno
- 21. Qual è il modo più semplice per scoprire se due file sono diversi a livello di codice?
- 22. Il modo più veloce per verificare se una stringa può essere analizzata in Double in Java
- 23. Qual è il modo più veloce per filtrare i dati da ArrayList?
- 24. Come testare se due numeri sono chiusi in Clojure
- 25. Il modo più veloce per verificare se alcuni record in una tabella di database?
- 26. WCF - qual è il legame più veloce?
- 27. Il modo più veloce per verificare se un oggetto esiste in Core Data o no?
- 28. Qual è il modo più veloce per ottenere l'output CSV in un frame di dati?
- 29. Quale algoritmo è più veloce per verificare se è impostato un bit?
- 30. Il modo più veloce per scrivere dati durante la produzione
Mi piacerebbe commentare che è un po 'grossolano misurare la complessità degli algoritmi aritmetici senza tenere conto dei costi delle operazioni aritmetiche. –
Il numero peggiore di passaggi è O (log n) anche quando due numeri sono voci successive nella sequenza di Fibonacci. –
@Pavel Shved: ho preso in considerazione il costo. cf. la frase "Il tempo medio di calcolo richiesto per ogni passaggio è quadratico nel numero di cifre." – jason