Strength reduction; function for

Strength reduction is a compiler optimization where a function of some systematically changing variable is calculated more efficiently by 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’.

Leave a Reply

You must be logged in to post a comment.