performance - signos - ¿Debería usar multiplicación o división?

multiplicaciones (25)

Aquí hay una pregunta tonta y divertida:

Digamos que tenemos que realizar una operación simple donde necesitamos la mitad del valor de una variable. Generalmente hay dos formas de hacer esto:

y = x / 2.0; // or... y = x * 0.5;

Suponiendo que estamos utilizando los operadores estándar proporcionados con el idioma, ¿cuál tiene un mejor rendimiento?

Supongo que la multiplicación suele ser mejor, así que intento seguir así cuando codigo, pero me gustaría confirmarlo.

Aunque personalmente estoy interesado en la respuesta para Python 2.4-2.5, no dude en publicar una respuesta para otros idiomas. Y si lo desea, no dude en publicar otras formas más elegantes (como usar operadores de turnos bit a bit) también.

Al igual que con las publicaciones n. ° 24 (la multiplicación es más rápida) y la n. ° 30, pero a veces ambas son igualmente fáciles de entender:

1*1e-6F; 1/1e6F;

~ Los encuentro tan fáciles de leer, y tengo que repetirlos miles de millones de veces. Por lo tanto, es útil saber que la multiplicación suele ser más rápida.

Aquí hay una respuesta tonta y divertida:

x / 2.0 no es equivalente a x * 0.5

Digamos que escribió este método el 22 de octubre de 2008.

double half(double x) => x / 2.0;

Ahora, 10 años después, aprendes que puedes optimizar esta pieza de código. El método se referencia en cientos de fórmulas en toda su aplicación. Entonces lo cambias y experimentas una notable mejora del 5% en el rendimiento.

double half(double x) => x * 0.5;

¿Fue la decisión correcta cambiar el código? En matemáticas, las dos expresiones son de hecho equivalentes. En informática, eso no siempre es cierto. Por favor, lea Minimizando el efecto de los problemas de precisión para más detalles. Si sus valores calculados son, en algún momento, comparados con otros valores, cambiará el resultado de los casos extremos. P.ej:

double quantize(double x) { if (half(x) > threshold)) return 1; else return -1; }

La línea de fondo es; una vez que te conformes con cualquiera de los dos, ¡entonces mantente firme!

Bueno, si suponemos que una operación de adición / subllamada cuesta 1, multiplique los costos 5 y divida los costos en aproximadamente 20.

Creo que esto se está volviendo tan insignificante que sería mejor que hicieras lo que sea que haga que el código sea más legible. A menos que realice miles de operaciones, si no millones, de veces, dudo que alguien note la diferencia.

Si realmente tiene que hacer la elección, la evaluación comparativa es el único camino a seguir. Encuentre qué función (es) le está causando problemas, luego descubra en qué parte de la función se producen los problemas y corrija esas secciones. Sin embargo, todavía dudo de que una sola operación matemática (incluso una repetida muchas, muchas veces) sea la causa de cualquier cuello de botella.

Después de una discusión tan larga e interesante, aquí está mi opinión sobre esto: no hay una respuesta definitiva a esta pregunta. Como algunas personas señalaron, depende de ambos, el hardware (cf y ) y el compilador (cf las pruebas de ). Si la velocidad no es crítica, si su aplicación no necesita procesar en gran cantidad de datos en tiempo real, puede optar por la claridad usando una división, mientras que si la velocidad de procesamiento o la carga del procesador son un problema, la multiplicación puede ser la más segura. Finalmente, a menos que sepa exactamente en qué plataforma se implementará su aplicación, el punto de referencia no tiene sentido. Y para la claridad del código, ¡un solo comentario haría el trabajo!

En primer lugar, a menos que trabaje en C o ASSEMBLY, probablemente se encuentre en un lenguaje de nivel superior en el que los puestos de memoria y los gastos generales generales anularán por completo la diferencia entre multiplicar y dividir hasta el punto de irrelevancia. Por lo tanto, solo elige qué lee mejor en ese caso.

Si hablas desde un nivel muy alto, no será mucho más lento para cualquier cosa que puedas usar. Verá en otras respuestas, la gente necesita multiplicar / dividir un millón solo para medir una diferencia de menos de milisegundos entre las dos.

Si todavía tiene curiosidad, desde un punto de vista de optimización de bajo nivel:

Divide tiende a tener una tubería significativamente más larga que multiplicar. Esto significa que se necesita más tiempo para obtener el resultado, pero si puede mantener el procesador ocupado con tareas no dependientes, entonces no le costará más de un múltiplo.

La duración de la diferencia de la tubería depende completamente del hardware. El último hardware que utilicé fue algo así como 9 ciclos para una FPU multiplicada y 50 ciclos para una FPU dividida. Suena mucho, pero luego perderías 1000 ciclos por un error de memoria, de modo que puede poner las cosas en perspectiva.

