Strength reduction is the process of simplifying a program by replacing
an operation in a loop (or recursive function) with a simpler operation
using state from the previous loop iteration (or function call).

The canonical example is array indexing. Consider this snippet of C code:

**struct** Person {
*char* *name;
*unsigned* age;
*unsigned* height;
};
*unsigned* total_age_of_everyone (*int* n_people, **struct** Person people[])
{
*unsigned* total = 0;
*unsigned* i;
**for** (i=0; i<n_people; i++)
{
total += people[i].age;
}
**return** total;
}

Naively, the array address in the loop must be calculated
by a multiplication: the address required to access
`people[i].age`

is:

people + i * **sizeof**(**struct** Person) + **sizeof**(*char**)

However, on most machines, that multiplication would take a while to
calculate. At least a couple ofcycles, which is annoying since the rest
of the loop probably doesn't take much more than that to execute.

If our compiler is clever enough, and most of them are, it'll spot
that there's a faster way to calculate that address. Between each
successive iteration of the loop, that address increases by a nice,
constant value: **sizeof**(**struct** Person)

. So
instead of performing a slow multiplication, the compiler can just add
**sizeof**(**struct** Person)

to the value that it
calculated on the last iteration.

The code the compiler produces would be equivalent to the code it would produce for:

*unsigned* total = 0;
*unsigned* i;
*unsigned* *age_pointer = & people[0].age;
**for** (i=0; i<n_people; i++)
{
total += *age_pointer;
age_pointer = (unsigned *) ( (char*) age_pointer
+ **sizeof**(**struct** Person) );
}
**return** total;

Note that we've introduced a loop-carried state element (person_pointer)
that wasn't there before, and that where the loop previously had an
expensive multiplication, it now only has an addition (which, on most
architectures, can probably be merged with the load operation, saving
even more on complexity).

This strength reduction can be applied to any function which
can be expressed as a simpler, iterative function. For example,
to compute a power series, we must calculate
*x*^{n} (which can be quite expensive to calculate) for all values of *n* from 0 onwards,
but each can be calculated simply from the last value by simplying
multiplying by *x*.