Happy Pi day everyone. This is the Pi machine. It’s a device that progressively approximates
the value of pi, and prints it out digit by digit. The longer you let it run, the more
digits that come out, and the more accurate its approximation gets, all the while you
get to enjoy blinkenlights, a bell ding on each digit, and lots clicking, since yes,
all the computation going on in this machine is being done by electromechanical relays.
But anyways, Pi… I mean everyone likes pi. It’s gotta be the most famous number in
popular mathematics, or at the very least the most famous transcendental. And what’s
not to love? It’s got a name far too easy to pun on dessert items, something about a
circle I guess, and ALL, THOSE, DIGITS. Pedants will argue that every number has an infinite
expansion of digits, but for any rational number those digits end up repeating, and
a lot of irrational numbers you see are just
square roots of a rational number. Pi is transcendental,
which means neither of these apply, and though we haven’t proven it, pi also appears to
be a normal number, which means the digits are as good as random. And yet Pi is one specific
set of random digits that ends up all over mathematics.
As one might expect, there is a proud history of computing this series of digits to greater
and greater precision. There’s the single fraction approximations like 22/7ths or 355/113
usually worked out through geometric reasoning, but things get even more precise when you
define pi as a sum of fractions, since the further you carry out the sum, the tighter
your approximation will get. It’s approaches like these that let Isaac Newton compute 16
places, Ludolph van Ceulen compute 35 [pronounced as 32]
(and engrave it on his tombstone) and much later
let William Shanks set the record for by-hand computations of pi with 707 digits over the
course of his life. Though sadly, due to human error, only 527 of these were correct.
But that was back in the 1800s when work was done with pen and paper. Things really took
off once mechanical computation came on the scene. Suddenly one person with a desk calculator
could compute over a thousand digits, and with electronic computers, that same thousand
digits could be computed in the order of minutes. Then it became hundreds of thousands, then
millions, billions, trillions, and at our current rate, I wouldn’t be too surprised
to see us surpass the quadrillionth digit of pi within a decade or so.
I’ve always liked the idea of a machine that could do one of these pi approximations
right in front of you, kinda like bornach’s “Pi Spigot” where you can get the digits
of pi literally on tap. Absolutely charming, but one of the things I just couldn’t get
over is how you can never be sure with one of these things that the creator isn’t just
“cheating,” and by cheating I mean, it’s just as easy to store the first 10,000 digits
of pi in the device and then stream them out one by one. That’s not computing, that’s
just remembering. Impressive when humans do it, sure, but computers? That’s just lame.
To be clear, as far as I’m aware, the “Pi Spigot” is legit, but it got me thinking.
If there's one thing this world needs,
it's a pi machine you can be sure is doing the computations right in front of you.
Something you couldn’t miss if you tried. Something clicky…
When it comes to digital logic, it’s hard to get much simpler than the relay. It’s
a form of switching that predates integrated circuits, transistors and tubes, since it’s
just a regular mechanical switch but articulated by an electromagnet. Commonly, relays will
have a dual-throw arrangement, so that the center switch jumps between one of two contacts
depending on whether the coil is active or not. In a way, relays are a way for a circuit
to “rewire” itself, kinda like a railroad
switch, and in doing so, with the right connections,
they let you do things like: make a circuit that inverts its input, make a circuit that
only turns on if both inputs are on, make a circuit that latches itself on or off whenever
it gets a pulse, or even one that generates pulses. All the logic gates you’re used
to from digital electronics can be made out of relays, and with enough of them chained
together you can even start to do computation. In fact, the very first electrical computers
were built on relays before work shifted towards the considerably faster vacuum tube.
Doing math with relays works the same exact way you learn arithmetic in elementary school,
except being in binary, it actually ends up being even simpler. I'm sure a number of you
would strongly disagree, but think about it. In base 10, even to do single digit addition,
you need to memorize how to sum 100 pairs
of numbers. In binary, there are only 4 combinations
and it’s easy enough to reduce them down into just a few logic operations. With just
two relays, you can make a circuit like this one, which adds three one bit numbers into
a two bit output. And, just like with by-hand addition, if you
want to add numbers bigger than a single digit, you just chain the smaller addition operations
together with carries. The same works here. String a couple of these adder circuits together,
and you can start adding 4 bit numbers, 8, 16, as wide as you want. This works well for
relatively short numbers, but it still costs 2 relays per bit, which means if you want
to add really long numbers like 128 or 256 bits, this circuit gets really big, and really
expensive. But remember, a four bit adder is really just four copies of the same circuit
doing the same logical operations. We could just as easily re-use one adder and feed in
the inputs for each column one at a time and get the same output. In fact, as long as you
have some form of memory to pass the carry bits from the last column into the next one,
we can set up one adder to add really long numbers one bit at a time. For each pair of
addend bits you stream in, you’ll get out one bit of their sum.
The really cool thing here is that there’s no longer a length limit to the numbers this
circuit can add. It could be one bit, it could be 5 bits, it could be a thousand. They all
take two relays. The only trade-off here is time, since the wider the number is, the longer
it takes to work through all the bits. We can do the other basic arithmetic operations
with relays too. Subtraction is really similar
to addition. A bit shift is basically a multiplication
by two. And you can combine several additions with bit shifts to get multiplication by any
number. In a similar vein, division can be reduced to shifting bits and subtracting.
It works using the same long division algorithm, except, remember how you needed to guess what
the next digit would be, then do a multiplication to check? Well, in binary that multiplication
is either by 0 or 1, so guess and check boils down to just, check. To divide A by B, you
shift in A one bit at a time, and every time your accumulator is greater than B, the next
output digit is a 1 and you subtract B, otherwise it’s a zero and you leave it alone.
In other words, the logic is, “shift in the numerator, subtract if you can.” Using
the building blocks we’ve already established, it’s pretty easy to make a circuit which,
given a denominator, takes the numerator bit by bit, and outputs the quotient bit by bit.
What’s neat about this circuit is that, watching the internal bits, you can see it
get into loops, like here. What you’re seeing is the binary version of a repeating decimal.
Just like how in base 10 ⅓ is 0.33333..., in base 2 it’s .010101...
You’ve probably noticed that for some of this wiring, I’m using printed circuit boards
rather than doing everything by hand, and it’s for good reason. Relay logic circuits
very quickly can devolve into wiring spaghetti. Check out one of my first attempts at a relay
calculator from years ago that I tried to hand wire. This board is functionally equivalent
to these four printed ones. Now, purely hypothetically,
I want you to imagine that there was a bad
component right in the middle of all this… Yeah. Even on neater breadboards though, with
all the mechanical action going on, these relays like to loosen themselves up and just
jump right out of their sockets. Try debugging a circuit like that. That’s why
this time around, I decided to design some common modules into PCBs to clean up the wiring.
Things like adders, subtractors, counters, memory circuits, selectors, and a couple LED
panels for debugging. These boards boil down a lot of the repetitive wiring to traces on
the board, and they even line up the input and output connections, so a lot of the signals
can be carried over ribbon cables 8 bits at a time.
This was actually my first time doing PCB design, and I gotta say, it turned out way
easier than I thought it would be. All you have to do is design the circuit board you want
in KiCAD and then lay out the components on the board. The software will tell you what
pins need to be connected, and then it’s up to you to route traces between them
like the game "Free Flow." (Flow Free, my bad)
I find it makes for a pretty enjoyable puzzle, though maybe if I
was a professional electrical engineer working on much harder routing problems for circuits
with far stricter tolerances this process wouldn’t be quite as fun.
At this point we’ve got the relays, we’ve got the arithmetic circuits. How do we wire
all these things together to actually approximate pi? Luckily for us, there are plenty of different
ways to go about this, from empirical methods, to Monte-Carlo methods, and a slew of different
infinite summations. The algorithm I chose
is a relatively recent one known as the Bailey-Borwein-Plouffe
formula, first discovered in 1995, and it looks like this. You can get it from some
weird integral tricks, which I think Michael Penn does a good job of explaining. What’s
most notable about this formula in particular though, is that it gives us an efficient digit
extraction algorithm for pi. You can actually use this formula, with a few manipulations,
to compute any arbitrary digit in pi, like say the 10 millionth, without actually having
to work out the preceding 9,999,999, just as long as you’re ok with the digits being
in base-16. BBP also isn't the fastest converging approximation of pi, but this superpower of
being able to pick out digits of Pi makes it really useful for confirming the results
of other algorithms when doing long computations of pi.
In our case though, I’m gonna use the original summation, no fancy digit extraction tricks.
And the summation itself is actually pretty eerily well suited for a binary system. All
the multiplications are powers of two. Like, 8k+1 in the denominator; it’s the same as
taking k, shifting it over 3 bits, and filling in a 1. Dividing by 16k is the same as shifting
4k bits to the right. All the numerators of the fractions are powers of two, so, you guessed
it, bit shifts. And maybe a bit more subtly, each iteration of the summation has four terms,
which we can number with exactly two bits. All those observations make this formula in
particular a lot simpler than others to implement in relays. Pull out all the bitwise operations,
and there are really only two arithmetic operations
that we need: division and addition. The relays
here work in two passes for each term. One works out the long-form value of each fraction,
and the other adds that value into the accumulator.
The only other thing I needed to add was a
circuit to count up for each value of k and use that value to fill in the denominators.
That’s the really cool part about there being exactly four fractions, if you use two
bits to determine what fraction we’re on, the whole state machine is just a counter.
The lowest bit decides whether to divide or add, the next two bits pick which fraction
to use, and all the upper bits fill in for k. The other neat thing is that thanks to
the bit streaming tricks from before, this circuit can carry out the calculations to
as many decimal places as you like. The only limiting factor is the number of bits for
k. Well… and we need somewhere to store the
approximation of pi while it’s being computed. I mean, at four bits per decimal digit, you’d
need one more of these boards for every two added digits of precision, and pretty soon
the majority of the relays in this device would just be there to act as memory. Boring!
Plus, I’m not up to soldering all that.
Instead, this is where I cheat. All the computation
happens on relays, but some of the storage happens on an appropriately named raspberry
pi. But, let’s be clear here, only storage, and generating clock pulses. You might say
that me asking for your trust is a little ironic considering the goals of this project.
Anyways, here are all the PCBs hooked together. This section counts what iteration we’re
on, this section does the division, and this one does the addition. The part in between
the rest is the “glue” board, since it passes signals between the other components
and the raspberry pi. And on the raspberry pi, there’s a short program that reads from
to the machine and displays the output on screen. Let it run, enjoy the blinky lights,
all the clickety clicks, and sure enough, that’s pi we’re getting.
Being able to see the results converted to decimal also helps to demystify what exactly
is going on with each pulse. You can watch the result for each division get closer and
closer to the real value the more bits get written out. Having a better look inside the
machine also helped a ton with debugging, which believe me, there was a lot of. I mean,
look at this wiring. The PCBs do a lot to organize things, but even then, it’s still
a bit of a rat’s nest, and it’s way too easy to get wires crossed plugging one board
into another. Even with the PCBs there were problems. One of my designs actually has a
defect in it where, during routing, I accidentally made a trace that crossed positive to negative.
I didn’t even notice until I built and plugged in the board. Luckily this one ended up being
salvageable, since I was able to physically sever the traces and hand wire a jumper around
them. When it comes to bugs though, the absolute
biggest contributor here are the relays themselves.
After all, relays are mechanical objects,
and that gives room for lots of failure modes. I’m lucky enough mine are sealed on the
sides, so I don’t have to relive the moth-filled days of yore, but heat and mechanical wear
are still very real problems. Originally, one of my boards was designed to run at 12
volts, but with all the active relays on it acting like little heaters, it would get pretty
warm in a short amount of time. Not very long into its life, it actually mechanically broke,
and now just generates binary gibberish. Now, everything runs at 6 volts, and is a fair
bit cooler. The other annoying thing is that the memory
latches do occasionally like to stick, ignoring whatever bit was actually supposed to be stored.
This one adds a frustrating level of non-determinism
that seems to be brought about by high clock
rates, bad choices in voltage, and, of all things, gravity. In my testing, I found that
one way I could seriously reduce my error rate was to stand the boards up sideways,
rather than laying on their backs. No kidding. Relays are fickle things, and since I was
getting a little annoyed at long streams of calculations getting ruined by a single misplaced
bit, I added a tiny bit of error correction logic to the raspberry pi. Now, the pi runs
the calculation in tandem with the relays, and if it detects an error, it resets the
relays to a clean state and starts that section over again. Don’t worry, the computation
is still all happening on the relays. This just helps smooth out the occasional glitches
in this electromechanical hardware. And to be clear, I have seen this thing run almost
an hour without a single error occurring. The last two things I felt this machine really
needed were a bell to ding on every successive digit, and a printer to spit out an ever growing
tape of pi. This one is a thermal receipt printer being controlled by the raspberry
pi, but believe it or not, the conversion from binary to base-10 is still happening
on the relays. Base conversions like that aren’t too bad for small integers, but they
get kinda tricky for really long fractional values, since a single binary digit can touch
many decimal digits. The trick I came up with is that each time a digit is computed, I pick
off the integer part of the approximation, and then multiply the whole thing by 10. So
for instance, we pick off the 3, and continue approximating the value 1.4159…, then take
off the 1 and approximate 4.1592… Each time, the next digit is in the integer part of the
number, so it’s always easy to extract. And don’t worry about the multiplication
by 10, since that’s really just two bit shifts and an add. It costs all of four extra
relays to compute, and takes no extra time since it runs in parallel with the addition
step. It’s incredibly minor, but that hack has got to be my absolute favorite in this
machine. But anyways, let’s take a look at the whole
thing in action. Press the start button, and it’s off. And every once in a while *ding*
it spits out a digit. As for speed? Well, this thing is definitely not setting records
anytime soon. At the fastest, I’ve had it running at 32 clock ticks per second, though
20 Hz is much more stable. The runtime also depends on the level of digits you want to
compute, since more digits means more iterations, and each iteration needs to be computed to
more digits of precision. For 6 digits though, it takes under 2 minutes. For 16, it’s about
10 minutes, and 32 takes well over a half hour. It has a quadratic complexity which
means that to reach digit 4,096, which is the furthest this machine should be able to
compute, by my estimates, it would take about a year and a half of non-stop operation, assuming
nothing breaks and I don’t go absolutely crazy from all that loud clicking 24/7. That
same computation on my computer takes about a second. But hey, building relay computers
hasn’t been about speed since the 1940s. And besides, we already know pi to trillions
of digits. For this machine, it’s all about the process. Being able to stretch out the
computation into a more human appreciable timescale. “Savoring the computation,”
one might say, though that one would not be me, since that sounds irredeemably nerdy.
Anyways, there you have it, the relay-powered Pi Machine. I’m gonna be honest, this project
was a tricky one, but I’m pretty happy with how it all turned out, and I learned a lot
from it. Pi approximations, PCB design, relay logic, laser cutting, and let’s not forget
all those crazy bitwise manipulations.
Which reminds me, there is one last ability of this
machine which I’ve so far neglected to mention.
I mean we all know a left bit shift is basically a multiply by two,
and so it’s really cheap to take the value of Pi
we’ve computed and shift it, and basically,
yeah this machine has a Tau mode. I don’t necessarily endorse
it, but like, come on it was just too easy not to implement, and all I could think of was
doubling my ad revenue when June 28th rolls around. Anyways. Happy Pi Day.