Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Optimize integer multiplication with +/-1

Is it possible to optimize multiplication of an integer with -1/1 without using any multiplication and conditionals/branches?

Can it be done only with bitwise operations and integer addition?

Edit: The final goal is to optimize a scalar product of two integer vectors, where one of the vectors has only -1/1 values.

like image 348
Doe Jensen Avatar asked Jan 02 '23 04:01

Doe Jensen


1 Answers

Most modern processors have an ALU with a fast multiplier (meaning it takes about the same time to add two numbers as to multiply them, give or take one CPU clock), so doing anything but for (i=0;i<VectorLength;++i) { p += (x[i] * y[i]) ; } isn't likely to help. However, try a simple if and see if that gives any benefits gained from the CPU's branch prediction:

for (i=0;i<VectorLength;++i) { p += (y[i]<0) ? -x[i] : x[i] ; }

In any case, if the CPU has fast multiply, doing any trick that involves more than one ALU operation (e.g., negation followed by addition, as in some of the examples given here) will more likely cause loss of performance compared to just one multiplication.

like image 65
Leo K Avatar answered Jan 05 '23 19:01

Leo K