# Arithmetic operations on multiple words on the PDP-8

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?

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.
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
DCA C+1        ; store in result
RAL            ; push carry into accumulator and clear link
TAD A+2        ; carry + next word of A
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
CMA IAC       ; compute ~B + 1
DCA C         ; store result
CMA           ; compute ~B
SZL           ; skip next instruction if no carry from previous TAD
CLL IAC       ; clear previous carry and apply it to accumulator
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
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.

• I'll have a look at compiler outputs, good idea. I think I found a method for subtraction without the skip, see other answer. Oct 21 '16 at 6:16
• Meh, FORTRAN compiles to FPP commands. IIRC FOCAL and BASIC just interprete (at least pseudo-code). Any other HLL compiler I could try? Oct 21 '16 at 10:45
• Bunch of possibilities here: homepage.cs.uiowa.edu/~jones/pdp8/faqs/#langs The earlier FORTRAN might not need a floating point coprocessor. The interpreters might have double-precision integer calculations internally. See if BASIC has integers bigger than 12 bits. Or maybe it has floating point numbers with more than 12 bits of mantissa. I looked at a LISP but seems like its (PLUS) and (MINUS) are only 12 bit: dbit.com/pub/pdp8/nickel/langs/lisp/ascii/lisp.03 Oct 21 '16 at 18:12
• No native-instruction structured language compiler for the PDP-8 was ever published during its production lifetime. The problem of packing the compiled code stream into the native memory model proved too intractable. Feb 12 '17 at 14:51

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
CLL CMA CML IAC ; form 13-bit negative with no previous borrow
TAD  A          ; generates 0 for borrow, 1 for no borrow
DCA  C
RAL             ; propagate "complemented" borrow
CMA CML IAC     ; form 13-bit negative
TAD  A+1        ; generates 0 for borrow, 1 for no borrow
DCA  C+1
RAL             ; propagate "complemented" borrow
CMA CML IAC     ; form 13-bit negative
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.

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)
CMA IAC       / 2's complement
TAD A         / borrow: L := 0
DCA C
CMA RAL       / L=0: AC := -2, L=1: AC := -1; L := 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.
• Doesn't work, unfortunately. After the first word you only need to subtract 1 if there's a borrow or 0 if not. The extra +1 is only needed on the first word. So what is needed is conversion of L to AC = -1 or 0. Best I could come up with takes two instructions: `RAL : CMA IAC` so it isn't any shorter than the `SZL` solution. Oct 22 '16 at 1:53