Una analogía es poner un pastel en el microondas mientras ves un programa de televisión. El tiempo total que lo alejó del programa de TV es cuánto tiempo lo puso en el microondas y lo sacó del microondas. El resto de tu tiempo aún viste el programa de TV. Entonces, si el pastel tardó 10 minutos en cocinarse en lugar de 1 minuto, en realidad no consumió más tiempo de la televisión.

En la práctica, si va a llegar al nivel de preocupación por la diferencia entre Multiplicar y Dividir, necesita comprender las tuberías, la memoria caché, los puestos de sucursales, la predicción fuera de servicio y las dependencias de interconexión. Si esto no suena como lo que pretendía hacer con esta pregunta, entonces la respuesta correcta es ignorar la diferencia entre los dos.

Muchos (muchos) años atrás era absolutamente crítico evitar divisiones y usar siempre multiplicaciones, pero en aquel entonces los aciertos de memoria eran menos relevantes y las divisiones eran mucho peores. Estos días califico la legibilidad más alta, pero si no hay diferencia de legibilidad, creo que es una buena costumbre optar por las multiplicaciones.

En realidad, hay una buena razón para que, como regla general, la multiplicación sea más rápida que la división. La división de puntos flotantes en el hardware se realiza con algoritmos de restas condicional y de desplazamiento ("división larga" con números binarios) o, lo más probable en la actualidad, con iteraciones como Goldschmidt''s algoritmo Goldschmidt''s . Shift y resta necesita al menos un ciclo por cada bit de precisión (las iteraciones son casi imposibles de paralelizar como lo son el cambio y el agregado de la multiplicación), y los algoritmos iterativos hacen al menos una multiplicación por iteración . En cualquier caso, es muy probable que la división tome más ciclos. Por supuesto, esto no explica las peculiaridades de los compiladores, el movimiento de datos o la precisión. En general, sin embargo, si está codificando un bucle interno en una parte sensible de un programa, es razonable escribir 0.5 * x o 1.0/2.0 * x lugar de x / 2.0 . La pedantería del "código que es más claro" es absolutamente cierto, pero los tres están tan cerca de la legibilidad que la pedantería es en este caso simplemente pedante.

Escriba el que indique más claramente su intención.

Después de que tu programa funcione, averigua qué es lento y hazlo más rápido.

No lo hagas al revés.

Esto se convierte en una cuestión más cuando estás programando en ensamble o quizás C. Me imagino que con la mayoría de los lenguajes modernos esa optimización se está haciendo por mí.

Hay una diferencia, pero depende del compilador. Al principio en vs2003 (c ++) no obtuve ninguna diferencia significativa para los tipos dobles (punto flotante de 64 bits). Sin embargo, volviendo a ejecutar las pruebas en el vs2010, detecté una gran diferencia, hasta un factor 4 más rápido para las multiplicaciones. Siguiendo esto, parece que vs2003 y vs2010 generan un código de fpu diferente.

En un Pentium 4, 2.8 GHz, vs2003:

Multiplicación: 8.09
División: 7.97

En un Xeon W3530, vs2003:

Multiplicación: 4.68
División: 4.64

En un Xeon W3530, vs2010:

Multiplicación: 5.33
División: 21.05

Parece que en el vs2003 una división en un bucle (por lo que el divisor se usó varias veces) se tradujo en una multiplicación con el inverso. En vs2010 esta optimización ya no se aplica (supongo que porque hay un resultado ligeramente diferente entre los dos métodos). Tenga en cuenta también que la CPU realiza divisiones más rápido tan pronto como su numerador es 0.0. No sé el algoritmo preciso cableado en el chip, pero tal vez depende del número.

Editar 18-03-2013: la observación de vs2010

Haz lo que necesites. Primero piense en su lector, no se preocupe por el rendimiento hasta que esté seguro de que tiene un problema de rendimiento.

Deje que el compilador haga el rendimiento por usted.

He leído en alguna parte que la multiplicación es más eficiente en C / C ++; No hay idea con respecto a los idiomas interpretados: la diferencia es probablemente insignificante debido a todos los otros gastos generales.

A menos que se convierta en un problema quedarse con lo que es más fácil de mantener / legible. Odio cuando la gente me dice esto, pero es muy cierto.

Java android, perfilado en Samsung GT-S5830

public void Mutiplication() { float a = 1.0f; for(int i=0; i<1000000; i++) { a *= 0.5f; } } public void Division() { float a = 1.0f; for(int i=0; i<1000000; i++) { a /= 2.0f; } }

Resultados?

Multiplications(): time/call: 1524.375 ms Division(): time/call: 1220.003 ms

La división es aproximadamente un 20% más rápida que la multiplicación (!)

