Strength Reduction: The Compiler Trick That Makes Loops Fly

Introduction

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.

Try It

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.

<!-- Strength Reduction Demo: multiply vs add per iteration -->
<div class="controls">
  <label for="stride-slider">Stride: <span id="stride-val">4</span></label>
  <input id="stride-slider" type="range" min="1" max="16" value="4" />
  <label for="steps-slider">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">Original (multiply)</div>
    <div class="code-box" id="code-orig"></div>
    <div class="trace-label">Values produced:</div>
    <div id="trace-orig" class="trace"></div>
  </div>
  <div class="panel">
    <div class="panel-title">Optimized (add)</div>
    <div class="code-box" id="code-opt"></div>
    <div class="trace-label">Values produced:</div>
    <div id="trace-opt" class="trace"></div>
  </div>
</div>
<div class="status-bar" id="status"></div>
<button id="btn-run" type="button">Rerun</button>

/* two-panel layout: original (multiply) vs optimized (add) */
* { 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; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Strength reduction: replace i*stride (one multiply per step)
// with an accumulator t that advances by stride (one add per step).
// The original loop recomputes i*stride on every iteration.
// The optimized loop keeps t = i*stride and adds stride each step.

let stride = 4, steps = 8;

const strideSlider = document.getElementById('stride-slider');
const stepsSlider  = document.getElementById('steps-slider');
const strideVal    = document.getElementById('stride-val');
const stepsVal     = document.getElementById('steps-val');

// Update displayed slider labels and re-render on every slider move.
strideSlider.addEventListener('input', () => { stride = +strideSlider.value; strideVal.textContent = stride; render(); });
stepsSlider.addEventListener('input',  () => { steps  = +stepsSlider.value;  stepsVal.textContent  = steps;  render(); });

function codeOrig(s, n) {
  // Show the original code pattern with the multiply.
  return `t = i * ${s}  // multiply every step\n\n` +
         `i = 0\n` +
         `loop ${n} times:\n` +
         `    offset = i * ${s}\n` +
         `    i++`;
}

function codeOpt(s, n) {
  // Show the optimized code pattern with the accumulator.
  return `t = 0     // init accumulator\n\n` +
         `i = 0, t = 0\n` +
         `loop ${n} times:\n` +
         `    offset = t\n` +
         `    t += ${s}   // add every step`;
}

function makeChip(value, kind) {
  const d = document.createElement('span');
  d.className = 'chip ' + kind;
  d.textContent = value;
  return d;
}

function render() {
  // Rebuild both code boxes and trace rows from current stride and steps.
  document.getElementById('code-orig').textContent = codeOrig(stride, steps);
  document.getElementById('code-opt').textContent  = codeOpt(stride, steps);

  const tOrig = document.getElementById('trace-orig');
  const tOpt  = document.getElementById('trace-opt');
  tOrig.innerHTML = '';
  tOpt.innerHTML  = '';

  let acc = 0;
  for (let i = 0; i < steps; i++) {
    const mulVal = i * stride;  // Original: compute i*stride via multiplication each step.
    tOrig.appendChild(makeChip(mulVal, 'chip-mul'));

    tOpt.appendChild(makeChip(acc, 'chip-add'));
    acc += stride;  // Optimized: advance accumulator by stride via addition.
  }

  // Update the summary status line below the panels.
  document.getElementById('status').textContent =
    i18nFmt('%steps% iterations, stride %stride% — both produce identical values.', { steps: steps, stride: stride });
}

document.getElementById('btn-run').addEventListener('click', render);
render();

<!-- Strength Reduction Demo: multiply vs add per iteration -->
<div class="controls">
  <label for="stride-slider">Stride: <span id="stride-val">4</span></label>
  <input id="stride-slider" type="range" min="1" max="16" value="4" />
  <label for="steps-slider">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">Original (multiply)</div>
    <div class="code-box" id="code-orig"></div>
    <div class="trace-label">Values produced:</div>
    <div id="trace-orig" class="trace"></div>
  </div>
  <div class="panel">
    <div class="panel-title">Optimized (add)</div>
    <div class="code-box" id="code-opt"></div>
    <div class="trace-label">Values produced:</div>
    <div id="trace-opt" class="trace"></div>
  </div>
</div>
<div class="status-bar" id="status"></div>
<button id="btn-run" type="button">Rerun</button>

/* two-panel layout: original (multiply) vs optimized (add) */
* { 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; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Strength reduction: replace i*stride (one multiply per step)
// with an accumulator t that advances by stride (one add per step).
// The original loop recomputes i*stride on every iteration.
// The optimized loop keeps t = i*stride and adds stride each step.

let stride = 4, steps = 8;

const strideSlider = document.getElementById('stride-slider');
const stepsSlider  = document.getElementById('steps-slider');
const strideVal    = document.getElementById('stride-val');
const stepsVal     = document.getElementById('steps-val');

// Update displayed slider labels and re-render on every slider move.
strideSlider.addEventListener('input', () => { stride = +strideSlider.value; strideVal.textContent = stride; render(); });
stepsSlider.addEventListener('input',  () => { steps  = +stepsSlider.value;  stepsVal.textContent  = steps;  render(); });

function codeOrig(s, n) {
  // Show the original code pattern with the multiply.
  return `t = i * ${s}  // multiply every step\n\n` +
         `i = 0\n` +
         `loop ${n} times:\n` +
         `    offset = i * ${s}\n` +
         `    i++`;
}

function codeOpt(s, n) {
  // Show the optimized code pattern with the accumulator.
  return `t = 0     // init accumulator\n\n` +
         `i = 0, t = 0\n` +
         `loop ${n} times:\n` +
         `    offset = t\n` +
         `    t += ${s}   // add every step`;
}

function makeChip(value, kind) {
  const d = document.createElement('span');
  d.className = 'chip ' + kind;
  d.textContent = value;
  return d;
}

function render() {
  // Rebuild both code boxes and trace rows from current stride and steps.
  document.getElementById('code-orig').textContent = codeOrig(stride, steps);
  document.getElementById('code-opt').textContent  = codeOpt(stride, steps);

  const tOrig = document.getElementById('trace-orig');
  const tOpt  = document.getElementById('trace-opt');
  tOrig.innerHTML = '';
  tOpt.innerHTML  = '';

  let acc = 0;
  for (let i = 0; i < steps; i++) {
    const mulVal = i * stride;  // Original: compute i*stride via multiplication each step.
    tOrig.appendChild(makeChip(mulVal, 'chip-mul'));

    tOpt.appendChild(makeChip(acc, 'chip-add'));
    acc += stride;  // Optimized: advance accumulator by stride via addition.
  }

  // Update the summary status line below the panels.
  document.getElementById('status').textContent =
    i18nFmt('%steps% iterations, stride %stride% — both produce identical values.', { steps: steps, stride: stride });
}

document.getElementById('btn-run').addEventListener('click', render);
render();

Result

Console

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.

The Real Mechanics

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.

Where It Matters

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.

Conclusion

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.

Comments

Loading comments...

https://www.kipuhub.com/en/article/strength-reduction/Content licensed under CC BY-NC 4.0.

Cookies & privacy

Strength Reduction

The compiler trick that turns multiplications into additions