Why multiply is software on small machines
Repeated addition in a loop, and the gates it saves
On a small CPU without a hardware multiplier, multiplication is done in software by repeated addition inside a loop, adding one operand to an accumulator while the other operand counts down to zero, because a multiply circuit costs far more gates than the short loop that replaces it.
The accumulator CPU has
ADD and SUB, but no MUL. That is not an oversight, it is a choice. Multiplication of two 8-bit numbers is real hardware: a tree of adders that sums the shifted partial products (the shift-and-add you can step through). On a tiny machine that circuit would dwarf everything else. So small CPUs leave multiply out of the hardware and do it in software instead.Multiply is repeated addition
3 x 4 means "add 4 to itself 3 times," or equally "add 3 to itself 4 times." That is a loop: keep a running total, add one operand to it, and count the other operand down until it reaches zero. Everything needed is already in the ISA, ADD, SUB, the zero flag, and a conditional jump: LOAD b ; counter = b (how many times to add)
loop: JZ done ; when the counter hits 0, we're finished
STORE cnt ; save the counter
LOAD prod ; running total
ADD a ; prod = prod + a
STORE prod
LOAD cnt ; counter - 1
SUB one
JMP loop ; and test again
done: HALT
a: .byte 3
b: .byte 4
one: .byte 1
cnt: .byte 0
prod: .byte 0After the loop,
prod holds 12. No multiply instruction was involved, only additions, a subtraction to count, and a branch to repeat. The program supplied an operation the hardware never had. That is the deepest idea in the whole course: given loops and decisions, software extends what the machine can do without changing a single gate.The trade: gates versus cycles
Software multiply is slow: multiplying by
200 runs the loop two hundred times, while a hardware multiplier gives the answer in one step. So it is a trade. A tiny microcontroller that rarely multiplies saves the gates and pays in clock cycles; a processor that multiplies constantly (graphics, signal processing) spends the gates on a dedicated multiplier and gets the speed. Same operation, different answer to "is this worth building in silicon?"Common mistakes. Repeated-addition multiply takes time proportional to the counter, so a large multiplier means a long loop, real software uses cleverer shift-and-add to cut that down, but even that is slower than hardware. Mind the width: the product of two bytes can exceed
255 and wrap in an 8-bit accumulator, so a correct routine needs a wider result or must expect overflow. And guard the zero case: if the counter starts at 0, the loop must produce 0, not run forever, which is why the test comes at the top.The line between hardware and software is a design decision, not a law. Anything a loop of simpler instructions can compute may be left out of the silicon and written as software, and anything written often enough in software may be pulled into the silicon as a new instruction. Multiply sits right on that line, and where a given chip draws it tells you what that chip is for.
Try it
Using only ADD, SUB, the zero flag, and jumps, how would you compute a DIVISION like
20 / 4 (how many times 4 goes into 20)? Sketch the loop.Answer
Division by repeated subtraction: keep a count starting at 0, and while the dividend is not below the divisor, subtract the divisor and add one to the count. For
20 / 4: subtract 4 to get 16 (count 1), 12 (2), 8 (3), 4 (4), 0 (5), then the zero flag fires and you stop with count = 5. Just as multiply is repeated addition, integer division is repeated subtraction, both are loops built from the instructions the machine already has.Frequently asked
Why do some CPUs not have a multiply instruction?
Because a hardware multiplier is a large circuit (a tree of adders for the partial products), and a small or low-cost CPU that rarely multiplies saves those gates by doing multiplication in software instead, as a loop of additions. It is a trade of chip area for clock cycles.
How does a computer multiply without a multiply instruction?
By repeated addition in a loop: keep a running total, add one operand to it, and count the other operand down with SUB until the zero flag fires. The loop uses only ADD, SUB, and a conditional jump, so the program supplies multiplication that the hardware never had.
Is software multiplication slower than hardware multiplication?
Yes. Repeated-addition multiply takes time proportional to the multiplier, so it can be hundreds of cycles, while a hardware multiplier produces the result in one or a few cycles. Software multiply trades speed for saved gates, which is why performance-critical chips include a dedicated multiplier.
Every lesson here builds toward one thing: a working CPU, from the transistor up.
Open the free lab →Or test yourself: the free placement exam takes 15 minutes →