2008-10-22 22 views
98

Aquí hay una pregunta tonta y divertida:¿Debo usar multiplicación o división?

Digamos que tenemos que realizar una operación simple donde necesitamos la mitad del valor de una variable. Hay típicamente dos formas de hacer esto:

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

Suponiendo que estamos usando los operadores estándar proporcionados con el lenguaje, lo que uno tiene un mejor rendimiento?

Supongo que la multiplicación suele ser mejor, así que trato de atenerme a eso cuando codigo, pero me gustaría confirmar esto.

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.

+5

¿Ejecutaste un punto de referencia? Solo se trata de una docena de líneas de código. ¿Qué aprendiste al ejecutar un punto de referencia? [Sugerencia: hacer eso hubiera sido más rápido que publicar la pregunta aquí.] –

+0

El comando timeit en IPython es una línea – endolith

+3

Gran pregunta, que ha generado algunas respuestas/discusiones bastante interesantes. Gracias :) – stealthcopter

Respuesta

1

Siempre he aprendido que la multiplicación es más eficiente.

+1

siempre he aprendido a dejar que el compilador lo resuelva. –

+0

"eficiente" es la palabra incorrecta. Es cierto que la mayoría de los procesadores se multiplican más rápido de lo que se dividen. Sin embargo, con las modernas instalaciones de tuberías su programa puede no notar ninguna diferencia. Como muchos otros dicen, realmente estás * mejor * haciendo solo lo que se lee mejor para un ser humano. –

4

Si está trabajando con números enteros o tipos de puntos no flotantes no se olvide de sus operadores bitshifting: < < >>

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

esta optimización se realiza automáticamente detrás de escena en cualquier compilador moderno. –

+0

