D 2016-12-01T15:26:00.561
L PEP001.PA
N text/x-markdown
P 867307b25b3555a75a2cfb066c5935dc604fa536
U tangent
W 15522
# PEP001.PA
## Or, How I Managed to Spend Three Days Solving FizzBuzz
[FizzBuzz](http://rosettacode.org/wiki/FizzBuzz) is a common test problem for software developers, often seen in interviews. It is [famously](https://blog.codinghorror.com/why-cant-programmers-program/) 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 #1](https://projecteuler.net/problem=1) — 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 PiDP-8/I](wiki?name=Warren%27s+PiDP-8/I+System) 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 time](http://tangentsoft.com/resume/), 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 panel](https://en.wikipedia.org/wiki/Front_panel) 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 printing](finfo?name=examples/routines/decprt.pal) and [ASCII string printing](finfo?name=examples/routines/prints.pal) 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 operator](https://en.wikipedia.org/wiki/Modulo_operation), 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 [KE8/I](http://dustyoldcomputers.com/pdp-common/reference/drawings/peripherals/ke8i.html), 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 [`bc(1)`](https://linux.die.net/man/1/bc) 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 tangentsoft.com, 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 examples/routines/decprt.pal
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?
Z 340ef7ea4da669e58332e9e3dbaaef55