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'll have a look at compiler outputs, good idea. I think I found a method for subtraction without the skip, see other answer.– dirktOct 21, 2016 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?– dirktOct 21, 2016 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, 2016 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, 2017 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 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.
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.
Clever stuff. Can't quite convince myself that carry works in all instances. I'll have to try testing this later to see. And, for that matter, I should test my proposed subroutines. Oct 21, 2016 at 18:13
1Doesn'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 IACso it isn't any shorter than the
SZLsolution. Oct 22, 2016 at 1:53