[Home]
[Edit this page]
[Recent Changes]
[Special Pages]
[Help]
CFastMultiplication
Left shifts can be used to multiply by powers of two. Right shifts can be used to divide by powers of two. One left shift will multiply by two; two left shifts will multiply by four, etc. In C, this can be done by the "<<" operator.
Multiplication by other numbers can be accomplished by adding shifts. For example:
This works because y*(2^6) + y*(2^8) = y*256 + y*64 = y*320.
This technique obfuscates the intentions of the programmer both to maintainers and to compilers. An optimizing compiler will factor something like y*320 into y*256 + y*64 -> y<<8 + y<<6 if there are benefits. Similarly, a compiler will translate y*64 into y << 6 if its worthwile doing.
Using shifts instead of multiplies frequently results in bugs if the numbers being operated on are not of type int. There are various promotions of types to other types that occur before the shifts happen.
Note:
This technique is generally not used in higher level languages due to the reasons stated above. However, most compilers will not optimize a multiplication by a constant, since the decision of whether to change to an addition of binary shifts depends on the target processor. This is used much more frequently in assembler. It is most useful in scenarios where the code being optimized is in the inner loop of an algorithm.
[Edit this page] [Page history] [What links here] [Discuss this topic] [Printer Friendly]
CFastMultiplication
(C) Fast Multiplications
Binary shifts can be used to do fast multiplications. It was widely used on older computers for all types of integer multiplications, but has become less useful as normal multiplications have become faster on newer processors.Left shifts can be used to multiply by powers of two. Right shifts can be used to divide by powers of two. One left shift will multiply by two; two left shifts will multiply by four, etc. In C, this can be done by the "<<" operator.
Multiplication by other numbers can be accomplished by adding shifts. For example:
offset += (y<<6) + (y<<8); // Multiply by 320
This works because y*(2^6) + y*(2^8) = y*256 + y*64 = y*320.
Drawbacks
This technique will cease to be useful as the number of shifts increases if the processor can only handle single shifts at a time. The exact amount varies from one processor to the next. This technique is particularly useful when the number of clock cycles required to shift a number compared to the number required to multiply by an integer is low. For multiplication by powers of two, this technique will always be faster or equal to an equivalent multplication by a constant. You can see this by comparing the clock cycles required for the two opcodes.This technique obfuscates the intentions of the programmer both to maintainers and to compilers. An optimizing compiler will factor something like y*320 into y*256 + y*64 -> y<<8 + y<<6 if there are benefits. Similarly, a compiler will translate y*64 into y << 6 if its worthwile doing.
Using shifts instead of multiplies frequently results in bugs if the numbers being operated on are not of type int. There are various promotions of types to other types that occur before the shifts happen.
Note:
This technique is generally not used in higher level languages due to the reasons stated above. However, most compilers will not optimize a multiplication by a constant, since the decision of whether to change to an addition of binary shifts depends on the target processor. This is used much more frequently in assembler. It is most useful in scenarios where the code being optimized is in the inner loop of an algorithm.
[Edit this page] [Page history] [What links here] [Discuss this topic] [Printer Friendly]