¿Alguien ha probado si está comprobando (usando operaciones de bits) si un operando (?) Tiene una versión modificable para usarlo en su lugar? función mul (a, b) { if (b es 2) return a << 1; if (b es 4) return a << 2; // ... etc return a * b; } Supongo que el FI es tan caro que sería menos eficiente. –

+0

Eso no se imprimió cerca de lo que imaginaba; No importa. –

4

La multiplicación es por lo general más rápido - ciertamente nunca más lento. Sin embargo, si no es de velocidad crítica, escriba el que sea más claro.

47

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 elegir, 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.

+1

Cuando solía hacer procesadores de radar, una sola operación hizo la diferencia. Pero optimizamos a mano el código de la máquina para lograr un rendimiento en tiempo real. Para todo lo demás, voto por simple y obvio. –

+0

Supongo que, para algunas cosas, podría interesarle una sola operación. Pero yo esperaría que en el 99% de las aplicaciones, no importa. –

+26

Especialmente porque el OP estaba buscando una respuesta en Python. Dudo que cualquier cosa que necesite esa cantidad de eficiencia sea escrita en Python. –

1

He leído 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 con lo que es más fácil de mantener/legible - Odio cuando la gente me dice esto, pero es muy cierto.

0

Bueno, si asumimos que un add/Subtrack costos de operación 1, a continuación, se multiplican los costes 5, y los costos se dividen aproximadamente 20.

+0

¿De dónde obtuviste estos números? ¿experiencia? ¿sensación de la tripa? artículo en internet? ¿cómo cambiarían para diferentes tipos de datos? – kroiz

30

La multiplicación es más rápido, la división es más preciso. Vas a perder cierta 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 se deja la cifra compilador cabo la constante invertida a una precisión perfecta, la respuesta todavía puede ser diferente.

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

El tema de la velocidad no es más que probable que la materia en C/C++ o lenguas JIT, e incluso entonces sólo si la operación está en un bucle en un cuello de botella.

+0

La división es precisa si se divide por números enteros. – plinth

+7

División de punto flotante con denominador> numerador debe introducir valores sin sentido en los bits de orden inferior; la división generalmente reduce la precisión. –

+8

@ S.Lott: No, eso no es cierto. Todas las implementaciones de coma flotante compatibles con IEEE-754 deben redondear perfectamente los resultados de cada operación (es decir, al número de coma flotante más cercano) con respecto al modo de redondeo actual. Multiplicar por el recíproco siempre va a introducir más errores, al menos porque debe ocurrir un redondeo más. – Electro

7

Haga lo que necesite.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.

3

La división de coma 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 el perfil demuestre 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.

1

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

70

Python:

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 

multiplicación es 33% más rápido

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 

=> ninguna 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 sólo un 5% más rápido

conclusiones: en Python es más rápido para multiplicar que repartir, pero a medida que se acerque a la CPU mediante máquinas virtuales más avanzados o equipos conjuntos de investigación, la ventaja desaparece. Es muy posible que una futura máquina virtual de Python lo haga irrelevante

+0

¡Gracias por el consejo sobre el uso del comando de tiempo para la evaluación comparativa! – Edmundito

+2

Su conclusión es incorrecta. Se vuelve más relevante a medida que el JIT/VM mejora. La división se vuelve más lenta en comparación con la menor sobrecarga de la máquina virtual. Recuerde que los compiladores generalmente no pueden optimizar mucho el punto flotante para garantizar la precisión. – rasmus

+5

@rasmus: A medida que el JIT mejora, es más probable que use una instrucción de multiplicación de CPU aunque haya pedido una división. –

8

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

Después de que su programa funcione, descubra qué es lento y hágalo más rápido.

No lo hagas al revés.

61

Siempre use 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 raíz de todos los males. ¡Recuerda siempre las tres reglas de optimización!

  1. No optimizar.
  2. Si usted es un experto, ver regla # 1
  3. Si usted es un experto y puede justificar la necesidad, a continuación, utilizar el siguiente procedimiento:

    • Código que no optimizado
    • determinar qué tan rápido es "Lo suficientemente rápido": tenga en cuenta qué requisito/historia del usuario requiere esa métrica.
    • Escriba una prueba de velocidad
    • Pruebe el código existente - Si es lo suficientemente rápido, listo.
    • Recode optimizado
    • Código de prueba optimizada. SI no cumple con la métrica, deséchela y conserve el original.
    • Si se cumple con la prueba, mantener el código original en como comentarios

También, haciendo cosas como la eliminación de bucles internos cuando no son necesarios o la elección de una lista enlazada a través de una matriz para una inserción ordenar no son optimizaciones, solo programación.

+5

esa no es la cita completa de Knuth; ver http://en.wikipedia.org/wiki/Optimization_(computer_science)#When_to_optimize –

+0

No, hay aproximadamente 40 citas diferentes sobre el tema de diferentes fuentes. Yo como piezas de algunos juntos. –

+0

Su última frase no aclara cuándo aplicar las reglas n. ° 1 y n. ° 2, dejándonos en el lugar donde comenzamos: debemos decidir qué optimizaciones son útiles y cuáles no. Pretender que la respuesta es obvia no es una respuesta. – Matt

2

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

2

Tenga cuidado con "adivinar multiplicación es por lo general mejor, así que trate de cumplir con lo que cuando el código"

En el contexto de esta cuestión específica, mejor aquí significa "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 Floating Point arithmetic with error analysis. Ver Basic Issues in Floating Point Arithmetic and Error Analysis.

Mientras que algunos valores de punto 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, se puede ver que a medida que los valores se hacen más pequeños, la diferencia entre los números casi iguales a crear resultados que no son cero, donde la respuesta correcta es cero.

24

Si desea optimizar su código, pero todavía ser clara, intente esto:

y = x * (1.0/2.0); 

El compilador debe ser capaz de hacer la división en tiempo de compilación, por lo que obtener una multiplicación en 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 coma flotante para calcular la aritmética de coma flotante.

+10

Ese código no está nada claro. –

+9

Muéstrese usted mismo (y quien sea que haya hecho esto) es una práctica estándar en el mundo y el software integrados. los ingenieros en ese campo lo encuentran claro. –

+0

Ho hum, otro -1 hoy sin ningún comentario .... –

17

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

Me 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é aquellos int s a double s (que es lo que probablemente haría pitón), tengo 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 referenciado cualquiera de este código, pero sólo examinando el código puedes ver que usar enteros, división por 2 es más corto que multiplicar por 2. Usando dobles, la multiplicación es más corta porque el compilador usa los códigos de operación de punto flotante del procesador, que probablemente corran más rápido (pero realmente no lo sé) que no usarlos para el sam operación e 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, puede ver que en mi programa main() devuelve a + b. Cuando tomo la palabra clave volátil de distancia, que no sabes lo que el ensamblaje se parece a (excluyendo la configuración del programa):

## 5/2 

## 5*0.5 
## done 

movl $5, %eax 
leave 
ret 

lo hizo tanto en la división, multiplicación y adición 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.

+1

No es una "instrucción única". Simplemente se dobló constantemente. – kvanberendonck

+3

@kvanberendonck Por supuesto, es una sola instrucción. Cuentelos: 'movl \t $ 5,% eax' El nombre de la optimización no es importante ni relevante. Solo quería ser condescendiente con una respuesta de cuatro años. –

+2

La naturaleza de la optimización aún es importante de entender, porque es contextual: solo se aplica si está agregando/multiplicando/dividiendo/etc. Constantes en tiempo de compilación, donde el compilador puede hacer todas las operaciones matemáticas por adelantado y mover la respuesta final a un registro en el tiempo de ejecución. La división es mucho más lenta que la multiplicación en el caso general (divisores de tiempo de ejecución), pero supongo que multiplicar por recíprocos solo ayuda si de todos modos se dividiría por el mismo denominador más de una vez. Probablemente sepa todo eso, pero los programadores más nuevos pueden necesitar que se lo deletree, así que ... por las dudas. –

1

Como en los mensajes # 24 (multiplicación es más rápido) y # 30 - pero a veces ambos son igual de fácil de entender:

1*1e-6F; 

1/1e6F; 

~ puedo encontrar a los dos igual de fácil de leer, y tienen que repítalos miles de millones de veces. Por lo tanto, es útil saber que la multiplicación suele ser más rápida.

1

Android Java, perfilado en el 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 

División es de aproximadamente 20% más rápido que la multiplicación (!)

+1

Para ser realista, debe probar 'a = i * 0.5', no' a * = 0.5'. Así es como la mayoría de los programadores usarán las operaciones. – Blazemonger

-2

técnicamente no hay tal cosa como la división, no es sólo la multiplicación por elementos inversos. Por ejemplo, nunca divide por 2, de hecho se multiplica por 0.5.niño deje de nosotros mismos que existe para un segundo - -

'División' es siempre más difícil que la multiplicación debido a la 'brecha' x por y primero hay que 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}, entonces no calcularlo desde y debe ser una optimización.

