Strength Reduction

General Program Transformation Defined by Cocke and Schwartz 1969

Goal: Replace costly repeated products i*c by less expensive additions; capable of automatically replacing a dth degree polynomial occurring in a program loop by sums.

Algorithm to implement Strength Reduction - Cocke and Kennedy 1975

Running Time of iterated algorithm: Omega((L**3) L') hash operations, where L is the size of the unoptimized program, and L' is the size of the optimized program

New Solution - Cai and Paige 95

Running Time: O(L + L') in the worst case

Reference: Cai and Paige, " Using multiset discrimination to solve language processing problems without hashing, " TCS 145(1995) 189-228.

Click here to read about the algorithm.