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