Strength Reduction

Every loop has a cost. When your program computes i * stride on each iteration, it pays for a multiplication — an operation that can be ten times slower than an addition on some hardware. Strength reduction is the compiler's answer: notice that the product only ever changes by a constant, then replace the multiply with an accumulating addition.

The idea is ancient by computing standards. Frances Allen and John Cocke described it in the early 1970s, but the pattern was already embedded in hand-optimised assembly of the 1960s. Yet it is not just a hardware trick — it is a precise algebraic observation: if $f(i) = c \cdot i$ and $i$ advances by 1 each step, then $f(i+1) = f(i) + c$. One add replaces one multiply, every iteration, forever.

Strength reduction is one thread in a larger tapestry of program optimization ideas, and understanding it illuminates why compilers can often produce code that beats hand-written loops.

The panel below runs two versions of the same loop side by side. The original computes the array offset as $i \times \text{stride}$ on every step — a multiply each time. The optimized version keeps a running total and just adds the stride each step.

<!-- {{c_demo_title}} -->
<div class="controls">
  <label for="stride-slider">{{lbl_stride}} <span id="stride-val">4</span></label>
  <input id="stride-slider" type="range" min="1" max="16" value="4" />
  <label for="steps-slider">{{lbl_steps}} <span id="steps-val">8</span></label>
  <input id="steps-slider" type="range" min="2" max="16" value="8" />
</div>
<div class="panels">
  <div class="panel">
    <div class="panel-title">{{title_original}}</div>
    <div class="code-box" id="code-orig"></div>
    <div class="trace-label">{{lbl_trace}}</div>
    <div id="trace-orig" class="trace"></div>
  </div>
  <div class="panel">
    <div class="panel-title">{{title_optimized}}</div>
    <div class="code-box" id="code-opt"></div>
    <div class="trace-label">{{lbl_trace}}</div>
    <div id="trace-opt" class="trace"></div>
  </div>
</div>
<div class="status-bar" id="status"></div>
<button id="btn-run" type="button">{{btn_run}}</button>

/* {{c_layout}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; color: #222; }
.controls { display: flex; flex-direction: column; gap: .4rem; margin-bottom: .8rem; }
label { font-size: .85rem; font-weight: 600; color: #444; }
input[type=range] { width: 100%; accent-color: #1d3557; }
.panels { display: grid; grid-template-columns: 1fr 1fr; gap: 1rem; }
.panel { background: #f4f7fa; border-radius: 10px; padding: .7rem; }
.panel-title { font-size: .78rem; font-weight: 700; text-transform: uppercase;
               letter-spacing: .06em; color: #1d3557; margin-bottom: .4rem; }
.code-box { background: #1d3557; color: #e0e8f0; border-radius: 7px; padding: .6rem .75rem;
            font: 12px/1.7 ui-monospace, monospace; white-space: pre; }
.trace-label { font-size: .75rem; color: #666; margin: .45rem 0 .2rem; }
.trace { display: flex; flex-wrap: wrap; gap: 4px; min-height: 28px; }
.chip { display: inline-flex; align-items: center; justify-content: center;
        min-width: 36px; height: 26px; padding: 0 7px; border-radius: 6px;
        font: 700 12px ui-monospace, monospace; }
.chip-mul { background: #fdecea; color: #c0392b; border: 1px solid #e0a9a3; }
.chip-add { background: #e8f5e9; color: #1b7a3e; border: 1px solid #a3d9a5; }
.status-bar { font-size: .9rem; font-weight: 600; min-height: 1.4em; margin: .6rem 0 .4rem; color: #1d3557; }
button { font: 600 14px system-ui; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }

// Code not found

Slide the stride and watch both counters stay in lock-step. The optimized loop does exactly the same arithmetic — it just uses addition instead of multiplication. Try a large stride to make the savings concrete: every multiplication in the original loop is a wasted opportunity that the compiler quietly eliminates.

How does a compiler spot the opportunity?

• Induction variables. A variable is an induction variable if it changes by a fixed amount each iteration. The classic loop counter i = 0, 1, 2, … is the basic induction variable.
• Linear derived expressions. If you compute $c \cdot i + d$ inside the loop — where $c$ and $d$ are loop-invariant — you have a derived induction variable. Its value changes by exactly $c$ on every step.
• The reduction. The compiler introduces a new variable $t$ initialized to $c \cdot i_{\text{start}} + d$, and replaces every use of $c \cdot i + d$ with $t$, adding $c$ to $t$ at the end of each iteration. The multiplication disappears from the loop body.
• Dead code. If the original expression is no longer used, the multiply is dead and can be deleted entirely. This is why strength reduction is often paired with dead-code elimination.

The saving is real: on a tight inner loop processing millions of array elements, turning $n$ multiplications into $n$ additions shaves a measurable fraction off total runtime. For array indexing — $\text{base} + i \times \text{element\_size}$ — this fires on almost every loop a compiler sees. It is one reason why idiomatic high-level code often compiles to pointer-bump sequences rather than repeated index arithmetic.

Strength reduction is not a niche trick — it is one of the most broadly applicable optimisations a compiler performs:

• Array traversal. Every a[i] in C compiles to base + i * sizeof(element). Strength reduction turns the per-iteration multiply into a pointer increment.
• Polynomial evaluation (Horner's method). Evaluating $a_n x^n + \dots + a_0$ with nested multiplications is a chain of strength-reduced additions once $x$ is fixed.
• Graphics rasterization. Scanline rasterizers step a pixel row one at a time; the $x$-coordinate is an induction variable and every derived colour or depth computation is strength-reduced.
• Digital signal processing. FIR and IIR filters multiply by fixed coefficients in tight loops — strength reduction eliminates those multiplies when the input pointer advances linearly.
• Modular arithmetic. Computing $i \bmod m$ in a loop can be replaced by a conditional subtraction — the same "replace a divide with a cheaper test" spirit as strength reduction.

The pattern connects to deeper ideas: dynamic programming exploits the same "reuse a previous result instead of recomputing" structure, just at the algorithm level rather than the instruction level.

Strength reduction is a small idea with a long reach. Notice that a loop computation changes by a constant each step, and a multiplication silently becomes an addition — repeated, free, and exact. No approximation, no trade-off, no loss of correctness.

That precision is what makes it beautiful: the compiler is not guessing or sacrificing accuracy. It is applying a mathematical identity — $f(i+1) = f(i) + c$ — and every loop that touches an array has been silently improved by it for decades. The next time you write a[i] inside a loop, know that the compiler has already replaced your multiply with a bump of a pointer, and the code runs a little faster because of an observation made in the 1960s.