Integer multiplication is one of the most algorithmically complex operations a CPU performs, yet on modern x86 cores a 64-bit IMUL takes just 3 cycles. That's a story about hardware design pushing math into silicon.

The naive approach — shift-and-add — takes one cycle per bit. A 64-bit multiply would take 64 cycles. Early CPUs like the 8086 actually did this: MUL on the 8086 took 118-133 cycles for a 16-bit operation. Multiplication was so slow that compilers used to convert x * 10 into (x << 3) + (x << 1).

The breakthrough was the Wallace tree (1964) and Dadda multiplier (1965). Instead of adding 64 partial products sequentially, you generate all 64 partial products simultaneously, then collapse them in a tree of carry-save adders. Each tree level reduces 3 numbers to 2 in constant time (no carry propagation). A 64-bit multiply needs roughly log₁.₅(64) ≈ 10 levels of CSA reduction, then one final carry-propagate add.

Modern CPUs go further with Booth encoding, which examines groups of bits to skip over runs of zeros and ones. Radix-4 Booth halves the number of partial products; radix-8 cuts it by a third. The Zen 4 multiplier uses radix-8 Booth feeding a Wallace tree.

The catch: multiplication is fully pipelined but not single-cycle. On Intel's Golden Cove:

• IMUL r64, r64: 3-cycle latency, 1-per-cycle throughput
• MUL r64 (writes RDX:RAX): 3-cycle latency, but ties up the multiplier port
• IMUL r32, r32: 3 cycles — same as 64-bit, because the tree handles both

Rule of thumb: on modern x86, treat IMUL as costing about 3× a simple ADD. If you have an independent multiply every cycle, throughput is the same as add — but a dependency chain of multiplies runs 3× slower than a chain of adds.

Real example: hash functions like FNV-1a use a multiply-then-XOR loop. Each iteration's multiply depends on the previous, so you're locked at 3 cycles per byte hashed. This is why high-performance hashes like xxHash split the state into 4 parallel lanes — the multiplier port can issue a new IMUL every cycle, but only if there are independent multiplies available to fill the pipeline.

Floating-point multiply is similar (4-5 cycles), but FMA — fused multiply-add — gets the multiply and add for the same 4-cycle latency. That's why dense linear algebra runs on FMAs, not separate operations.