Fast multiplication

This tip submitted by Jean-François Geyelin on 2005-03-01 05:54:49. It has been viewed 47441 times.
Rating of 6.7 with 261 votes



It is well known that bit shifting enables programmers to do multiplication when dealing with numbers such as 2, 4, 8, 16, 32, 2^n, ...
For instance:
a=a<<4;
equals
a*=16;

But multiplying by 100 (and for many other numbers) is also possible:
a*=100;
equals
a= a*64 + a*32 + a*4;
equals
a=(a<<6)+(a<<5)+(a<<2);

Some compilers might optimise this by themselves.

Finally, when dealing with floats, you can also do fast multiplications by 2,4,5,6 (or by 10,100,1000 depending on the internal representation of the floats) simply by increasing/decreasing the exponent.





More tips

Help your fellow programmers! Add a tip!