2026-06-29
Every other basic arithmetic op on a modern CPU is fast. Add: 1 cycle. Multiply: 3–5 cycles, fully pipelined. Division? 10 to 95 cycles, and usually not pipelined at all. One in-flight divide blocks the next one.
The reason is algorithmic. Addition has a known fast structure (carry-lookahead). Multiplication parallelizes beautifully via a Wallace tree of partial-product reducers — wide hardware, shallow depth. Division has no equivalent. The classic algorithms — restoring, non-restoring, and SRT (Sweeney-Robertson-Tocher) — are fundamentally iterative: each digit of the quotient depends on the remainder produced by the previous digit. You can't compute bit 5 of the quotient until you know bits 6 and 7.
Modern CPUs use radix-16 or radix-256 SRT dividers that resolve multiple quotient bits per cycle, but you still iterate. A 64-bit integer divide on Intel Golden Cove takes 12–18 cycles latency, throughput one every 6–10 cycles. Double-precision FP divide: 13–14 cycles, throughput one per 5. Compare to FP multiply: 4 cycles latency, one per cycle throughput.
Concrete example. A loop computing histogram[x % 1024] in a hot path. The modulo compiles to an idiv — ~25 cycles each iteration, blocking subsequent divides. Change to histogram[x & 1023] (since 1024 is a power of two) and the operation becomes a single-cycle AND. Easy 20× speedup on that operation.
Compilers know this. When the divisor is a compile-time constant, GCC and Clang emit magic-number multiplication: x / 7 becomes a 64-bit multiply by 0x2492492492492493 followed by a shift. Two pipelined ops instead of one serial divide. But if the divisor is a runtime variable, you eat the full cost.
1.0/d once, multiply by it inside the loop. Loses ~1 ULP of accuracy; gains 5–10×.libdivide precompute the magic number at runtime — worth it after ~5 divides by the same value.The divider is also typically shared across the integer and FP pipelines (or across SMT siblings), so one thread issuing back-to-back divides can starve the other.