# How do microprocessors multiply without a "Multiply" instruction? [duplicate]

I was reading about the SAP computers(as I do), and examined the SAP-2 chapter of Paul Malvino's Digital Computer Electronics, hoping to learn about how a microprocessor without a multiply instruction would go about multiplying numbers. It required 3 registers, which i will denote A, B, and C, and the instructions to sucessfully multiply 2 binary numbers went like this according to the book:

Line 2:Load B with the first number you are multiplying

Line 3:Load C with the second number you are multiplying

Line 4:Add A and B and store sum in A

Line 5: Decrement C

Line 6: If the byte stored in C is not zero, jump to line 4

Line 7: Stop the program. The product will be in A.

The first problem here is the decrement instruction. Earlier in the book, it said that to execute a decrement instruction, you must load the value you want to decrement in A, subtract 1, and then load it back into the designated register. But that means that the product value in A will be overwritten by the decrement instruction, so that won't work. The second problem is the flags, which only apply to A, which means to untrigger the jump instruction, you have to overwrite A. And if that doesn't work, how do microprocessors multiply without a "Multiply" instruction? Or is there something I misunderstood in the program or how the "decrement" instruction works?

• The method you describe, is a very ineffective way for multiplication, probably it wasn't ever used. May 1, 2020 at 20:59
• If you need a register that's in use, you dump it to memory and then restore it. Not having the book, I can't tell whether it expects you to infer this - but steps 5 and 6 could be bracketed in save/restore of A. With potential complications for conditional jumps if they have to use what's in A, but solvable with the cost of extra instructions executed. However, as indicated by others, turning A*B into A+A++A+... (B times) is not really practical. You'd expect a real CPU to have a shift instruction precisely to avoid this.
– dave
May 1, 2020 at 22:43
• I think the SAP-2 might be a bit too simple for its intended purpose of teaching, if the author has to resort to a repeated-addition algorithm to demonstrate multiplication, rather than the much more common (and vastly more efficient) long multiplication. May 2, 2020 at 7:47
• Well if you denoted them A, B and C, and you have "decrement C" but the chip can only decrement A, then obviously the registers are in reality C, B and A, right? Also, did you know you can copy values from registers into memory, and copy values from memory into registers, and copy values from registers to other registers? So, the product can be in A when you do "add A and B", and then you do some shuffling, and then the counter is in A when you do "decrement C" and the product is in D. May 4, 2020 at 23:29

It seems that some of the information you have doesn't apply to the SAP-2.

Earlier in the book, it said that to execute a decrement instruction, you must load the value you want to decrement in A, subtract 1, and then load it back into the designated register.

The Simple As Possible SAP-2 computer has dedicated decrement instructions.