La división de punto flotante es (generalmente) especialmente lenta, por lo que aunque la multiplicación de punto flotante también es relativamente lenta, es probablemente más rápida que la división de coma flotante.

Pero estoy más inclinado a responder "en realidad no importa", a menos que los perfiles hayan demostrado que la división es un poco cuello de botella frente a la multiplicación. Supongo, sin embargo, que la elección de la multiplicación contra la división no tendrá un gran impacto en el rendimiento de su aplicación.

La multiplicación es más rápida, la división es más precisa. Perderá algo de precisión si su número no es una potencia de 2:

y = x / 3.0; y = x * 0.333333; // how many 3''s should there be, and how will the compiler round?

Incluso si dejas que el compilador descubra la constante invertida con precisión perfecta, la respuesta puede ser diferente.

x = 100.0; x / 3.0 == x * (1.0/3.0) // is false in the test I just performed

El problema de la velocidad solo es importante en C / C ++ o en los idiomas JIT, e incluso solo si la operación está en un bucle en un cuello de botella.

La multiplicación suele ser más rápida, sin duda nunca más lenta. Sin embargo, si no es crítico para la velocidad, escriba el que sea más claro.

Pitón:

time python -c ''for i in xrange(int(1e8)): t=12341234234.234 / 2.0'' real 0m26.676s user 0m25.154s sys 0m0.076s time python -c ''for i in xrange(int(1e8)): t=12341234234.234 * 0.5'' real 0m17.932s user 0m16.481s sys 0m0.048s

la multiplicación es un 33% más rápida

Lua:

time lua -e ''for i=1,1e8 do t=12341234234.234 / 2.0 end'' real 0m7.956s user 0m7.332s sys 0m0.032s time lua -e ''for i=1,1e8 do t=12341234234.234 * 0.5 end'' real 0m7.997s user 0m7.516s sys 0m0.036s

=> sin diferencia real

LuaJIT:

time luajit -O -e ''for i=1,1e8 do t=12341234234.234 / 2.0 end'' real 0m1.921s user 0m1.668s sys 0m0.004s time luajit -O -e ''for i=1,1e8 do t=12341234234.234 * 0.5 end'' real 0m1.843s user 0m1.676s sys 0m0.000s

=> es solo un 5% más rápido

Conclusiones: en Python es más rápido multiplicar que dividir, pero a medida que te acercas a la CPU con VM más avanzadas o JIT, la ventaja desaparece. Es muy posible que una futura máquina virtual de Python lo haga irrelevante

Si desea optimizar su código pero aún así ser claro, intente esto:

y = x * (1.0 / 2.0);

El compilador debería poder dividir en tiempo de compilación, por lo que obtendrás una multiplicación en el tiempo de ejecución. Esperaría que la precisión sea la misma que en el caso y = x / 2.0 .

Donde esto puede importar, MUCHO es en procesadores integrados donde se requiere emulación de punto flotante para calcular la aritmética de coma flotante.

Si está trabajando con números enteros o no flotantes, no olvide los operadores de cambio de bits: << >>

int y = 10; y = y >> 1; Console.WriteLine("value halved: " + y); y = y << 1; Console.WriteLine("now value doubled: " + y);

Siempre aprendí que la multiplicación es más eficiente.

Siempre usa lo que sea más claro. Cualquier otra cosa que hagas es tratar de burlar al compilador. Si el compilador es en absoluto inteligente, hará lo mejor para optimizar el resultado, pero nada puede hacer que el siguiente tipo no lo odie por su mala solución de cambio de bits (me encanta la manipulación de bits por cierto, es divertido. ¡Pero divertido! = Legible )

La optimización prematura es la fuente de todos los males. ¡Recuerda siempre las tres reglas de optimización!

No optimizar
Si eres un experto, mira la regla # 1
Si usted es un experto y puede justificar la necesidad, entonces use el siguiente procedimiento:
- Codifíquelo sin optimizar
- determinar qué tan rápido es "lo suficientemente rápido" - Tenga en cuenta qué requisito / historia del usuario requiere esa métrica.
- Escribe una prueba de velocidad
- Pruebe el código existente: si es lo suficientemente rápido, listo.
- Recode optimizado
- Prueba de código optimizado SI no cumple con la métrica, deséchela y conserve el original.
- Si cumple con la prueba, guarde el código original como comentarios

Además, hacer cosas como eliminar los bucles internos cuando no son necesarios o elegir una lista vinculada en una matriz para una ordenación por inserción no son optimizaciones, solo programación.

Solo voy a agregar algo para la opción "otros idiomas".
C: Como esto es solo un ejercicio académico que realmente no hace diferencia, pensé que contribuiría con algo diferente.

Compilé para ensamblar sin optimizaciones y miré el resultado.
El código:

