Optimisation: What is Strength Reduction

Strength reduction is a technique to take an expensive operation and replace it with an equivalent but cheaper operation.

The most common form of this optimisation you will encounter in normal code is strength reduction on an index in a loop.

val = 0
for(int i = 0; i < n; i++)
{
arr[i] = val * i;
}

In this loop the multiplication is an expensive operation which could be replaced with a cheaper addition and register store

val = 0;
runningValue = 0;
for(int i = 0; i < n; i++)
{
arr[i] = runningValue;
runningValue += val;
}

This might seem counter intuitive as addition and multiplication is generally considered very cheap. However multiplication is around three times slower than addition on modern machines - although this will vary depending on machines and the type of the numbers being used.