Strength Reduction
You'll learn how compilers replace slow operations with faster equivalent ones to speed up your code, especially inside loops.
What is Strength Reduction?
Strength reduction is a compiler optimization that replaces computationally expensive operations with cheaper ones that produce the same result. The name comes from reducing the "strength" (cost) of an operation.
The most common example: replacing multiplication with addition. Multiplying takes more CPU cycles than adding, so if you can achieve the same effect by adding instead, your code runs faster.
Why It Matters in Loops
Loops execute their bodies many times. Even small per-iteration savings multiply dramatically:
for i = 0 to 999:
x = i * 4
Here, i * 4 runs 1,000 times. But notice: each iteration just adds 4 to the previous value! A strength-reduced version:
x = 0
for i = 0 to 999:
x = x + 4
Now we use addition instead of multiplication—much faster on most hardware.
Common Strength Reductions
- Multiplication → Addition:
i * cbecomes repeated addition wheniincrements predictably - Exponentiation → Multiplication:
x ** 2becomesx * x - Division by constant → Multiplication:
x / 8becomesx * 0.125(or bit shift for powers of 2) - Array indexing:
array[i * stride]can maintain a pointer that advances bystrideeach iteration
The Pattern
Strength reduction looks for induction variables—variables that change predictably in loops—and transforms expensive calculations based on them into incremental updates.
Key Takeaway:
Strength reduction speeds up programs by replacing expensive operations (like multiplication or division) with cheaper ones (like addition or bit shifts), especially targeting operations on loop variables that change predictably.