# PEP001.PA

## Or, How I Managed to Spend Three Days Solving FizzBuzz

is a common test problem for software developers, often seen in interviews. It is easy for a competent programmer to solve, yet somehow I — a self-styled competent programmer — managed to spend three days solving it. Let me tell you the story.


## The Challenge

I set myself the challenge of solving [Project Euler Problem — a close relative of FizzBuzz — in PDP-8 assembly language as a way to force myself to learn the platform. Nothing motivates like an achievable goal, particularly when one's good self-image is on the line.

When I started, I had only been playing with [my for a few weeks. I had no prior experience with a PDP-8, or any similar machine. The closest experience I had was a little experience with 6502 assembly language on the Apple ][ series in the early to late 1980s. I'd barely figured out how to run the assembler prior to setting myself this challenge.

On the positive side of the balance scale, I've been a software developer for over 30 years now, almost all of that in a professional capacity. I've learned an [awful lot of programming languages and CPUs in that including a few other assembly languages.

How hard could it be?


## Trap 1: No ROM, No Runtime

One universal characteristic of all personal computers is that it needs to have some sort of ROM, a fixed bit of programming that contains commonly-used routines, such as one to print a line of text to the user's display. The OS may paper over this ROM with some higher-level runtime, but there must be some base level of functionality that you can count on being present so you don't continually reinvent the wheel.

The PDP-8 was the spiritual ancestor of the personal computer: inexpensive, simple, and small, by the standards of the time. Just like its microcomputer descendants, the PDP-8 had a flat file system, and it ran BASIC, but real programmers wrote in assembly instead. The PDP-8 wasn't quite a "personal" computer, but it was as close as you could get in 1965-1974, the heyday of the PDP-8, before microcomputers ate its lunch.

One major thing the PDP-8 didn't have that microcomputers had, though, is a ROM. When you turn a PDP-8 on, the CPU initializes itself, and then *nothing else happens*. It just sits there, waiting for you to give it some code to run. Every single word of program code that the machine runs had to be put in its memory by some human. DEC shipped nothing, other than the media you need to load such programs in from. Strictly speaking, data media aren't even necessary: you can toggle programs in via [the front if you want instead. This directly sets memory locations with values you specify, in binary. It doesn't get much more low-level than this.

So that brings me to Trap 1: How does this program print an answer to the screen? Solution? Write your own [decimal number and [ASCII string routines! In assembly language. Debugged via the front panel.

There's one day gone.


## Trap 2: No Modulo Operator

The standard solution to FizzBuzz is to use the [modulo which returns the remainder when dividing one number into another. 6 mod 4 is 2, for example.

Major problem: the PDP-8's stock instruction set doesn't have a modulo operator, or even a division operator. This was common on early microcomputers, too: the 6502, the 8080, and the Z80 all lacked a hardware multiplier, and certainly didn't have a divider.

Fortunately for me, DEC produced an add-on to the PDP-8/I I used for this project called the also known as the Extended Arithmetic Element. The PDP-8 simulator I used for this project does have an EAE feature, so I was able to use its `DVI` instruction.

But of course the standard PDP-8 assembler doesn't know about the `DVI` instruction, or any of the special flags, registers, and microcode instructions you need to use along with it. You must actually define all of this at the top of your program so that the assembler knows how to generate the necessary code!

`DVI` is an integer divide instruction that leaves the remainder in the PDP-8's accumulator, which means it effectively implements the modulo operation as a side effect of doing division. But in order to figure that out, you must read the KE8/I specification document, which describes in excruciating detail how the KE8/I is implemented at the silicon gate level.

Nowhere in this document does it simply say "divides the value following the DVI instruction into {AC:MQ}, with the quotient in MQ and the remainder in AC." It does say all of that, piece by piece over the *five* pages documenting the `DVI` instruction, but you must extract it yourself. Here, I've done that for you in a single sentence. You're welcome.

There's another day gone.


## Trap 3: No Precision

The problem I set myself states that you must add the values of the numbers that match the given criteria up, so that the web site knows you have solved it if you can provide a rather large integer in an input box.

No, I'm not going to tell you what the answer is. Go write a 5-line Python program to solve it yourself.

Me, I took 156 PDP-8 instructions to solve it, not counting space for constants, variables, and links, the latter being a dirty trick that PDP-8 assemblers use for jumping between 128-word "pages" of memory. And you thought the 64k segments of real mode x86 assembly were bad!

But I digress.

The PDP-8 is a 12-bit machine. Since the standard arithmetic operations assume you want signed integer arithmetic, this means the largest positive number you can do math on within a PDP-8 is 2047. As the problem is posed on the Project Euler site, you need to add up the matching numbers in the range 1 to 999. That means if only three numbers match, we're likely to run over that limit.

I solved this by making my program keep track of the current total and print it out as a subtotal value once the total exceeds 1024, since no single integer in the target range could possibly overflow a 12-bit signed integer. It wrote this out as a long string of additions:

    ANSWER: 1064 + 1059 + 1060 + 1137 + 1158 + 1125 + 1047 + 1125 + ...

It went on like that for many lines. I ran this on the simulated PDP-8 via an OS X Terminal window, then copied the long string of additions and pasted it into which did all the adding up on a processor many orders of magnitude more powerful than the PDP-8.

Cheating? Maybe. I briefly considered saving each subtotal to core memory, then writing a routine to add the values up in grade school fashion, right-to-left, carries and all.

I decided that, day 3 gone, that I'd done well enough.

## The Solution

Here is my winning solution to the problem, all 221 well-commented lines of it:

    / Project Euler Problem #1, Multiples of 3 and 5:
    /
    /   If we list all the natural numbers below 10 that are multiples of
    /   3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
    /   Find the sum of all the multiples of 3 or 5 below 1000.
    /
    / Solution by Warren Young of 2016.11.30


    / DIY ASSEMBLER INSTRUCTIONS

    / Our assembler doesn't know the EAE instructions, so teach it
    DVI=7407                / integer divide .+1 into {AC:MQ}, answer in MQ
    MUY=7405                / integer multiply MQ by .+1, answer in {AC:MQ}

    / Combined microcoded instruction aliases
    CLR=CLA CLL             / clear both AC and L
    MCM=CLA MQA             / move MQ to AC
    TCA=CMA IAC             / two's complement the accumulator
    XMA=MQA MQL             / exchange MQ and AC
    AC1=CLA IAC             / set AC to 1


    MAIN
    / Program entry point.   We purposely reinitialize global variables and
    / processor state in case we're restarting this program in-core.

    PAGE 1
    MAIN,   CLR
            TAD (3)
            DCA CURR        / start with 3, because we know 1 & 2 can't work
            DCA TOTAL       / reset total to 0
            TLS             / send null to terminal to get flags set right
            TAD (ANSWER)    / write "ANSWER: " to the terminal
            JMS PRINTS
            JMP MLCORE
    CURR,   0               / current number we're checking
    TOTAL,  0               / the answer so far; at the end, printed out

    / Constants
            DECIMAL
    MAX,    999             / check natural numbers CURR to MAX; must be < 2048!
    STMAX,  1024            / subtotal max; avoids overflow of 12-bit signed int

            OCTAL
    CRLF,   15;12;0         / ASCII character values; don't forget trailing 0!
    PLUS,   40;53;40;0
    ANSWER, 101;116;123;127;105;122;72;40;0


    MLCORE
    / The core of the main loop.  MAIN just inits the globals and calls us.

            / Try dividing 3 into CURR first
    MLCORE, CLR
            TAD (3)
            JMS ISMOD0
            SNA             / if ISMOD0 left AC = 0, CURR divided evenly by
            JMP NXITER      / 3, so skip 5 lest we count multiples of 15 2x

            / That didn't work out, so try dividing 5 into it
            CLA
            TAD (5)
            JMS ISMOD0

            / Loop cleanup
    NXITER, CLA
            TAD CURR
            TCA
            TAD MAX         / = 0 if CURR == MAX
            SNA             / if so, leave calculation loop
            JMP MLDONE

            CLR             / CURR still < MAX, so increment CURR
            TAD CURR
            IAC
            DCA CURR

            TAD TOTAL       / if TOTAL is getting too big, print...
            TCA             / a subtotal and zero TOTAL so we don't...
            TAD STMAX       / overflow the 12-bit limit
            SZL
            JMP MLCORE      / STMAX - TOTAL > 0 so re-enter loop core
            JMS SHOTOT      / exceeded threshold, so display subtotal and " + "
            CLA
            DCA TOTAL       / take advantage of free zero
            TAD (PLUS)
            JMS PRINTS
            JMP MLCORE

            / Calculation complete.  Show answer and exit gracefully.
    MLDONE, JMS SHOTOT
            CLA
            TAD (CRLF)
            JMS PRINTS
            JMP ENDG


    ISMOD0
    / If passed AC divides evenly into CURR (in C-speak, CURR % AC == 0)
    / add CURR to TOTAL and return 0 in AC.  Else, return nonzero in AC and
    / leave TOTAL untouched.

    ISMOD0, 0
            / Divide CURR by DIVISOR, passed as AC
            DCA DIVISOR
            TAD CURR        / load CURR into just-cleared AC
            MQL DVI         / move CURR to MQ, divide by DIVISOR...
    DIVISOR,0               / ...quotient in MQ, remainder in AC
            SZA
            JMP I ISMOD0    / remainder nonzero, so leave early

            / Division left AC empty, so CURR divides evenly by DIVISOR!
            TAD CURR        / don't need to clear AC; prior test says AC == 0
            TAD TOTAL
            DCA TOTAL
            JMP I ISMOD0


    SHOTOT
    / Write TOTAL to terminal in decimal, nothing following.

    SHOTOT,0
            CLR
            TAD TOTAL
            JMS DECPRT      / print answer on console, in decimal
            TSF             / wait for terminal to be ready again
            JMP .-1

            JMP I SHOTOT    / and done


    PRINTS

    PRINTS,0
            DCA SADDR       / save AC as string address
    PSNEXT, TAD I SADDR     / load next character
            SNA
            JMP I PRINTS    / found the null terminator; leave

            TSF             / wait for terminal to be ready
            JMP .-1
            TLS             / write character to the terminal

            CLA             / increment string address pointer
            TAD SADDR
            IAC
            DCA SADDR

            JMP PSNEXT      / look at next character
    SADDR,  0


    ENDG
    End program gracefully, either re-entering OS/8 if we can see that
    its entry point looks sane, or halting with the answer in AC so the
    user can see the answer on the front panel.

    ENDG,   CLA
            TAD OS8ENT
            TCA
            TAD OS8INS1
            SNA
            JMP 7600        / re-enter OS/8
            CLR
            TAD TOTAL
            HLT             / not running under OS/8, so halt
    OS8ENT, 7600            / OS/8 entry point
    OS8INS1,4207            / first instruction at that entry point


    DECPRT
    Decimal number printer; see

    PAGE 2
    DECPRT, 0
            DCA VALUE       /SAVE INPUT
            DCA DIGIT       /CLEAR
            TAD CNTRZA
            DCA CNTRZB      /SET COUNTER TO FOUR
            TAD ADDRZA
            DCA ARROW       /SET TABLE POINTER
            SKP
            DCA VALUE       /SAVE
            CLL
            TAD VALUE
    ARROW,  TAD TENPWR      /SUBTRACT POWER OF TEN
            SZL
            ISZ DIGIT       /DEVELOP BCD DIGIT
            SZL
            JMP ARROW-3     /LOOP
            CLA             /HAVE BCD DIGIT
            TAD DIGIT       /GET DIGIT
            TAD K260        /MAKE IT ASCII
            TSF             /OR TAD DIGIT
            JMP .-1         /JMS TDIGIT(SEE 8-19-U)
            TLS             /TYPE DIGIT
            CLA
            DCA DIGIT       /CLEAR
            ISZ ARROW       /UPDATE POINTER
            ISZ CNTRZB      /DONE ALL FOUR?
            JMP ARROW-1     /NO: CONTINUE
            JMP I DECPRT    /YES: EXIT
    ADDRZA, TAD TENPWR
    CNTRZA, -4
    TENPWR, -1750           /ONE THOUSAND
            -0144           /ONE HUNDRED
            -0012           /TEN
            -0001           /ONE
    K260,   260
    VALUE,  0
    DIGIT,  0
    CNTRZB, 0


    END
    / Assembler-generated constants will appear below this in the list file
    $

Allow me to repeat that in most modern programming languages, you get the same result in about 5 lines of code, and you don't need to fob the arithmetic off on `bc(1)`.

Isn't it glorious?