PiDP-8/I Software: Changes To PEP001.PA

+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+

# 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 about a week. 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. It ran BASIC, its primary operating systems had a flat directory structure, and real programmers wrote in assembly, just like the microcomputers that came along a decade later. 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 he 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](finfo?name=examples/pep001.pal) is my winning solution to the problem, all 221 well-commented lines of it.

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?













































































1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77	+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +	# 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 about a week. 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. It ran BASIC, its primary operating systems had a flat directory structure, and real programmers wrote in assembly, just like the microcomputers that came along a decade later. 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 he 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](finfo?name=examples/pep001.pal) is my winning solution to the problem, all 221 well-commented lines of it. 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?

Initial version of "PEP001.PA"