Aaron Lager, Panamax Furman, Santa Rosa, CA; Edited by Charles H Small and Fran Granville -- EDN, 5/29/2008

This Design Idea presents a method for fast integer multiplying and multiplying by fractions.

What can you do when you lack access to a hardware multiplier or MAC (multiply/accumulate) function and you need to multiply by something other than a power of two?

One option is to include the math.h function and just sling around the multiplication operator and watch your code bloat and slow to a crawl. Option two is to get fancy with bit shifting.

The general idea is to find powers of two, including zero, that you can add to achieve the multiplier you need. This method works because of the distributive properties of multiplication.

Using the distributive properties of multiplication, you can, for example, rearrange the problem of: 12×12=144?(4+8)×12=144?(12×4)+(12×8)=144.

This version is amenable to implementation in C code because four and eight are powers of two. To implement the multiplications, you use the exponent of the power-of-two representation for your code as an integer shift. Because 4=22 and 8=23, you use two and three as your shift factors.

• For example, multiply the variable foo by 12 to get 144: BYTE foo=12: foo=((foo<<3)+(foo<<2)). Left-shifting by three is the same as multiplying by eight, and left-shifting by two is the same as multiplying by four.
• Another example is multiplying by six: 6×10=60?(2+4)×10=60?(2×10)+(4×10)=60. BYTE foo=10; foo=((foo<<1)+(foo<<2)). Left-shifting by one is the same as multiplying by two, and left-shifting by two is the same as multiplying by four.

Using this same theory of distribution, you can also perform fractional multiplication or division. This method creates rounding errors just like dividing integers by values that are not powers of two does with math.h functions and the division operator.

• One example is 2.5×10=25?(2+0.5)×10=25?(2×10)+(0.5×10)=25. The result is ((foo<<1)+(foo>>1)). Left-shifting by one is the same as multiplying by two, and right-shifting by one is the same as dividing by two or multiplying by 0.5.
• Another example is 3.125×80=250?(2+1+0.125)×80=250?(2×80)+(1×80)+(0.125×80)=250. The result is ((foo<<1)+foo+(foo>>3)). Left-shifting by one is the same as multiplying by two, multiplying by one is the same as adding the multiplicand once to the result, and right-shifting by three is the same as dividing by eight or multiplying by 0.125.
• A third example is 2.625×80=210?(2+0.5+0.125)×80=210?(2×80)+(0.5×80)+(0.125×80)=210. The result is ((foo<<1)+(foo>>1)+(foo>>3)). Left-shifting by one is the same as multiplying by two, right-shifting by one is the same as dividing by two or multiplying by 0.5, and right-shifting by three is the same as dividing by eight or multiplying by 0.125.

All of these examples take up less space and are faster than calling the standard 8×8-multiply function or division function from most standard math libraries.

Also, you should note that, if the result of the variable you are multiplying can ever exceed 8 bits, then you should use a word function that can store 16 bits of your result, and you should use casting on the outer parentheses.

The result is (word)((foo<<1)+(foo>>1)+(foo>>3)).

Aaron Lager, Panamax Furman, Santa Rosa, CA; Edited by Charles H Small and Fran Granville -- EDN, 5/29/2008