strength reduction

An optimisation where a function of some systematically

changing variable is calculated more efficiently by using

previous values of the function. In a procedural 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)) ...

==@#

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

(1995-01-31)