# 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.

Group: Processor
URL: https://digiwleea.wleeaf.dev/learn/multiply-in-software/

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](https://digiwleea.wleeaf.dev/tools/binary-multiplication/) 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](https://digiwleea.wleeaf.dev/learn/branching-and-loops/): 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](https://digiwleea.wleeaf.dev/learn/the-zero-flag/), and a conditional jump:

```asm
      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 0
```

_Multiply a by b by repeated addition. The running total 'prod' starts at 0; each pass adds a and decrements the counter b, stopping when b reaches 0. For a = 3, b = 4 it computes 3 + 3 + 3 + 3 = 12._

After 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?"

> **WARN:** **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](https://digiwleea.wleeaf.dev/learn/adder8/), so a correct routine needs a wider result or must expect [overflow](https://digiwleea.wleeaf.dev/learn/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.

> **KEY:** 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.

**Q (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.

**A:** 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.

### FAQ

**Q:** Why do some CPUs not have a multiply instruction?

**A:** 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.

**Q:** How does a computer multiply without a multiply instruction?

**A:** 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.

**Q:** Is software multiplication slower than hardware multiplication?

**A:** 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.