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. 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.
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.
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 ; generates 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 ; generates 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.