2

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?

  • 1
    The method you describe, is a very ineffective way for multiplication, probably it wasn't ever used. – peterh - Reinstate Monica May 1 at 20:59
  • 1
    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. – another-dave May 1 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. – Chromatix May 2 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. – user253751 May 4 at 23:29
4

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.

| improve this answer | |
  • 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? – Nip Dip May 1 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. – Erik Eidt May 1 at 22:59
  • Alright, it makes sense now. – Nip Dip May 1 at 23:07
6

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.

| improve this answer | |
  • 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? – Nip Dip May 2 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. – StarCat May 2 at 6:01
  • 1
    @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. – Chromatix May 2 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. – Nip Dip May 2 at 17:25

Not the answer you're looking for? Browse other questions tagged or ask your own question.