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