CODEWITHSUNDEEP
performancecpulow-level
lhk
lhk

Reputation: 30006

What has a better performance: multiplication or division?

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.

Upvotes: 9

Views: 10983

Answers (5)

StarShine
StarShine

Reputation: 2060

One note to make, if you are looking for numerical stability:

Don't recycle the divisions for solutions that require multiple components/coordinates, e.g. like implementing an n-D vector normalize() function, i.e. the following will NOT give you a unit-length vector:

V3d v3d(x,y,z);
float l = v3d.length();
float oneOverL = 1.f / l;
v3d.x *= oneOverL;
v3d.y *= oneOverL;
v3d.z *= oneOverL;
assert(1. == v3d.length()); // fails!

.. but this code will..

V3d v3d(x,y,z);
float l = v3d.length();
v3d.x /= l;
v3d.y /= l;
v3d.z /= l;
assert(1. == v3d.length()); // ok!

Guess the problem in the first code excerpt is the additional float normalization (the pre-division will impose a different scale normalization to the floating point number, which is then forced upon the actual result and introducing additional error).

Didn't look into this for too long, so please share your explanation why this happens. Tested it with x,y and z being .1f (and with doubles instead of floats)

Upvotes: 0

Petr Skocik
Petr Skocik

Reputation: 60056

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

enter image description here

enter image description here

  • 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).

Upvotes: 8

Rahul Tripathi
Rahul Tripathi

Reputation: 172378

Well if it is a single calculation you wil hardly notice any difference but if you talk about millions of transaction then definitely Division is costlier than Multiplication. You can always use whatever is the clearest and readable.

Please refer this link:- Should I use multiplication or division?

Upvotes: 4

Paul R
Paul R

Reputation: 212929

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.

Upvotes: 11

Alan Shutko
Alan Shutko

Reputation: 380

That will likely depend on your specific CPU and the types of your arguments. For instance, in your example you're doing a floating-point multiplication but an integer division. (Probably, at least, in most languages I know of that use C syntax.)

If you are doing work in assembler, you can look up the specific instructions you are using and see how long they take.

If you are not doing work in assembler, you probably don't need to care. All modern compilers with optimization will change your operations in this way to the most appropriate instructions.

Your big wins on optimization will not be from twiddling the arithmetic like this. Instead, focus on how well you are using your cache. Consider whether there are algorithm changes that might speed things up.

Upvotes: 4

Related Questions