Course contentsShow
← Computer Science
Lesson 2067 of 2,87246. Compilation and InterpretationFree lesson

Strength Reduction

Replacing expensive operations with cheaper equivalent operations, especially in loops.

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 * c becomes repeated addition when i increments predictably
  • Exponentiation → Multiplication: x ** 2 becomes x * x
  • Division by constant → Multiplication: x / 8 becomes x * 0.125 (or bit shift for powers of 2)
  • Array indexing: array[i * stride] can maintain a pointer that advances by stride each 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.