Section 11-4 "Register Instructions", subsection "INR and DCR" (p. 178) tells us about `DCR A`, `DCR B`, and DCR C`.  So, decrementing C is directly doable, without using A.

The second problem is the flags, which only apply to A, which means to untrigger the jump instruction, you have to overwrite A.

Oddly placed within Section 11-5 "Jump and Call Instructions", subsection "CALL and RET", minor section "More on Flags" (p. 180), tells us that the `DCR` instruction affects the `S` and `Z` flags.  So you can pair `DCR` with `JNZ` to accomplish a decrement and branch if not zero.

The text says:

If the accumulator goes negative while the `DCR C` is executed, the sign flag is set; if the accumulator goes to zero the zero flag is set.

It describes that the `DCR C` instruction is executed by sending `C` to the accumulator and decrementing by 1 within the ALU — and that since this is done in the ALU, the flags are set.

Still, there does appear to be some conflicting information.  It is clear that the ALU is used to in decrementing `C` and setting the `Z` flag.  And it is also clear from the examples and solutions that the `A` accumulator is not affected by decrementing `C`.  Yet the text does describe that the accumulator is used to decrement.  So, something else is happening, perhaps `C` is sent to the `TMP` register as that is also connect to the ALU.  Also, I would take it that the flags are set by the ALU output, not by a target register or specifically the `A`/`accumulator` — as the block diagram (Fig 11-2) indicates, the flags come out of the ALU, regardless of what register is the target.  Yet the text also describes the circuit for the flags, and says this is connected to the accumulator — but I would think it that circuit attaches to the ALU output.

Given their juggling of three different SAP-# models, some missing clarity or minor contradictions like this are to be expected.

• Thanks for the clarification! There is one problem however. On page 180 in "More on Flags", the book says "For instance, to execute a DCR C, the contents of the C register are decremented by sending these contents to the accumulator(A), subtracting 1, and sending the result back to the register." What exactly does that mean for the contents already loaded in the accumulator? And how does the computer get the 1 and -1 it needs to increment or decrement the C register? May 1, 2020 at 21:20
• Those are great questions, but all I can do is point out there appear to be some inconsistencies in the text. We know from the program fragments supplied that `A` is not wiped out by `DCR C`, so I'm thinking maybe they misspoke and it goes to the TMP accumulator/register instead. Also, it seems possible that inc & dec are expected to be built in features of the ALU, so no 2nd input is needed perhaps. May 1, 2020 at 22:59
• Alright, it makes sense now. May 1, 2020 at 23:07

The repeated-addition algorithm you describe is not the usual way. Instead, think of long multiplication, but in base 2 instead of base 10. The shift instructions available in most CPUs are useful here.

Here's how you might do it on a 6502:

``````Mul8x8to16:
LDX #8
LDA #0
STA resultHi
@loop:
; shift result up by one place
ASL A
ROL resultHi
; examine next most-significant bit of A operand
ASL operandA
; if it was set, add a copy of B to the result…
CLC
; …carrying to the high byte if needed
INC resultHi
; do the above the correct number of times
DEX
BNE @loop
; complete the result
STA resultLo
RTS
``````

In the above, only the low half of the result is kept in the accumulator, and is saved to memory right at the end. The 6502 has enough operations that work directly on memory or on the index registers for that approach.

The original ARM1 of 1985 also lacked a multiply instruction; this was one of the things added to the ARM2, which was the first version commercially sold in home computers. On the ARM1, you would need a routine like the following:

``````Mul32x32to64:
MOV    r2, #\$7FFFFFFF  ; low half of result and loop counter in one
MOV    r3, #0          ; high half of result
@loop:
MOVS   r0, r0, LSR #1  ; pull next lowest bit of A into Carry
ADDSCS r3, r3, r1      ; if it was set, add B into high result
MOVS   r3, r3, RRX     ; shift result (and its carry) down into…
MOVS   r2, r2, RRX     ; …the low half, shifting out a counter bit
BCS    @loop           ; repeat 32 times
MOV    pc, lr          ; return
``````

There are fewer instructions (and fewer cycles per loop) involved here, and the ARM does considerably more per instruction than the 6502. But the basic principle of long multiplication remains.

• That sounds much more complex than the SAP-2's approach, despite the SAP-2 having less instructions than the 6502. Can you please elaborate on why your more complex solution is more efficient? May 2, 2020 at 5:16
• @Nip Dip, this method is much faster. It only needs to “shift and add” at most 8 times, while the “repeated addition” method will need to perform a large number of additions, depending on the size of the numbers being multiplied. For 8 bits this comes down to a maximum of 255 additions. For 16x16 bit multiplications, the difference is even greater, needing just 16 shifts+adds with this method and a maximum of 65535 for the repeated addition method. And so on for 32x32 bits which just takes 32 shifts+adds but can take billions of repeated additions. May 2, 2020 at 6:01
• @NipDip It only looks complicated because the operations involved are very simple by themselves. For an 8-bit CPU, this is actually quite a small and straightforward routine. I'll add a version for the ARM1, which also lacked a hardware multiply. May 2, 2020 at 7:22
• Alright, I don't know the instruction set of the 6502, so I'll do some research on how it would do it. May 2, 2020 at 17:25