Added to Favorites

Related Searches

Nearby Words

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. Examples of this include: replacing integer division or multiplication by a power of 2 with a shift operation, replacing integer division by a constant with reciprocal multiplication, and replacing integer multiplication by a constant with a combination of shifts, adds or subtracts. 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:

original calculation | replacement calculation |
---|---|

y = x / 8 | y = x >> 3 |

y = x * 64 | y = x << 6 |

y = x * 2.0 | 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. E.g.

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'.

Wikipedia, the free encyclopedia © 2001-2006 Wikipedia contributors (Disclaimer)

This article is licensed under the GNU Free Documentation License.

Last updated on Thursday July 24, 2008 at 14:55:48 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

This article is licensed under the GNU Free Documentation License.

Last updated on Thursday July 24, 2008 at 14:55:48 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

Copyright © 2014 Dictionary.com, LLC. All rights reserved.