Replacing expensive operations with cheaper ones. Classic example: x = n * i in a loop becomes x += n.
Strength reduction is the practice of optimizing by replacing expensive operations with cheaper ones. (See https://en.wikipedia.org/wiki/Strength_reduction).
Classic example:
for (int i=0 ; i<1024 ; i++) {
a[i] = b[i * 33];
}
can be transformed by a compiler, or by a human, to code that implements it as
int i33 = 0;
for (int i=0 ; i<1024 ; i++) {
a[i] = b[i33];
i33 += 33;
}
Multiply is still somewhat more expensive than add on modern computers, and compilers go to some effort to replace them with one or two shifts+add instructions. See for example How to multiply a register by 37 using only 2 consecutive leal instructions in x-86?
Another example would be optimizing n % 4 to n & 3 (for unsigned n, or to a more elaborate sequence for signed n), because hardware division instructions are still very expensive.
