Arithmetic operations on multiple words on the PDP-8

Question

For the PDP-8 with its strange ISA, I've always wondered what the "standard" (i.e. fastest) way to do arithmetic operations (add, subtract, maybe multiply) on integers consisting of multiple words was. I've seen a bit of PDP-8 assembly, but never any that involved these operations. Anyone who has seen these? Or can come up with fast ones?

Answer 1

Doug Jones' PDP-8 Programmer's Reference Manual is very helpful here.

There's pretty much just one way to do multi-word precision add and subtract. Memory addressing complicates things so let's just consider adding two fixed 3 word little-endian numbers at address A and B with result into C.

   CLA CLL        ; clear accumulator and link (carry-ish) bit.
   TAD A          ; load first word of A into accumulator
   TAD B          ; add first word of B to A.
   DCA C          ; store result (and clears accumulator)
   RAL            ; 13 bit rotate of accumulator so accumulator = link, link = 0
   TAD A+1        ; carry + next word of A
   TAD B+1        ; add next word of B
   DCA C+1        ; store in result
   RAL            ; push carry into accumulator and clear link
   TAD A+2        ; carry + next word of A
   TAD B+2        ; add next word of B
   DCA C+2        ; store result

With no built-in subtract instruction we must use the fact that A - B is equivalent to A + ~B + 1 where ~ is the one's complement.

   CLA CLL
   TAD B         ; load first word of B
   CMA IAC       ; compute ~B + 1
   TAD A         ; add in first word of A
   DCA C         ; store result
   TAD B+1       ; load second word of B
   CMA           ; compute ~B
   SZL           ; skip next instruction if no carry from previous TAD
   CLL IAC       ; clear previous carry and apply it to accumulator
   TAD A+1       ; add in second word of A
   DCA C+1       ; store result
   TAD B+2       ; get third word of B
   CMA           ; ~B
   SZL           ; if carry from previous TAD then
   CLL IAC       ;   clear previous carry; add 1 to accumulator
   TAD A+2       ; add third word of A
   DCA C+2       ; store result

Those familiar with more modern architectures might worry that carry will be lost in some situations. For instance, an IAC might set the link bit and the following TAD will clear it if not carry. Not to worry, the link bit is handled more cleverly than that. It complements the link bit when there is carry out of the add. If there is no carry it leaves it alone. The operation is similar to modern "add with carry" instructions but gives us the latitude we need to handle this case. The PDP-8 designers clearly had some foresight.

Notice that multi-word addition uses RAL to get the carry into the accumulator and clear the link bit. I can't see how that trick can be applied to subtraction due to the need to complement the accumulator. The SZL : CLL IAC sequence can be replaced with DCA C+1 : RAL but that's the same number of instructions and probably slower.

Multiply is a whole other can of worms. For an answer to that and possibly better add and subtract routines I suggest looking at FORTRAN or other high-level language compiler output.

Answer 2

I worked with this machine for many years, mostly while employed at Digital Equipment Corporaion. The code in our library for multiple-precision subtraction was:

        CLA             ; not required if previous code always leaves AC==0
        TAD  B
        CLL CMA CML IAC ; form 13-bit negative with no previous borrow
        TAD  A          ; sets link to 0 for borrow, 1 for no borrow
        DCA  C
        RAL             ; propagate "complemented" borrow
        TAD  B+1        ; add previous stage borrow before forming negative
        CMA CML IAC     ; form 13-bit negative
        TAD  A+1        ; sets link to 0 for borrow, 1 for no borrow
        DCA  C+1
        RAL             ; propagate "complemented" borrow
        TAD  B+2        ; add previous stage borrow before forming negative
        CMA CML IAC     ; form 13-bit negative
        TAD  A+2
        DCA  C+2        ; et.seq. for further precision
        ; for unsigned arguments, the link now indicates a negative result

The static load is an irreducable 5 instructions per additional word of precision. The dynamic load is 8 to 11 cycles per word of precision, depending on indirection.

The PDP-8 programmers I worked with at DEC felt this arrangement of operations was the most easily proved correct. Some DECUS contributors may have had other opinions.

Answer 3

I think I found a faster method for subtraction, without the skip. The trick is to not increment AC for the 2's complement, but do the increment before the 1's complement (so it becomes a decrement), and decrement by 2 (i.e increment the subtrahend by 1) if there's a borrow. In other words, initialize AC to -2 if there's a borrow, and -1 otherwise.

    CLA CLL CML   / L := 1 (no borrow)
    TAD B
    CMA IAC       / 2's complement
    TAD A         / borrow: L := 0
    DCA C
    CMA RAL       / L=0: AC := -2, L=1: AC := -1; L := 1
    TAD B+1
    CMA           / 1's complement
    TAD A+1
    DCA C+1
    ...

To make it more regular, one could also do a 1's complement for the lowest word, using CLA CMA CLL CML as initialization.

But of course I've no idea if that was a standard method.