7

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?

7

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. – dirkt 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? – dirkt 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 – George Phillips 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. – A. I. Breveleri Feb 12 '17 at 14:51
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.

  • 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. – George Phillips Oct 21 '16 at 18:13
  • 1
    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. – George Phillips Oct 22 '16 at 1:53
3

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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