Why multiply is harder than add
By now the ALU can add and subtract a pair of n-bit numbers in one go, and you have even seen a carry-lookahead adder race the carry across all the columns at once. Addition is a single sweep of binary addition across n columns. Multiplication is not one such sweep — it is a pile of them. Multiplying two n-bit numbers can produce a result up to 2n bits wide, and the schoolbook method builds it from n separate additions.
Recall how you multiply by hand in base ten: for each digit of the multiplier you write down a shifted copy of the multiplicand, then add the whole stack. Binary makes each of those steps almost trivial, because every digit of the multiplier is either 0 or 1. So each partial product is either the multiplicand shifted into place, or nothing at all. The hard part is no longer 'what do I write down' — it is 'how do I add all these rows quickly', and that question is what separates a slow multiplier from a fast one.
Shift-and-add: the patient one-row-at-a-time machine
The smallest, cheapest multiplier reuses one adder over and over. This is shift-and-add multiplication, and it is just the hand method run on a sequential circuit. Keep a running product register (initially zero) and walk through the multiplier one bit at a time, from the least significant end. At each step you look at the current multiplier bit: if it is 1, add the multiplicand into the high half of the product; if it is 0, add nothing. Then shift everything right by one position so the next bit lines up, and repeat n times.
Multiply 5 (0101) by 6 (0110), 4-bit, shift-and-add bit multiplier bit action partial sum (8-bit) --- -------------- ------------ ------------------- b0 0 add 0 0000 0000 b1 1 add 5<<1 0000 1010 (= 10) b2 1 add 5<<2 0001 1110 (= 30) b3 0 add 0 0001 1110 (= 30) result = 30 (5 x 6, correct)
It works, and it is tiny — one adder, a couple of shift registers, a little control state machine counting the steps. But notice the cost: for n-bit operands it takes about n clock cycles, because it does one addition per multiplier bit in sequence. A 64-bit multiply this way is dozens of cycles. That is the same trade you keep meeting on this ladder — cheap hardware buys slow operation. To go faster we either do fewer additions or do them in parallel, and both ideas have a classic answer.
Booth's algorithm: turning runs of ones into one subtract
Here is a lovely arithmetic insight. A run of consecutive 1s in the multiplier, like 0111 1000, represents a string of additions you would rather not do one by one. But that block of ones equals a big power of two minus a smaller one — 0111 1000 is 128 minus 8 — so instead of seven additions you can do one add at the top of the run and one subtract at the bottom. Booth's algorithm is exactly this trick made systematic, and as a bonus it handles signed two's complement operands directly, with no special case for negative numbers.
Mechanically, Booth scans the multiplier looking at each bit and the bit just below it (imagine an extra 0 hanging off the bottom). A 1-to-0 transition as you read upward marks the start of a run and triggers a subtract of the multiplicand; a 0-to-1 transition marks the end and triggers an add; inside a run of identical bits you only shift. The honest caveat: Booth shines on operands with long runs of ones, but on a pattern that alternates 0101... it can actually do more operations than plain shift-and-add. That is why real chips use a refined 'modified Booth' that looks at two bits at a time, guaranteeing it processes the multiplier in n/2 steps regardless of the bit pattern.
Array and tree multipliers: spend gates, buy speed
The sequential multipliers reuse one adder across n cycles. The opposite extreme generates all the partial products at once and adds them with a forest of adders, finishing in a fixed, short delay. An array multiplier lays out an n-by-n grid of AND gates (each computes one partial-product bit) feeding a mesh of full adders — a beautiful, regular block of silicon that produces the answer in roughly the time it takes a carry to ripple across and down the array. It is fast, but its delay still grows with n, and it eats a lot of area.
The clever next step is the Wallace tree (and its cousin the Dadda tree). Instead of adding the partial products in a long line, it crushes them down in a tree, using carry-save adders that add three rows into two without ever propagating a carry along the way. Because the height of a tree grows only like the logarithm of the number of rows, the partial products collapse in about log-n levels instead of n. Only the very last step — turning the final two rows into one number — needs a real carry-propagating adder, and that is exactly where a fast carry-lookahead adder earns its keep.
Notice the pattern across all three designs — sequential, array, tree. They all compute the same product; they differ only in how much hardware they throw at it and how fast they finish. That is the architect's recurring lever: spend area and power to shorten the critical path, or save hardware and pay in cycles. A phone's low-power core might favour a compact sequential multiplier; a server's number-crunching unit happily spends millions of transistors on a tree to multiply in a single pipeline stage.
Division: the slow child of the ALU
If multiplication is a pile of additions, division is worse, and there is a deep reason why. Multiplication can guess every partial product up front — each multiplier bit independently says 'add this shifted copy or not'. Division cannot. At each step you must decide the next quotient bit by asking 'does the divisor fit into what remains?', and you cannot answer that until you have finished the previous subtraction. The steps are chained: each depends on the result of the one before, so there is no parallel shortcut like the multiplier tree.
The basic hardware mirrors long division: shift the partial remainder left, try subtracting the divisor, and if the result is non-negative keep it and record a quotient bit of 1, otherwise restore the old remainder and record a 0. This 'restoring' division does one trial subtraction per quotient bit — again about n sequential, dependent steps. A refinement called non-restoring division avoids the wasted restore, and high-end chips use SRT division (named for Sweeney, Robertson, and Tocher) to produce several quotient bits per step from a small lookup table. But even SRT is fundamentally iterative.
Putting the multiplier and divider to work
Step back and the whole arithmetic toolkit lines up. Addition and subtraction reuse one adder thanks to two's complement; a fast adder trades gates for a shorter carry; a multiplier is a structured pile of adders you can build cheap-and-slow or fat-and-fast; division is the stubbornly sequential one you avoid when you can. These are the integer operations the ALU exposes to every arithmetic instruction the processor runs.
- Need a cheap multiplier? Reuse one adder for n cycles with shift-and-add — small area, slow result.
- Want speed and signed operands handled cleanly? Reach for Booth (modified Booth in practice) to halve the steps and absorb the sign.
- Want a multiply in roughly one pipeline stage? Spend the gates on an array or Wallace-tree multiplier, finished by one carry-propagating add.
- Facing a divide? Expect many sequential cycles — and where you can, replace it with a multiply-by-reciprocal or a shift.
All of this still lives in the world of integers, where every value is exact and a fixed number of bits either holds the answer or overflows. The next guide leaves that comfortable world for fractions and very large or very small numbers: how a floating-point unit aligns exponents, operates on significands, normalizes, and rounds — and the honest surprises that come when a finite word can only approximate the real numbers.