binario GCD Algoritmo vs algoritmo de Euclides en las computadoras modernas

Question

http://en.wikipedia.org/wiki/Binary_GCD_algorithm

Esta entrada de Wikipedia tiene una implicación muy poco satisfactoria: el algoritmo binario GCD fue en un tiempo de hasta un 60% más eficiente que el estándar de Euclides Algoritmo, pero como En 1998, Knuth llegó a la conclusión de que solo había un 15% de aumento en la eficiencia en sus computadoras contemporáneas.

Bien, pasaron otros 15 años ... ¿cómo se acumulan estos dos algoritmos hoy con los avances en hardware?

¿El GCD binario continúa superando al algoritmo euclidiano en idiomas de bajo nivel pero languidece debido a su complejidad en lenguajes de nivel superior como Java? ¿O es la diferencia discutible en la informática moderna?

¿Por qué me importa que pueda preguntar? Acabo de tener que procesar como 100 mil millones de estos hoy :) Aquí hay un brindis por vivir en una era de informática (Euclid pobre).

Answer 1

La respuesta es, por supuesto, "depende". Depende del hardware, el compilador, la implementación específica, lo que sea que olvidé. En máquinas con división lenta, el GCD binario tiende a superar al algoritmo euclidiano. Lo comparé hace un par de años en un Pentium4 en C, Java y en algunos otros idiomas, en general en ese punto de referencia, el gcd binario con una tabla de búsqueda de 256 elementos venció al algoritmo euclidiano por un factor de entre 1,6 y casi 3. Euclidiano se acercaron cuando en lugar de dividirse de inmediato, primero se realizaron algunas rondas de resta. No recuerdo las cifras, pero el binario todavía era considerablemente más rápido.

Si la máquina tiene una división rápida, las cosas pueden ser diferentes, ya que el algoritmo euclidiano necesita menos operaciones. Si la diferencia de costo entre división y resta/cambio es lo suficientemente pequeña, el binario será más lento. Cuál es mejor en tus circunstancias, tienes que averiguar haciendo una evaluación comparativa.