(I’m bored, and I’m tired of talking about the Wuhan virus. So let’s delve into my personal code archive. First, of course, we need a prologue, so bear with me.)
For as long as I can remember, I have been interested in recreational mathematics. And that phrasing is entirely literal: I’m 36, and I have memories from my early childhood involving numbers, math problems, and the fascination that the field produced in me. From a young age, I read through math textbooks for fun (algebra at age 4-5, calculus as early as 9), but I was more drawn to the strange and wonderful ways people used numbers. Puzzles involving math were great fun. I read condensed versions of The Phantom Tollbooth and Flatland while my contemporaries were struggling through Dr. Seuss. My aunt had a kind of children’s encyclopedia, where each volume revolved around a different topic; to this day, I have no idea what was in the other 12 or so, because I only ever read the math one.
Naturally, that led me to computers early on, and you could say that my career as a programmer started when I was 8, the day the teacher of my gifted class handed me a black binder, pointed me towards the Apple II in the back of the room, and sent me on my way into the world of
10 PRINT "MICHAEL RULES!"; 20 GOTO 10. I was hooked, and nearly three decades have not dimmed that fire one bit.
But I still have a passion for numbers, for mathematics in the recreational sense. As an adult, I discovered Donald Knuth’s The Art of Computer Programming, the seminal (and unfinished after some 50 years!) text on the underlying mathematics of programming, and that connected the twin loves of my online life.
Honestly, the books aren’t much help for learning how to code. The edition I have uses a positively ancient assembly language for its examples, and it’s easier for me to understand the concepts from the prose descriptions. But the lessons are still usable today…assuming you need them. Or, in my case, want them.
Chapter 4 is my favorite, as it discusses, well, numbers. A significant chunk of the chapter (itself half a book long) is concerned with the representation of numbers, whether in writing or in computer circuitry, and it was here that I rediscovered the spark of my childhood. And that leads me to one of my solo projects from 2019: Trireme.
What in the world?
Trireme is, to put it simply, a simulation of a fictitious CPU that uses non-binary arithmetic. Now, that doesn’t mean it rejects society’s notions of sexuality. Instead, it rejects society’s notion of how a computer should work. You see, all computers in use today deal in binary numbers. Base-2. 1s and 0s. (Sometimes, you’ll hear talk of hexadecimal, but that’s a human conceit: a single hex digit is nothing more than a group of 4 binary bits.)
But it wasn’t always that way. In the early days of computing, binary wasn’t a given. Quite a few computers from the 50s and 60s used decimal arithmetic. That was harder on the designers, and they often cheated by using some kind of binary-coded decimal scheme internally. (Even today’s x86 processors, such as the one you most likely have in your PC, still have instructions for this kind of number, but they’re disabled most of the time.)
Decimal’s fine. It’s what we use in the real world, so putting it in the virtual world isn’t too big a stretch. What I learned from Knuth’s book, then expanded upon in my online research much later, is that some people went for something even stranger. The Soviets, ever ready to be different from the US, had a weird little machine called Setun. It didn’t use binary numbers. It didn’t use decimal. No, its designers chose something called balanced ternary arithmetic: base-3, but instead of using 0, 1, and 2 as digits (like you’d expect), you use 0, 1, and -1. It’s crazy.
And, in my opinion, beautiful.
I’m a big fan of symmetry. To me, it is the largest component of what makes something aesthetically pleasing. Balanced ternary is a symmetric number system, and thus I find it more intrinsically beautiful than computer binary, where negative numbers have to be represented using either a sign bit (which gives you the possibility of a negative zero) or two’s complement arithmetic (where the maximum negative value doesn’t have a positive counterpart).
Eye of the beholder
I first read about Setun in the Knuth book, as he devotes a small section to balanced ternary for the same aesthetic reasons. From there, I learned the rudiments of the number system, how arithmetic works when some digits are negative by their very nature. And I thought little of it for a decade after that.
In 2009, I was bored (are you sensing a theme yet?), and I got one of my borderline-insane ideas. What if we made a balanced ternary computer today? What would it look like? Setun was a stack-based machine; I won’t go into the details here, but suffice to say, I find stack machines ugly and unwieldy. I much prefer load-store architectures similar to those I’ve programmed in the past: AVR, 6502, etc.
So I designed one. Recall that I have no formal training in CPU design or even electronics. I was just a man with a dream, and I got surprisingly far, considering what little I had to work with. I even went to the most fundamental level, designing logic circuits that could detect and operate on electrical signals that came in three levels, including positive and negative voltage.
(You’d be surprised how well it works. Two transistors of the right type can create a balanced ternary signal. A flip-flop—basically a memory cell—takes fewer than ten. A half adder? Not much bigger. With today’s miniaturization, we could do it, and it wouldn’t be too inefficient.)
In the end, however, I’m a programmer, so my main interest lay in the software to emulate this hypothetical architecture. My first attempt, a decade ago, was…not good. Okay, it wasn’t bad, but it could use a lot of work. The code was not organized well. It relied too much on what are now considered suboptimal structures, and it just didn’t do everything I wanted. Still, I called it a partial success, because I proved to myself that it was possible to make a modern-style processor using non-binary numbers, and that I could do it.
Skip ahead another decade, and I read a forum post mentioning Setun, even linking to an article written about a nearly forgotten experiment from behind the Iron Curtain. That hit me at the right time to rekindle the fire. It’s nothing more than coincidence, really. Perfect timing to snipe my mind.
Trireme was born that night. I chose the name because I wanted something that evoked the number 3 (to represent the ternary aspect), and I didn’t think Trident worked. Plus, I’m a big Civilization fanboy; the trireme is an iconic unit for the series, so why not honor it in this way?
With ten more years of experience, I was smarter about both aspects of the project. I understood more about computer architecture, what worked and what didn’t. As well, I’m a better programmer today than I was then, with much more breadth, and a better grasp on how to write code other people could stand to read.
I wrote the code in Modern C++, because I wanted something fast, but also because I really like the language. (I know, I’m weird that way.) It’s a real program, too, complete with a command-line interface, a rough outline of a plugin system, and a few bells and whistles. Is it complete? Not at all. I’d love to do more with it. Given the chance, I’d like to add more to what’s currently a microcontroller; Trireme needs simulated peripherals, an OS, and much, much more. Despite that, I’m proud to say that it’s mine.
The purpose of Trireme, in as much as it has one, is to answer one question: How much of modern computer science relies on computers using binary arithmetic? As it turns out, quite a lot. Many of our common algorithms are tuned to binary, for instance, as our most of the standards upon which our modern world is built. But I think that’s where something like Trireme can come in handy as a pedagogical tool. It’s always good to think outside the box. Studying such an “alien” computer might give us insight into how to improve our own.
If you’d like to check it out, I’ve put the code for Trireme up as a Github repository. It’s free and open source, and I would love to talk to people who are interested in it. Yes, it needs a lot of improvement, but that’s on the back burner as I work on a few more practical projects. Once I have the spare time, I do want to return to it, make it better.
Why? Because I love numbers. And, strange as it may seem, I have rarely had as much fun programming as when I was working on Trireme. Isn’t that enough?