¿Debería usar multiplicación o división?

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. Por lo general, hay 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 idioma, ¿cuál tiene mejor rendimiento?

Supongo que la multiplicación suele ser mejor, así que trato de ceñirme a eso cuando codifico, 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 sofisticadas (como usar operadores de desplazamiento bit a bit) también.

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 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

=> 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 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 utilizando máquinas virtuales o JIT más avanzadas, la ventaja desaparece. Es muy posible que una futura máquina virtual de Python lo haga irrelevante

Utilice siempre lo que sea más claro. Cualquier otra cosa que haga es intentar burlar al compilador. Si el compilador es inteligente, hará todo lo posible para optimizar el resultado, pero nada puede hacer que el próximo chico no te odie por tu pésima solución de desplazamiento 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. ¡Recuerde siempre las tres reglas de optimización!

1. No optimices.
2. Si es un experto, consulte la regla n. ° 1

3. Si es un experto y puede justificar la necesidad, utilice el siguiente procedimiento:

   • Codifíquelo sin optimizar
   • Determine qué tan rápido es "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, ya está.
   • Recodificarlo optimizado
   • Pruebe el código optimizado. SI no cumple con la métrica, deséchelo y conserve el original.
   • Si cumple con la prueba, mantenga el código original como comentarios

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

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

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

La multiplicación es más rápida, la división es más precisa. Perderás algo de precisión si tu 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 deja que el compilador averigüe 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

Es probable que el problema de la velocidad solo importe en los lenguajes C / C ++ o JIT, e incluso entonces solo si la operación está en un bucle en un cuello de botella.

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á una multiplicación en tiempo de ejecución. Espero que la precisión sea la misma que en el y = x / 2.0caso.

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

Solo voy a agregar algo para la opción "otros idiomas".
C: Dado que este es solo un ejercicio académico que realmente no hace ninguna diferencia, pensé en contribuir 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é esos intsa doubles (que es lo que probablemente haría Python), 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 este código, 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 punto flotante del procesador, que probablemente corran más rápido (pero en realidad no lo sé) que no usarlos para la misma operación. Entonces, 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ía preocuparse, excepto en términos de legibilidad.

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

## 5/2

## 5*0.5
## done

movl    $5, %eax
leave
ret

¡Hizo tanto 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 respetable.

Perdón por la respuesta demasiado larga.

En primer lugar, a menos que esté trabajando en C o ASSEMBLY, probablemente esté en un lenguaje de nivel superior donde la memoria se atasca y los gastos generales de llamadas empequeñecerán absolutamente la diferencia entre multiplicar y dividir hasta el punto de la irrelevancia. Entonces, elija lo que se lea mejor en ese caso.

Si habla desde un nivel muy alto, no será mucho más lento para cualquier cosa para la que probablemente lo use. Verá en otras respuestas, las personas necesitan hacer un millón de multiplicar / dividir solo para medir una diferencia de menos de milisegundos entre los dos.

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

El dividendo tiende a tener una tubería significativamente más larga que la multiplicación. 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 terminará costando más que una multiplicación.

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

Una analogía es poner un pastel en el microondas mientras miras un programa de televisión. El tiempo total que te alejó del programa de televisión es cuánto tiempo fue ponerlo en el microondas y sacarlo del microondas. El resto del tiempo seguía viendo el programa de televisión. Entonces, si el pastel tardó 10 minutos en cocinarse en lugar de 1 minuto, en realidad no consumió más tiempo de ver televisión.

En la práctica, si va a llegar al nivel de preocuparse por la diferencia entre Multiplicar y Dividir, debe comprender las canalizaciones, la memoria caché, las paradas de rama, la predicción fuera de orden y las dependencias de las canalizaciones. Si esto no suena como lo que pretendías ir con esta pregunta, entonces la respuesta correcta es ignorar la diferencia entre las dos.

Hace muchos (muchos) años era absolutamente crítico evitar las divisiones y usar siempre multiplicaciones, pero en ese entonces los golpes de memoria eran menos relevantes y las divisiones eran mucho peores. En estos días, califico la legibilidad más alto, pero si no hay diferencia de legibilidad, creo que es un buen hábito optar por multiplicar.

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

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

No lo hagas al revés.

Haz lo que necesites. Piense primero 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.

Si está trabajando con enteros o tipos de punto no flotante, no olvide sus operadores de desplazamiento de bits: << >>

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

