¿Por qué multiplicar es más barato que dividir?

Question

Hace poco escribí una clase Vector 3, y envié mi función normalize() para su revisión a un amigo. Dijo que era bueno, pero que debería multiplicar por lo recíproco donde sea posible porque "multiplicar es más barato que dividir" en tiempo de CPU.

Mi pregunta simplemente es, ¿por qué es eso?

Answer 1

Piénselo en términos de operaciones elementales que el hardware puede implementar más fácilmente: sumar, restar, cambiar, comparar. La multiplicación incluso en una configuración trivial requiere menos pasos elementales de este tipo; además, permite avances de algoritmos que son aún más rápidos; consulte here por ejemplo ... pero el hardware generalmente no los aprovecha (excepto quizás hardware extremadamente especializado). Por ejemplo, como dice la URL de wikipedia, "Toom-Cook puede hacer una multiplicación de N en cubos de tamaño por el costo de cinco multiplicaciones de tamaño N", eso es bastante rápido para números muy grandes (el algoritmo de Fürer, un desarrollo bastante reciente, puede hacer Θ(n ln(n) 2Θ(ln*(n))) - de nuevo, vea la página de wikipedia y enlaces desde allí).

La división es intrínsicamente más lenta, como - otra vez - por wikipedia; incluso los mejores algoritmos (algunos de los cuales están implementados en HW, simplemente porque no son tan sofisticados y complejos como los mejores algoritmos para la multiplicación ;-) no pueden contener una vela a los de multiplicación.

Solo para cuantificar el problema con números no tan grandes, estos son algunos resultados con gmpy, un contenedor de Python fácil de usar alrededor de GMP, que tiende a tener implementaciones de aritmética bastante buenas, aunque no necesariamente las últimas- y-mayores sibilancias. En un lento (de primera generación ;-) Macbook Pro:

$ python -mtimeit -s'import gmpy as g; a=g.mpf(198792823083408); b=g.mpf(7230824083); ib=1.0/b' 'a*ib' 
1000000 loops, best of 3: 0.186 usec per loop 
$ python -mtimeit -s'import gmpy as g; a=g.mpf(198792823083408); b=g.mpf(7230824083); ib=1.0/b' 'a/b' 
1000000 loops, best of 3: 0.276 usec per loop 

Como se ve, incluso en este pequeño tamaño (número de bits de los números), y con las bibliotecas optimizadas por la gente exactamente la misma velocidad obsesionado , la multiplicación por el recíproco puede ahorrar 1/3 del tiempo que toma la división.

Puede ser sólo en raras ocasiones que estos pocos nanosegundos son una cuestión de vida o muerte, pero, cuando son, y por supuesto si se están dividiendo en varias ocasiones por el mismo valor (para amortizar distancia del 1.0/b operación!), entonces este conocimiento puede ser un salvavidas.

(Gran parte de la misma vena - x*x a menudo ahorrar tiempo en comparación con x**2 [en idiomas que tiene un operador de ** "elevar al poder", como Python y Fortran] - Horner y de scheme para el cálculo polinomio es mucho más preferible a repetidas operaciones de aumento de potencia! -).

Answer 2

El funcionamiento de la CPU para la división (flotante) es mucho más complicado que la multiplicación. La CPU tiene que hacer más. Estoy lejos de tener conocimientos sobre hardware, pero puede encontrar mucha información sobre la implementación de divisiones comunes (basada en algoritmos newton-raphson, por ejemplo).

También tendría cuidado de usar siempre la multiplicación del recíproco en lugar de la división para obtener el rendimiento de la CPU: es posible que no den exactamente los mismos resultados. Esto puede o no importar dependiendo de su aplicación.

Answer 3

Si piensas en la escuela primaria, recordarás que la multiplicación fue más difícil que la suma y la división fue más difícil que la multiplicación. Las cosas no son diferentes para la CPU.

Recuerde también que el cálculo del recíproco implica una división, por lo tanto, a menos que calcule el recíproco una vez y lo use tres veces, no verá una aceleración.