http://en.wikipedia.org/wiki/Binary_GCD_algorithmAlgoritmo binario GCD vs algoritmo di Euclide sui computer moderni
Questa voce di Wikipedia ha un'implicazione molto insoddisfacente: l'algoritmo di Binary GCD era un tempo fino al 60% più efficiente rispetto l'algoritmo standard Euclide, ma come Verso la fine del 1998, Knuth concluse che c'era un guadagno di efficienza solo del 15% sui suoi computer contemporanei.
Pozzo altri 15 anni è passato ... come fanno questi due algoritmi impilano oggi con i progressi in hardware?
Il GCD binario continua a sovraperformare l'algoritmo euclideo nei linguaggi di basso livello ma rimane indietro a causa della sua complessità nei linguaggi di livello superiore come Java? O è la differenza contraria al computing moderno?
Perché mi interessa che tu possa chiedere? Mi è capitato di dover processare come 100 miliardi di questi oggi :) Ecco un brindisi per vivere in un'epoca di informatica (povero Euclide).
si può avere un punto di riferimento per testarli, in un solo ciclo (ad esempio dimensioni del 1000) creare un elenco di numeri casuali, e allora per ogni coppia di calcolare numero binario e in un altro ciclo calcolare euclid MCD, ciò che è il problema? IMO, Ancora nei computer moderni il binario dovrebbe essere più veloce specialmente con numeri più grandi. –
Potrei, e sarebbe abbastanza rappresentativo di una particolare lingua su un particolare processore su un particolare sistema operativo. Questa è un'operazione numerica abbastanza comune che ero curioso più in generale di quale fosse la soluzione preferita oggi nelle applicazioni ad alte prestazioni. – jkschneider
Se devi fare 100 miliardi oggi, qualsiasi tempo speso a discutere la soluzione più efficiente ti costerà più tempo perso rispetto all'implementazione dell'uno o dell'altro. –