What has a better performance: multiplication or division?

Question

Which version is faster: x * 0.5 or x / 2 ?

I've had a course at the university called computer systems some time ago. From back then I remember that multiplying two values can be achieved with comparably "simple" logical gates but division is not a "native" operation and requires a sum register that is in a loop increased by the divisor and compared to the dividend.

Now I have to optimise an algorithm with a lot of divisions. Unfortunately it's not just dividing by two, so binary shifting is not an option. Will it make a difference to change all divisions to multiplications ?

Update:

I have changed my code and didn't notice any difference. You're probably right about compiler optimisations. Since all the answers were great ive upvoted them all. I chose rahul's answer because of the great link.

Answer 1

Usually division is a lot more expensive than multiplication, but a smart compiler will often convert division by a compile-time constant to a multiplication anyway. If your compiler is not smart enough though, or if there are floating point accuracy issues, then you can always do the optimisation explicitly, e.g. change:

 float x = y / 2.5f;

to:

 const float k = 1.0f / 2.5f;

 ...

 float x = y * k;

Note that this is most likely a case of premature optimisation - you should only do this kind of thing if you have profiled your code and positively identified division as being a performance bottlneck.

Answer 2

Division by a compile-time constant that's a power of 2 is quite fast (comparable to multiplication by a compile-time constant) for both integers and floats (it's basically convertible into a bit shift).

For floats even dynamic division by powers of two is much faster than regular (dynamic or static division) as it basically turns into a subtraction on its exponent.

In all other cases, division appears to be several times slower than multiplication.

For dynamic divisor the slowndown factor at my Intel(R) Core(TM) i5 CPU M 430 @ 2.27GHz appears to be about 8, for static ones about 2.

The results are from a little benchmark of mine, which I made because I was somewhat curious about this (notice the aberrations at powers of two) :

• ulong -- 64 bit unsigned
• 1 in the label means dynamic argument
• 0 in the lable means statically known argument

The results were generated from the following bash template:

#include <stdio.h>
#include <stdlib.h>
typedef unsigned long ulong;
int main(int argc, char** argv){
    $TYPE arg = atoi(argv[1]);
    $TYPE i = 0, res = 0;
    for (i=0;i< $IT;i++)
        res+=i $OP $ARG;
    printf($FMT, res);
    return 0;
}

with the $-variables assigned and the resulting program compiled with -O3 and run (dynamic values came from the command line as it's obvious from the C code).