Strength reduction is a compiler optimization where a costly operation is replaced with an equivalent but less expensive operation.
Operator strength reduction involves using mathematical identities to replace slow math operations with faster operations. The cost and benefits will depend highly on the target CPU and sometimes on the surrounding code (depending on availability of other functional units within the CPU). Examples of this include
- replacing integer division or multiplication by a power of 2 with an arithmetic shift or logical shift[1]
- replacing integer multiplication by a constant with a combination of shifts, adds or subtracts.
| original calculation | replacement calculation |
|---|---|
| y = x / 8 | y = x >> 3 |
| y = x * 64 | y = x << 6 |
| y = x * 2 | y = x + x |
| y = x * 15 | y = (x << 4) - x |
Induction variable or recursive strength reduction replaces a function of some systematically changing variable with a simpler calculation using previous values of the function. In a procedural programming language this would apply to an expression involving a loop variable and in a declarative language it would apply to the argument of a recursive function. For example,
f x = ... (2 ** x) ... (f (x + 1)) ...
becomes
f x = f' x (2 ** x) where f' x z = ... z ... (f' (x + 1) (2 * z)) ...
Here the expensive operation (2 ** x) has been replaced by the cheaper (2 * z) in the recursive function f'. This maintains the invariant that z = 2 ** x for any call to f'.
Notes
- ^ In languages such as C, integer division has round-towards-zero semantics, whereas a bit-shift always rounds down, requiring special treatment for negative numbers.
See also
This article was originally based on material from the Free On-line Dictionary of Computing, which is licensed under the GFDL.
This entry is from Wikipedia, the leading user-contributed encyclopedia. It may not have been reviewed by professional editors (see full disclaimer)