En realidad, hay una buena razón por la que, como regla general, la multiplicación será más rápida que la división. La división de punto flotante en hardware se realiza con algoritmos de sustracción condicional y de desplazamiento ("división larga" con números binarios) o, más probablemente en estos días, con iteraciones como el algoritmo de Goldschmidt . Desplazar y restar necesita al menos un ciclo por bit de precisión (las iteraciones son casi imposibles de paralelizar al igual que el desplazamiento y suma 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 requiera más ciclos. Por supuesto, esto no tiene en cuenta 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 al tiempo de un programa, escribir 0.5 * xo 1.0/2.0 * xmás bien x / 2.0es algo razonable. La pedantería de "codificar lo que es más claro" es absolutamente cierta, pero los tres son tan cercanos en legibilidad que la pedantería en este caso es simplemente pedante.

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

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

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, probablemente sea más rápida que la división de punto flotante.

Pero estoy más inclinado a responder "realmente no importa", a menos que el perfil haya demostrado que la división es un cuello de botella frente a la multiplicación. Sin embargo, supongo que la elección de la multiplicación frente a la división no tendrá un gran impacto en el rendimiento de su aplicación.

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

Tenga cuidado con "adivinar que la multiplicación suele ser mejor, así que trato de ceñirme a eso cuando codifico".

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.

Consulte Aritmética de coma flotante con análisis de errores . Consulte Problemas básicos en aritmética de coma flotante y análisis de errores .

Si bien 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) dominan 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 vuelven más pequeños, la diferencia entre números casi iguales crea resultados distintos de cero donde la respuesta correcta es cero.

Leí en alguna parte que la multiplicación es más eficiente en C / C ++; No tengo idea sobre los idiomas interpretados; la diferencia probablemente sea insignificante debido a todos los demás gastos generales.

A menos que se convierta en un problema, quédese con lo que es más fácil de mantener / legible; odio cuando la gente me dice esto, pero es tan cierto.

Sugeriría la multiplicación en general, porque no tienes que gastar los ciclos asegurándote de que tu divisor no sea 0. Esto no se aplica, por supuesto, si tu divisor es una constante.

Android Java, 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 (!)

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

1*1e-6F;

1/1e6F;

~ Encuentro que ambos son igualmente fáciles de leer y tengo que repetirlos miles de millones de veces. Por eso es útil saber que la multiplicación suele ser más rápida.

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

En un Pentium 4, 2,8 GHz, frente a 2003:

• 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 vs2003 una división en un bucle (por lo que el divisor se usó varias veces) se tradujo 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 sea 0.0. No conozco el algoritmo preciso cableado en el chip, pero tal vez dependa del número.

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

Aquí hay una respuesta tonta y divertida:

x / 2.0 no es equivalente ax * 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, aprende que puede optimizar este código. Se hace referencia al método en cientos de fórmulas a lo largo de su aplicación. Así que lo cambia y experimenta una notable mejora del rendimiento del 5%.

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

¿Fue la decisión correcta cambiar el código? En matemáticas, las dos expresiones son equivalentes. En informática, eso no siempre es cierto. Lea Minimizar el efecto de los problemas de precisión para obtener más detalles. Si sus valores calculados se comparan, en algún momento, 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 conclusión es; una vez que te conformes con cualquiera de los dos, ¡apégate a ello!

Bueno, si asumimos que una operación de suma / resta cuesta 1, entonces multiplique los costos 5 y divida los costos alrededor de 20.

Después de una discusión tan larga e interesante, aquí está mi opinión sobre esto: no hay una respuesta final a esta pregunta. Como algunas personas señalaron, depende tanto del hardware (cf piotrk y gast128 ) como del compilador (cf las pruebas de @Javier ). Si la velocidad no es crítica, si su aplicación no necesita procesar en tiempo real una gran cantidad de datos, 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 podría 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 mayor claridad del código, ¡un solo comentario haría el trabajo!

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

'División' - engañémonos a nosotros mismos que existe por un segundo - siempre es más difícil que la multiplicación porque para 'dividir' xpor yuno primero se necesita calcular el valor y^{-1}tal que y*y^{-1} = 1y luego hacer la multiplicación x*y^{-1}. Si ya lo sabe, y^{-1}entonces no calcularlo ydebe ser una optimización.