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

Question

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 1:Load A with 0

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?

Answer 1

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.

Answer 2

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
  BCC @skipAdd
  ; if it was set, add a copy of B to the result…
  CLC
  ADC operandB
  ; …carrying to the high byte if needed
  BCC @skipAdd
  INC resultHi
@skipAdd:
  ; 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.