int main() { volatile int a; volatile int b; asm("## 5/2/n"); a = 5; a = a / 2; asm("## 5*0.5"); b = 5; b = b * 0.5; asm("## done"); return a + b; }

compilado con gcc tdiv.c -O1 -o tdiv.s -S

la división por 2:

movl $5, -4(%ebp) movl -4(%ebp), %eax movl %eax, %edx shrl $31, %edx addl %edx, %eax sarl %eax movl %eax, -4(%ebp)

y la multiplicación por 0.5:

movl $5, -8(%ebp) movl -8(%ebp), %eax pushl %eax fildl (%esp) leal 4(%esp), %esp fmuls LC0 fnstcw -10(%ebp) movzwl -10(%ebp), %eax orw $3072, %ax movw %ax, -12(%ebp) fldcw -12(%ebp) fistpl -16(%ebp) fldcw -10(%ebp) movl -16(%ebp), %eax movl %eax, -8(%ebp)

Sin embargo, cuando cambié esas int s a double s (que es lo que python probablemente haría), obtuve esto:

división:

flds LC0 fstl -8(%ebp) fldl -8(%ebp) flds LC1 fmul %st, %st(1) fxch %st(1) fstpl -8(%ebp) fxch %st(1)

multiplicación:

fstpl -16(%ebp) fldl -16(%ebp) fmulp %st, %st(1) fstpl -16(%ebp)

No he comparado ninguno de estos códigos, pero con solo examinar el código puede ver que al usar números enteros, la división por 2 es más corta que la multiplicación por 2. Al usar dobles, la multiplicación es más corta porque el compilador usa los códigos de operación de coma flotante del procesador, que probablemente corra más rápido (pero en realidad no lo sé) que no usarlos para la misma operación. Así que, en última instancia, esta respuesta ha demostrado que el rendimiento de la multiplacción por 0.5 frente a la división por 2 depende de la implementación del lenguaje y la plataforma en la que se ejecuta. En última instancia, la diferencia es insignificante y es algo de lo que prácticamente nunca deberías preocuparte, excepto en términos de legibilidad.

Como nota al margen, puedes ver que en mi programa main() devuelve a + b . Cuando elimino la palabra clave volátil, nunca adivinará cómo se ve el ensamblaje (excluida la configuración del programa):

## 5/2 ## 5*0.5 ## done movl $5, %eax leave ret

hizo la división, la multiplicación y la suma en una sola instrucción. Claramente, no tiene que preocuparse por esto si el optimizador es de algún tipo respetable.

Perdón por la respuesta demasiado larga.

Sugeriría la multiplicación en general, porque no tiene que gastar los ciclos para asegurarse de que su divisor no sea 0. Esto no se aplica, por supuesto, si su divisor es una constante.

Técnicamente no existe la división, solo hay multiplicación por elementos inversos. Por ejemplo, nunca divide por 2, de hecho se multiplica por 0.5.

''División'' - engañémonos de que existe por un segundo - siempre es más difícil esa multiplicación porque para ''dividir'' x por y uno primero necesita calcular el valor y^{-1} tal que y*y^{-1} = 1 y luego hacer la multiplicación x*y^{-1} . Si ya conoce y^{-1} , no calcularlo desde y debe ser una optimización.

Tenga cuidado con "adivinar la multiplicación generalmente es mejor, así que intento mantener eso cuando codigo"

En el contexto de esta pregunta específica, mejor aquí significa "más rápido". Lo cual no es muy útil.

Pensar en la velocidad puede ser un grave error. Hay profundas implicaciones de error en la forma algebraica específica del cálculo.

Ver aritmética de punto flotante con análisis de error . Consulte Problemas básicos en Aritmética de puntos flotantes y Análisis de errores .

Mientras que algunos valores de coma flotante son exactos, la mayoría de los valores de coma flotante son una aproximación; son un valor ideal más algún error. Cada operación se aplica al valor ideal y al valor de error.

Los mayores problemas provienen de tratar de manipular dos números casi iguales. Los bits más a la derecha (los bits de error) llegan a dominar los resultados.

>>> for i in range(7): ... a=1/(10.0**i) ... b=(1/10.0)**i ... print i, a, b, a-b ... 0 1.0 1.0 0.0 1 0.1 0.1 0.0 2 0.01 0.01 -1.73472347598e-18 3 0.001 0.001 -2.16840434497e-19 4 0.0001 0.0001 -1.35525271561e-20 5 1e-05 1e-05 -1.69406589451e-21 6 1e-06 1e-06 -4.23516473627e-22

En este ejemplo, puede ver que a medida que los valores se hacen más pequeños, la diferencia entre números casi iguales crea resultados distintos de cero donde la respuesta correcta es cero.