+3

Que ignora por completo la realidad de ambos comandos existentes en el silicio. – NPSF3000

+0

@ NPSF3000 - No sigo. Bajo la suposición de que ambas operaciones existen, simplemente afirma que la operación de división implica implícitamente el cálculo de una multiplicación multiplicativa y una multiplicación, que siempre será más difícil que simplemente hacer una sola multiplicación. El silicio es un detalle de implementación. – briantyler

+0

@ BTyler. Si ambos comandos existen en el silicio, y ambos comandos toman el mismo número de ciclos [como uno esperaría] que cuán relativamente complejas son las instrucciones es completamente irrelevante desde un POV de rendimiento. – NPSF3000

1

Existe 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 W3530 Xeon, VS2010:

  • Multiplicación: 5,33
  • División: 21,05

Parece que en VS2003 una división en un bucle (múltiple lo que se utilizó el divisor veces) fue traducido a 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

+0

Me pregunto si hay alguna razón por la que un compilador no pueda reemplazar, p. 'n/10.0' con una expresión de la forma' (n * c1 + n * c2) '? Yo esperaría que en la mayoría de los procesadores una división tome más de dos multiplicaciones y una división, y creo que la división por cualquier constante puede arrojar un resultado correctamente redondeado en todos los casos usando la formulación indicada. – supercat

4

En realidad hay una buena razón por la que, como regla general del pulgar multiplicación será más rápido que la división. La división de punto flotante en el hardware se realiza con algoritmos de resta condicional y de cambio ("división larga" con números binarios) o, lo más probable en la actualidad, con iteraciones como el 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. Sin embargo, en general, si está codificando un bucle interno en una parte sensible de un programa, escribir 0.5 * x o 1.0/2.0 * x en lugar de x/2.0 es algo razonable de hacer. 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.

0

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 piotrk y gast128) y el compilador (cf las pruebas @Javier). 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!

6

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

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

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

Dividir para tener una tubería significativamente más largo que se multiplican. 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.

El tiempo que 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 mira 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, caché, puestos de ramificación, predicciones fuera de orden y dependencias de tuberías. 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.