Over on my tumblr I’ve been having a bit of fun with number systems. The first post is about how the claim that e is the most efficient radix is wrong, and the other is about how you can use a noninteger, for instance e, can be made to work a radix.
Tumblr
As an experiment I’ve temporarily moved to tumblr. So far I’ve written about why programming languages should be careful when giving access to individual character in a string (individual characters considered harmful) and I’m just starting to write about a really neat hack you can do in smalltalk to look inside functions.
Go on, take a look. You’re at the end of this post anyway.
Bezier
A while ago I got it into my head that I should see if it was possible to render vector graphics on an LCD display driven by an Arduino. Over christmas I finally had some time to give it a try and it turns out that it is possible. Here’s what it looks like.
What you’re seeing there is a very stripped down version of SVG rendered by an Arduino. The processor driving it is 16 MHz and has only 2K of RAM so doing something as computationally expensive as rendering vector graphics is a bit of a challenge. Here’s what a naive implementation with no tuning looks like:
This post is about how the program works and mainly about how I got from the slow and blocky to the much faster and smoother version.
Hardware setup
On the right here is the hardware I’m using (click for a larger image). It’s an Arduino Uno connected to an 1.8″ TFT LCD display, 160 by 128 18bit color pixels, and two 2axis joysticks for navigating. The zooming, rotating, and panning you saw in the videos above was controlled by the joysticks: the top one pans up/down and left/right, the bottom one zooms in and out when you move it up and down and rotates when you move it left and right. I had the Arduino already and the rest, the display and joysticks, cost me around $45.
Software setup
If you open an .svg
file you’ll see that path elements are specified using a graphical operation format that looks something like this
m 157.10609,48.631198 c 0,37.817019 51.99553,51.899082 77.682505,13.390051 C 52.802707,101.94644 2.8939181,85.209645 2.8939181,48.57149 c 0,36.638156 49.6730159,54.2537427 76.5296669,13.344121 l 25.451205,40.4365453 77.682505,24.41472 77.682505,13.403829 z
Each line is a graphical operation: m
is moveTo
, c
is curveTo
, l
is lineTo
, etc. Lowercase indicates that the coordinates are relative to the endpoint of the last operation, uppercase means that the coordinates are absolute.
The first step was to get this onto the Arduino so I wrote a python script that switched to using purely absolute coordinates and output the operations as a C data structure:
PROGMEM static instr_t path[] = { move_to(e(0.0), e(0.0), e(157.10609), e(48.631198)), curve_to(e(157.10609), e(48.631198), e(157.10609), e(86.448217), ...), curve_to(e(79.423585), e(62.021249), e(52.802707), e(101.94644), ...), curve_to(e(2.8939181), e(48.57149), e(2.8939181), e(11.933334), ...), line_to(e(79.423585), e(35.227369), e(104.87479), e(5.2091763)), line_to(e(104.87479), e(5.2091763), e(182.557295), e(29.6238963)), line_to(e(182.557295), e(29.6238963), e(260.2398), e(16.2200673)), line_to(e(260.2398), e(16.2200673), e(157.10609), e(48.631198)), end() };
The macros, move_to
, curve_to
, etc., insert a tag in front of the coordinates. The result is like a bytecode format that encodes the path as a sequence of double
s. The main program runs through the path and renders it, one operation at a time, onto the display. Once it’s done it starts over again.
To implement navigation there is a transformation matrix that is updated based on the state of the joysticks and multiplied onto each of the the coordinates before they’re drawn. For details of how the matrix math works see the source code on github.
This is the same basic program that runs everything, from the very basic version to the heavily optimized version you saw at the beginning – the difference is how tuned the code is.
The display comes with a library that allows you to draw simple graphics like circles, straight lines, etc., and that’s what the drawing routines were initially based on. What it doesn’t come with is an operation for drawing curves so the main challenge was to implement curve_to
.
Bezier curves
The SVG curve_to
operation draws a cubic Bezier curve. I’m going to assume that you already know what a Bezier curve is so this is just a reminder. A cubic Bezier curve is defined by four points: start, end, and two control points, like you see here on the right. It goes from the start point to the end point and along the way gravitates towards first the one control point, then the second one, nice and smoothly.
If you’re given four points, let’s call them , , and so on, the Bezier defined by them is given by these parametric curves in x and y for t going between 0 and 1:
I’ll spend some more time working with this definition in a bit and rather than write two equations each time, one for x and one for y, I’m going to use the 2element vector instead so I can write:
It means the same as the x and y version but is shorter.
Using this definition you can draw a decent approximation of any Bezier curve just by plugging in values of t and drawing straight lines between the points you get out. The smoother you want the curve to be the more line segments you can use. On the right here is an example of using 2, 4, 8, 16, and 32 straight line segments. And on a small LCD you don’t need that many to get a decentlooking result.
First attempts
The graphics library that comes with the LCD supports drawing straight lines so it’s easy to code up the segment approach. On the right is the same video from before of what that looks like with 2 segments per curve. The way it works is that it clears the display, then draws the curve from one end to the other, and then repeats. As you can see it looks awful. It’s so slow that you can see how it constantly refreshes.
The problem is the size and depth of the display. With 160 by 128 at 18bit colors you need 45K just to store the display buffer – and the controller only has 2K of memory. So instead of buffering the line drawing routine sends each individual pixel to the display immediately. Writing a block of data is reasonably fast (sort of, I’ll get back to that later) but writing individual pixels is painfully slow.
Luckily, for what I want to do I really don’t need full colors, monochrome is good enough, so that reduces the memory requirement dramatically. At 1bit depth 160 by 128 pixels is still more than we can fit in memory but it’s small enough though that half does fit. So the first improvement is to buffer half the image, flush it to the display in one block, then clear the buffer, buffer the second half and then flush that.
As you can see that already looks a lot better. The biggest improvement is that there’s no need to clear the display between updates so you don’t see it refreshing at all unless you move the image. Refreshing is also a lot faster because the program takes advantage of sending whole blocks of data. But the drawing is still quite coarse, and refreshing is slow. There is also a short but visible pause between rendering the first and second half. There’s some work to do before this is good enough that you can draw something like a map of Australia from the beginning.
Faster Bezier curves
Most of the rendering time is spent computing points along the Bezier curves. For each t the program is doing a lot of work:
for (uint8_t i = 1; i <= N; i++) {
double t = static_cast<double>(i) / N;
Point next = (p[0] * pow(1  t, 3))
+ (p[1] * 3 * t * pow(1  t, 2))
+ (p[2] * 3 * pow(t, 2) * (1  t))
+ (p[3] * pow(t, 3));
// Draw a line from the previous point to next
}
You can be a lot smarter about calculating this. The general Bezier formula from before can be rewritten as:
where
The four Ks can be calculated just once at the beginning and then used to calculate the points along the curve in a slightly simpler way than the original formula. But there is still a lot of work going on. The thing to notice is that what we’re doing here is calculating successive values of a polynomial at fixed intervals. I happened to write a post about that problem a few months ago because that’s exactly what the difference engine was made to solve. The difference engine used divided differences to solve that problem, and we can do exactly the same.
To give a short recap of how divided differences works, if you want to calculate successive values of a ndegree polynomial, let’s take the square function, you can do it by calculating the first n+1 values,
calculate the distances between those values (the first differences) and then the distances between those (the second difference),
You can then calculate successive values of the polynomial using only addition, by adding together the differences:
You don’t need the full table either, just the last of each of the differences:
We can do the same with the Bezier, except that it’s order 3 so we need 4 values and 3 orders of differences:
Point d0 = /* The same formula as above for t=0.0 */ Point d1 = /* ... and t=(1.0/N) */ Point d2 = /* ... and t=(2.0/N) */ Point d3 = /* ... and t=(3.0/N) */ // Calculate the differences d3 = d3  d2; d2 = d2  d1; d1 = d1  d0; d3 = d3  d2; d2 = d2  d1; d3 = d3  d2; // Draw the segments for (uint8_t i = 1; i <= N; i++) { d0 = d0 + d1; d1 = d1 + d2; d2 = d2 + d3; Point next = d0; // Draw a line from the previous point to next }
For each loop D_{0} will hold the next point along the curve. That’s not bad. At this point we’re only doing a constant amount of expensive work at the beginning to get the four D_{i} and the rest is simple addition. It would be great through if we could get rid of more of the expensive work, and we can.
Let’s say we want n line segments per curve, and let’s define . Then the first four values we need for the differences are:
That makes the four differences:
This means that instead of calculating the full values and the subtracting them from each other we can plug in the four points to calculate the Ks and then use them to calculate the Ds. Coding this is straightforward too:
static const double d = 1.0 / N; // Calculate the four ks. Point k0 = p[0]; Point k1 = (p[1]  p[0]) * 3; Point k2 = (p[2]  p[1] * 2 + p[0]) * 3; Point k3 = p[3]  p[2] * 3 + p[1] * 3  p[0]; // Calculate the four ds. Point d0 = k0; Point d1 = (((k3 * d) + k2) * d + k1) * d; Point d2 = ((k3 * (3 * d)) + k2) * (2 * d * d); Point d3 = k3 * (6 * d * d * d); // ... the rest is exactly the same as above
This makes the initial step somewhat less expensive. But it turns out that we can get rid of the initial computation completely if we’re willing to fix the number of segments per curve at compile time.
Transformations
Even better than calculating the K_{i} and D_{i} for each curve while running would be if we could calculate the D_{i} ahead of time and store those instead of the P_{i}. That way we would only need to do the additions, there would be no multiplication at all involved in calculating the line segments. It should be easy – the Ds only depend on n (through d) and the Ps and all those are known at compile time.
Well actually no because it’s not the compile time known Ps that are being used here, it’s the result of multiplying them with the view matrix, which is how navigation is implemented. And that matrix is calculated based on input from the joysticks so it’s as compile time unknown as it could possibly be.
The matrix transformation itself is simple, it produces a from a by doing:
which I’ll write as
where M is a 3 by 2 matrix. That doesn’t mean that precomputing the Ds is impossible though. If you plug the definition of P’ into the definitions of the Ks and Ds it’s trivial to see that the posttransformation D_{0}, , is simply
It takes a bit more work for the other Ds but it turns out that for all of them it holds that:
Where is the same as except that the constant factor is left out. So
is defined as
So you can precompute the Ds and still navigate the image if you just apply the transformation matrix slightly differently. And calculating the Ds is simple enough that it can be made a compile time constant if the Ps are compile time constant, which they are.
#define K0(P0) (P0) #define K1(P0, P1) ((P1  P0) * 3.0) #define K2(P0, P1, P2) ((P2  (P1 * 2.0) + P0) * 3.0) #define K3(P0, P1, P2, P3) (P3  (P2 * 3.0) + (P1 * 3.0)  P0) #define D0(P0) K0(P0) #define D1(P0, P1, P2, P3) ((((K3(P0, P1, P2, P3) / kN) + K2(P0, P1, P2)) / kN + K1(P0, P1)) / N) #define D2(P0, P1, P2, P3) ((((3.0 * K3(P0, P1, P2, P3) / N) + K2(P0, P1, P2)) * 2.0) / (N * N)) #define D3(P0, P1, P2, P3) (6.0 * K3(P0, P1, P2, P3) / (N * N * N))
With this change the curve drawing routine becomes trivial:
// Read the precomputed ds into local variables Point d0 = d[0]; Point d1 = d[1]; Point d2 = d[2]; Point d3 = d[3]; // Draw the segments for (uint8_t i = 1; i <= N; i++) { d0 = d0 + d1; d1 = d1 + d2; d2 = d2 + d3; Point next = d0; // Draw a line from the previous point to next }
If you compare this with the initial implementation this looks very tight, it’s hard to imagine how you can improve upon drawing parametric curves using only addition. But there is one place.
The thing is, all these additions are done on floatingpoint numbers and the Arduino only has software support for floatingpoint, not native. So even if it’s only addition it’s still relatively expensive. The last step will be to change this to using pure integers.
Fixed point numbers
The display I’m drawing this on is quite small so the the numbers that are involved are quite small too. A 32bit float gives much more precision than we need. Instead we’ll switch to using fixedpoint numbers. It’s pretty straightforward actually. Any floatingpoint value in the input you multiply by a large constant, in this case I’ll use 2^{16}, and then rounded the result to a 32bit integer. Then you do all the arithmetic on that integer, replacing floatingpoint addition, multiplication and division by constants, etc., with the corresponding integer operations. Finally just before rendering any coordinates on the display you divide by the constant, this time by leftshifting by 16, and the result will be very close to the same as you’d have gotten using floating point. You can get it close enough that the difference isn’t visible. And even though the Arduino doesn’t have native support for 32bit integers either they’re still a lot faster than floats.
Multiplying by 2^{16} means that we can represent values between 32768 and 32767, with a fixed accuracy of around 10^{5}. That turns out to be plenty of range for any number we need for this size display even at the max zoom level but the accuracy is slightly too low as you can see in this video:
When going from floating to fixed point directly you end up with these visible artifacts. There is a relatively simple fix for that though. The problem is caused by these two, the precomputed values of D_{2} and D_{3}:
#define D2(P0, P1, P2, P3) ((((3.0 * K3(P0, P1, P2, P3) / N) + K2(P0, P1, P2)) * 2.0) / (N * N)) #define D3(P0, P1, P2, P3) (6.0 * K3(P0, P1, P2, P3) / (N * N * N))
In both cases we’re calculating a value and then dividing it by a large number, the number of segments per curve squared and cubed respectively. Later on, especially when you zoom in, you’re multiplying them with a large number which magnifies the inaccuracy enough that it becomes visible. The solution is to not divide by those constants until after the matrix transformation. That makes the artifacts go away. It’s a little more work at runtime but at the point where we’re doing it we’re working with integers so if N is a power of 2 the division is actually a shift.
At this point the slowest part is shipping the data to the LCD. It turns out there were some opportunities to improve that as well so the very last step is to do that.
Faster serial
The data connection to the display is serial so every single bit goes over just a single pin using SPI. The Arduino has hardware support for SPI on a few pins so that’s what I’m using. The way you use the hardware support from C code is like this (where c is a uint8_t):
SPDR = c; while (!(SPSR & (1 << SPIF))) ;
You store the byte you want to send at a particular address and then wait for the signal that the transfer is done by waiting for a particular bit to be set at a different address. We’re doing this for each byte so that’s a lot of busy waiting for that bit to flip. The first improvement is to flip them around,
while (!(SPSR & (1 << SPIF))) ; SPDR = c;
Now instead of waiting before continuing we continue on immediately after starting the write, and then we wait for the previous SPI write to complete before starting the next one. If there is any work to be done between sending two pixels, and it does take a little work to decode the buffer and decide what to write out, we’re now doing that work first before waiting for the bit to flip.
Also, a great way to make sending data fast is to send less data. By default you send 18 bits per pixel but the display allows you to send only 12. In 12 bit mode you send two pixels together in 3 bytes. You switch to 12 bit mode by changing the init sequence slightly.
Patching these two changes into the underlying graphics library shaves around 25% off the time to flush to the display. It also means that you can’t just load my code and run it against the vanilla libraries but the tweaks you need are absolutely minimal.
The results
That’s it, you’ve seen every single trick I used. Here’s a longer video that shows different segment counts, from quite coarse with a decent frame rate to very smooth but somewhat slow.
When I say “decent frame rate” I don’t mean “Peter Jackson thinks this looks good”. What I mean is that the display is refreshed often enough that when you move the joysticks you get feedback quickly enough that you can actually navigate without getting lost. If it takes 500ms to refresh it becomes almost impossible, or at least really frustrating, to zoom in on a detail; if it takes 150ms it’s not a problem. And with the final version you can do that even at 32 segments per curve. It’s not super pretty but fast enough that using the navigation is not a problem.
If you were so inclined you could squeeze this even more especially if you get a parallel rather than a serial connection to the display to get the flush delay down. The reason I’m actually playing around with Bezier curves is for a different project with different components and those remaining improvements won’t help me for that. But with a parallel connection I do suspect you can get the frame rate as high as 20 FPS with this setup. I’ll leave that to someone else though.
Bernoulli
It’s Ada Lovelace‘s 197th birthday today and the perfect day for my last post about Babbage‘s computing engines. This one is about the famous first program for calculating the Bernoulli series which appeared in Note G of her notes on Babbage’s analytical engine. One of the odd things about this program is that it’s widely known and recognized as an important milestone – but as far as I can determine not widely understood. I haven’t found even one description of what it does and how it does it, except for the original note.
In this post I’ll give such a description. It has roughly three parts. First I’ll give a quick context – what is Note G, that kind of thing. Then I’ll derive the mathematical rules the program is based on. I’ll roughly follow the same path as Note G but I’ll include a lot more steps which should make it easier to digest. Note G is very concise and leaves a lot of steps to the reader and the derivation is quite clever so some of those steps can be tricky. (You can also just skip that part altogether and take the result at the end as given.)
In the last part I’ll write up a modernstyle program in C that does the same as the Note G program and then break it down to get the program itself. Finally I’ll do what you might call a code review of the program.
Okay, let’s get started.
Background
I won’t go into too many general details about Babbage, Ada Lovelace, or the analytical engine. There’s plenty of resources on them and their history on the web, including other posts I’ve written about the difference engine (what motivated it, how did it work) and programming the analytical engine (table code, microcode, and punched cards).
In 1840, after Babbage had been working on the analytical engine for a while, he went to Turin and discussed his ideas with a group of engineers and mathematicians. Based on those conversations one of them, Luigi Menabrea, published an article about the engine in French in 1842. Soon after that Ada Lovelace translated the article into English and Babbage encouraged her to write an original article. She did – sort of – but rather than write a separate article she did it in the form of notes to her translation of Menabrea’s article. Just to give an idea of how much she added, her translation with notes, published in 1843, was three times as long as the original. One of the notes, Note G (they were named from A to G), presented the program I’ll describe in this post.
We’ll get to that very soon but first a few words about what it calculates, the Bernoulli series.
Bernoulli
This is the first few values of the Bernoulli series:
Name  B_{0}  B_{1}  B_{2}  B_{3}  B_{4}  B_{5}  B_{6}  B_{7}  … 
Value  1  ^{1}/_{2}  ^{1}/_{6}  0  ^{1}/_{30}  0  ^{1}/_{42}  0  … 
It’s one of those mathematical objects, like e and π, that keep appearing in different places and seem to have a special significance within the structure of mathematics. One place it appears is in Taylor expansions of exponential and trigonometric functions – for instance, it holds that
The Bernoulli series is not that difficult to compute but it’s not trivial either. If you want to demonstrate the power of a computing engine it’s not a bad choice.
Part of Note G is concerned with deriving a way to calculate the series and that’s what we’ll start with, using the formula above in combination with a second identity, one you’re probably already familiar with, the Taylor expansion of e^{x}:
If we plug this into the lefthand side of the previous equation in place of we get
This means that the original equation can also be written as
Multiplying the denominator from the lefthand side onto both sides we get this identity:
This looks like we’ve gone from bad to worse, right? Both series on the right are infinite and we have an inconvenient variable x stuck in there which we need to get rid of. This is where the cleverness comes in.
We’re not going to multiply these two series together, but if we were to do it we know what the result would look like. It would be a new series in x of the form:
The 1 on the lefthand side even tells us what those coefficients are going to be: c_{0} is going to be 1 and all the remaining c_{i}s are going to be 0. And even though the full product will be infinite, the individual coefficients are all nice and finite; those we can derive. Here is the first one, which we know will be 1:
The only unknown here is B_{0} and if we solve for it we get that it’s 1. Let’s try the next one:
Since we now know what B_{0} is B_{1} is the only unknown; solving for it gives us ^{1}/_{2}. One more time,
Solving for B_{2} gives us ^{1}/_{6}.
In general, if we know the first k1 Bernoulli numbers we can now calculate the k‘th by solving this:
This only gets us part of the way though, it needs to be cleaned and simplified before we can code it. (And again, if you find yourself getting bored feel free to skip to the next section where we start coding).
The first simplification is to solve B_{k} up front. As you can see above the term we’re interested in is always the last one and has the form
This we can solve for in the original equation:
This simplifies the process of calculating B_{k}, we now just have to plug the previous values into this equation to get the next one.
We’ve already computed the first few values of the series so we can calculate the first two terms up front:
Pluggin them back into the formula we get:
As the table of Bernoulli values at the beginning suggested all the numbers at odd indexes greater than 1, B_{3}, B_{5}, etc., are zero. And since we’ve already handled 1 as a special case we can just drop all the odd terms:
Above each B_{i} has two separate factors being multiplied onto it; we can multiply those together to make just one factor:
Since we’re only even interested in even values of k we don’t lose generality if we assume that that k=2n for some integer n.
Okay, now we’re getting close to the final form that we’ll code up but first I’ll have to stop and do something distasteful: I’ll change how we denote the values in the Bernoulli series. What you’ve seen up until this point is the modern, standard use of indices: B_{1} is ^{1}/_{2}, B_{2} is ^{1}/_{6}, B_{3} is 0 etc. In Note G, however, Lovelace numbers the values differently. She skips the first two values and the rest are shifted by 1 so that B_{1} denotes the value we would call B_{2}, B_{2} is what we would call B_{3} and so on:
Value  1  ^{1}/_{2}  ^{1}/_{6}  0  ^{1}/_{30}  0  ^{1}/_{42}  0  … 
Modern  B_{0}  B_{1}  B_{2}  B_{3}  B_{4}  B_{5}  B_{6}  B_{7}  … 
Note G  not used  B_{1}  B_{2}  B_{3}  B_{4}  B_{5}  B_{6}  … 
Up until now I’ve been using (what we call) B_{0} and B_{1} so it made sense to use the modern convention but now we only have terms left that have a name in Note G, so I’ll switch to her convention. This means that I’ll write the formula as
Note that the meaning of n doesn’t change so the formula is almost the same as it was before, the only difference is the numbering of the B_{i}s.
At this point it’s convenient to give the factors being multiplied onto B_{i} a name; we’ll call them . So the above is the same as
where
The second one looks hairy but can be boiled down:
The last step is possible because there is, very conveniently, the same number of terms in the numerator and denominator. What’s useful about this form is that it makes it clear that each of the A_{i}s is the previous one with another factor multiplied onto it (except for A_{0} which is special):
We’re slowly starting to see a program take shape here: if we know the previous B_{i} we can iteratively calculate the sequence of A_{i}s and multiply them onto those values, ultimately giving us the next B_{i}. Now we’ll switch gears and code that up as an actual program.
The program
Let’s quickly recap what all the work above gave us. This formula gives us the next Bernoulli number, given the previous values:
where
Say we wanted to write a program that calculated B_{7} using this approach, that is, the special case where n is 4 (since, as you may vaguely remember, n is the value such that k = 2n – 1).
Let’s take a crack at implementing this in C. We’ll do it twice: first a straightforward implementation that’s quite similar to the Note G program and then we’ll go back over it again and make some modifications to make is (almost) stepbystep identical to Note G.
First, we can assume that the program has been given n and that we have already computed the preceding B_{i}. We’ll store those in some variables.
double n = 4; double B1 = 0.166667; // 1/6 double B3 = 0.0333333; // 1/30 double B5 = 0.0238095; // 1/42
The general idea will be to keep a variable A
that we’ll multiply successive factors onto so it takes the value of , then , etc. We’ll the multiply those factors onto the previous B_{i}, which we’ve already been given, and accumulate the result in another variable, result
.
The first term we’ll calculate directly:
double A = 0.5 * (2 * n  1) / (2 * n + 1); // A0
double result = A;
Then we calculate the second term, , and subtract it from the result:
A = 2 * n / 2; // A1 double term = B1 * A; // B1 A1 result = term; // A0  B1 A1
The we calculate by multiplying the appropriate factor onto :
A *= (2 * n  1) / 3 * (2 * n  2) / 4; // A3 term = B3 * A; // B3 A3 result = term; // A0  B1 A1  B3 A3
And for the last term, , we follow exactly the same pattern except that the factor is slightly different:
A *= (2 * n  3) / 5 * (2 * n  4) / 6; // A5 term = B5 * A; // B5 A5 result = term; // A0  B1 A1  B3 A3  B5 A5 printf("The result is: %g\n", result);
If you run this program it will print
The result is: 0.0333333
which is indeed ^{1}/_{30} also known as B_{7}. This is, in essence, what the Note G program does. It calculates B_{7} using this sequence of steps. However, if you were to look at Note G now what you’d see would still look a bit foreign. That’s because C let’s us do things that the analytical engine doesn’t. For instance, C lets us write complex expressions where the analytical engine only does one operation at a time. In C we also don’t need to worry about recurring expressions like n * 2
because the compiler will make sure it only gets calculated once. The analytical engine obviously had no compiler so the programmer has to do that kind of optimizations by hand.
To take all this into account I’ll rewind and go over the program again but this time I’ll include all the extra work. In the code comments I’ll give how the variables in my program maps to variables in Note G.
First off we have the values we’re given as input:
one = 1.0; // V1 two = 2.0; // V2 n = 4.0; // V3 B1 = 0.166667; // V21 B3 = 0.0333333; // V22 B5 = 0.0238095; // V23
Note G doesn’t use constant values, only variables. So to use the values 1 and 2 it needs two variables that are preinitialized with those values. Also, we’ll assume that all variables are predeclared and start out with the value 0, we won’t bother declaring then anymore.
The first step is to calculate . The C version was:
double A = 0.5 * (2 * n  1) / (2 * n + 1); // A0
double result = A;
and here is the same thing in analyticalenginestyle C:
two_n_minus_one = two_n_plus_one = numerator = two * n; // V4 V5 V6 two_n_minus_one = one; // V4 two_n_plus_one += one; // V5 A = two_n_minus_one / two_n_plus_one; // V11 A /= two; result += A; // V13 current_n = n  one; // V10
If you compare the two versions it should be clear that they do the same thing except that in the latter you get all the excruciating details of the temporary variables. But it’s still pretty straightforward. Notice in the next to last step how we add A
to result
before result
has ever been assigned – we’re using the fact that variables that haven’t been used yet can be assumed to be 0.
The next part of the C program calculates :
A = 2 * n / 2; double term = B1 * A; // B1 A1 result = term; // A0  B1 A1
In analyticalenginestyle this corresponds to:
denominator += two; // V7 A = numerator / denominator; term = B1 * A; // V12 result = term; current_n = one;
Instead of recalculating 2*n
we already have it in a variable, numerator
, and will be decrementing it as we go. Similarly with the denominator
which we’ll increment as we go rather than recalculate. Notice again how we increment denominator
before it has been initialized and rely on it being 0 so it ends up containing 2.
The next step is to calculate :
A *= (2 * n  1) / 3 * (2 * n  2) / 4; // A3 term = B3 * A; // B3 A3 result = term; // A0  B1 A1  B3 A3
In analytical engine style we get:
numerator = one; denominator += one; factor_1 = numerator / denominator; // V8 A *= factor_1; numerator = one; denominator += one; factor_2 = numerator / denominator; // V9 A *= factor_2; term = B3 * A; result = term; current_n = one;
The first two blocks together calculate and the last part subtracts another term from result
. The last part looks very similar:
A *= (2 * n  3) / 5 * (2 * n  4) / 6; // A5 term = B5 * A; // B5 A5 result = term; // A0  B1 A1  B3 A3  B5 A5
In this code we’re using different constants to calculate A than the previous block, and we’re using B_{5} instead of B_{3} in the second step. In the analyticalenginestyle code we’ve already decremented the variables we’re using to calculate A
so that part is exactly the same as for the previous block, but we still need to use B_{5} instead of B_{3}:
numerator = one; denominator += one; factor_1 = numerator / denominator; A *= factor_1; numerator = one; denominator += one; factor_2 = numerator / denominator; A *= factor_2; term = B5 * A; result += term; current_n = one;
That’s it – the value of B_{7} is now stored in result
. The only thing left to do is to store the value in a dedicated variable and then reset some of the other variables so we’re ready to calculate the next B_{i}.
B7 += result; // V24 n += one; // Also reset numerator and denominator.
Now, it might look like we’ve just written the world’s most excruciating C program. In fact what’s we’ve done here is step through, instructionbyinstruction, the Bernoulli program in Note G. If you look through that program here on the right you will notice that for each step there is a corresponding line in the analyticalenginestyle C program above. (For details on how the table program format works see my post on analytical programming.) Click the program to go to an expanded version.
Comparing the programs
Now, if you were to go though the program in details you would notice that what I just said isn’t actually true. There are some small differences between the Cstyle version and what you see in the original notes. Those differences are, I’m afraid, bugs in the original program.
There are three separate issues. The first one is trivial: in step 4 the instruction that should do
A = two_n_minus_one / two_n_plus_one;
is actually switched around and does
A = two_n_plus_one / two_n_minus_one;
That’s a tiny issue that could have been introduced by the printer, and the comment for that step in the table has it the right way round.
Secondly, remember how similar the code for calculating and was, the only difference being that one used B3
and the other B5
? The second issue is that Note G actually overlooks this difference and where the code for should be simply says to repeat the steps for calculating . As you’ll see if you click through to the expanded version, in the white space between steps 23 and 24 there is a comment saying “Here follows a repetition of Operations thirteen to twentythree”.
The third issue is more systematic: the signs are reversed. If you fix the two first issues the result will be correct – except that it has the wrong sign. The sign reversal is also present in the text of the note so I’m not sure if it’s deliberate, but if it is the program calculates something we wouldn’t call the Bernoulli series.
There is also a fourth bonus issue, which is not a bug exactly. At the end in step 25 the code resets some variables such that it’s ready to calculate B_{9}. But if you loop around and run the main program again it won’t give the right result. This is both because some of the variables which the program assumed were 0 on the first run won’t be on the second and because the “loop” after step 23 would need yet another block, this one for calculating . But this is only an issue if you consider the program to calculate the whole Bernoulli sequence rather than just B_{7}.
Now, I want to be sure to put these issues in the right perspective. This is a complex program. I’ve been programming most of my life and it still took me a significant amount of time to understand how it worked. This program was written by a mathematician with no background in programming – they were inventing programming as they went along. On paper. There is an almost frightening intellectual power behind this, both in the program itself and the underlying framework. For me, the fact that we modern programmers, with the benefit of education and experience, can spot a few details out of place is only what you would expect and takes little away from that.
That’s it, you now know how the Note G program works and what each step does. If you’ve found this interesting there’s a good chance you’ll find Lovelace’s original notes interesting too, I recommend reading them. If you want to play around with the program yourself I’ve “ported” it to C; you can find it on github.
Punched Cards
This post is a continuation of analytical programming about the programming model used to program Babbage’s analytical engine. In the previous post I talked about two of the ways programming was used, the table format used to describe programs and the microcode format used internally within the engine. The third program format which is what this post is all about is the one used to feed programs to the engine. (Side note: if this looks familiar it’s because it used to be the second half of that post which you may already have read; I’ve just pulled it out into a separate post)
In some regards the card format is similar to the bytecode formats we know today. That’s one of the reasons I find it especially interesting, because it’s so relatively familiar and relatable for a modern programmer. However, in one regard is is very different from any modern programming model. Babbage felt very strongly that there was a fundamental difference between specifying which operation to perform and which variables to perform the operation on. Modern programming and mathematics has generally moved in the opposite direction, seeing operations and function as values of a different type that can nonetheless be abstracted over much the same way that numeric values can. Babbage would have disagreed strongly with this.
Because of this view a punched card program is divided into two distincts parts: one set of cards containing all the operations to perform and another set specifying the variables to perform them on. For instance, a program that multiplied three numbers, V_{1}, V_{2}, and V_{3} and stored the result in V_{4}, similar the table program from the previous post but using multiplication instead of addition, would be split from the format where operations and variables are together,
V_{1} × V_{2} → V_{4}
V_{3} × V_{4} → V_{4}
and into two separate sets of cards, one giving the operations
and one giving the column indices
In the following I’ll use these colored boxes to represent punched cards. The real punched cards didn’t look anything like this as you’ve seen from the picture at the beginning. For the variable cards I’m also omitting the part that indicates whether reads are clearing or restoring, that would have been there in the original design.
Besides specifying which operation to perform the operation cards all specified how many times the operation should be repeated; using this the operations program above could be specified even more succinctly as
To execute an instruction the engine would first read the operations card and store the number of repeats in a register, the Operation Card Counting Apparatus. Then it would repeatedly perform the operation, decrementing the O.C.C.A for each and reading the next operation card when it reached zero. For each operation it would read as many variable cards as were appropriate for that operation.
In the following I’ll describe each of the instructions understood by the engine. It’s only about a dozen. The number of variable cards for an operation card depends on the repeat count but I’ll show the variable cards that go with a single repetition. I’ll separate the cards representing input and output with an arrow, just to make it easier to read. It’s purely a visual aid though, in practice you had to keep track what the cards meant yourself.
Basic Operations
The most straightforward arithmetic instructions, instruction format wise, are the multiplicative ones. We have multiplication of two columns, V_{i} and V_{j}:
Wait, you might say, didn’t you just show multiplication using just three variable cards? Yes, and that was a simplification. In reality multiplying two 50digit numbers can give you up to 100 digits and as a general principle the analytical wouldn’t discard digits. Instead it would store the most significant 50 digits in one column and the least significant 50 in another. In addition, unlike the difference engine the analytical engine had builtin support for fixedprecision values by allowed you to specify an implicit multiplier which would be taken into account during all operations. This could cause a single multiplication to produce up to 150 digits, hence you need three columns to be able to store the result of any multiplication, called the head, middle, and tail values. If you know your output fits within 50 digits you can use scratch columns for the most significant parts and only use the least significant 50 bits of the output, that’s up to you, but you always have to pass three output variable cards.
Symmetric to multiplication the engine also supported division:
The input/output logistics of this operation are the same as multiplication, the result can be up to 150 digits long. The microcode for division is even more complex than multiplication, as you would probably expect. It’s an iterative approach that first approximates the result by looking just at the most significant digits of both inputs and gradually refines the result by considering more and more less significant digits. Both operations take time proportional to the number of digits of the numbers involved.
Besides arithmetic operations the engine also supported shifting values up and down in base 10, corresponding to multiplying or dividing by powers of 10. Here is the step down operation, what we would call rightshifting:
This instruction shifts the value in V_{i} a steps to the right, effectively dividing the value by 10^{a}. The n as usual specifies how many times to repeat the operation. Like with the multiplicative operations the shift, sorry stepping, operations are somewhat familiar but also quite different. The step up operation takes two parameters: the number of times to repeat the operation and how far to shift the value. Since each operation card only holds one parameter and this one uses two we need to operation cards, the operation itself and a dummy card that has no function but to hold the amount to shift by.
In modern programming shift operations always discard bits, either high or low bits. As we’ve seen Babbage made sure operations never discarded bits. In this case we get two outputs: the shifted value on one column and the bits that were shifted away on the other. Again, if you really intend to discard the bits that were shifted away you can just store them in a scratch column.
Internally the engine had primitives that could shift by 1 and 2 digits in one cycle and the shift card was implemented by repeatedly shifting by 1 digit. If you wanted to shift by an even number there was a separate card that worked the same way as the single shift but repeating the 2digit shift primitive:
This instruction shifts by 2a but uses only a cycles to do it where the single step down operation would take 2a cycles. Symmetrically there are operations for stepping up, what we would call shifting left:
There’s a few things to note about this set of operations. First of all, the amount to shift by is always fixed by an operation card so there is no way to shift by a variable or computed amount, only by a constant. Also, since no values are ever discarded the up/down variants are complementary: stepping up by 26 gives you the same result as stepping down by 24 except that the head and tail of the results are swapped. So you would never step more than 25 in any direction because you could get the same result with fewer cycles by stepping the other way.
Now we get to addition and subtraction. You might think they were among the simpler operations, simpler than division surely, but no, the instruction format is really hairy. The thing is, you very often end up having to perform long sequences of additions and subtractions and if the format was straightforward like division you would end up constantly writing values out to columns and reading them back in. What you really want is to add and subtract a sequence of numbers into a running sum inside the engine’s mill and only once you’ve done store the result in a column. The interface for doing this changed many times and the final result is clearly a work in progress itself. The basic form looks like this:
This instruction first adds a values together, then subtracts b values, and finally stores the result in V_{o}. The second addition card seems a bit random; it’s not clear why it’s even necessary but in any case it’s just an end marker, it doesn’t cause any numbers to be added.
You might be thinking to yourself: surely you need two columns to store the result or you may end up discarding digits? Well yes, sort of. The internal column that stores the running total before it’s transferred out has 3 extra digits of precision so you can safely add and subtract lots of numbers without overflowing. And as long as you’re sure that the final result doesn’t exceed 50 digits then you’re good. If the result does exceed 50 digits then the machine would stop and notify the machine’s operator, presumably by ringing a bell. What he could do to resolve the issue is unclear. But that’s how it worked.
Now, Babbage felt that this was a somewhat limited interface: you have to add first, then subtract, and then you’re done. Sometimes you want to subtract first. Other times you want to add, then subtract, then add some more, and so on. So he experimented with other approaches, like allowing as many add and subtract cards as you want, in any order, terminated by a special F card. Often you want just one addition or subtraction so he introduced two new cards, addonce and subtractonce. Why that’s better than a general add card with a repetition count of one is unclear but presumably they were faster. This was still a work in progress and we don’t know how addition would ultimately have worked if he’d been able to complete his design.
Special operations
The operations I’ve covered so far are the most straightforward ones, the arithmetic operations. The remaining ones are a set of somewhat obscure arithmetic operations and the control structures. I’ll go over the obscure ones first, starting with the operations for counting significant digits.
The oneinput version computes the number of significant digits of a single value, the twoinput version computes the sum of the number of significant digits in two inputs. The oneinput operation is somewhat useful; the twoinput one is more puzzling. It could be implemented using the oneinput version and addition, though this would be a lot less efficient. Babbage must have had some use in mind for both but it’s not clear from his notes what it was.
The analytical engine was a generalization of the difference engine but the goals were much the same: producing arithmetic tables. Hence it seems natural that the analytical engine should have “native” support for difference engine style calculations. This operation provides that support. It performs n iterations of the aorder finite difference tabulation. How finite difference tabulation works is covered in full detail in my post about the difference engine. This operation, which is naturally repetitive, may be the inspiration for having a repeat count on the other operations.
For each iteration you specify the set of columns that hold the differences and the output column. This means that for say 100 iterations you need to specify hundreds of variable cards. It makes sense to some extent, you probably want the output of each iteration to get its own column rather than override the previous value differenceenginestyle. On the other hand, a modern programmer would have used a 50element array and stored the output at successive indexes, rather than duplicate the code 50 times to store the results in what is essentially 50 global variables. The underlying issue is a broader one: the analytical engine only supported what we would call direct addressing, global variables basically. There was no such thing as writing to or reading from a column whose index was computed at runtime, so you had no data structures of any kind, not even flat arrays. Indirect addressing wouldn’t actually have been that difficult to implement but apparently it just hadn’t occurred to Babbage and the differences operation is one of the places where you see the effect.
The last few operations we don’t actually know the instruction format for. The first two are approximate multiplication and division. You’ll remember that multiplication and division take time proportional to the number of digits. If an approximate result is good enough for a computation you can use the approximate versions which works essentially the same way as their accurate counterparts except for a step before the main computation that rightshifts the operands to discard the least significant digits, and in the case of multiplication a step at the end that leftshifts the result back to get the right magnitude.
The last arithmetic operation is doublelength addition which is similar to the addition above but for each operand takes two columns, the head and the tail of a 60digit value, and produces a 60digit result. It’s pretty straightforward really, the only really notable thing about it is that Babbage’s implementation has a subtle bug which may cause the output to have the wrong sign in some cases.
Control
As you may have noticed I’ve been going from the best to the least well understood operations and now we get to the control flow operations, the least well understood of all. Babbage does mention them but spends very little time on them. His focus was on the more challenging operations like the arithmetic ones and control flow, which would be easy to implement mechanically, he more or less ignored. He knew at a high level which kind of control flow the engine should support and knew that it would be easy to implement – so why spend too much time on it at the design phase?
The two control operations we do know is branchifzero and branchifnegative:
The first thing you’ll notice is that the variable cards are different – where normally a variable card specifies a single column, for the control operations they also specify a count. They’re also different in that the argument is not the number of times to repeat the operation because that doesn’t make sense for a branch.
They way both operations work is that first the selected column is checked for whether it’s zero or negative respectively. If the condition is true the operation card stream is moved by a cards and the variable card stream is moved by b cards. It’s not clear which direction the cards are moved but since we know programs that (at least appear to) branch backward it seems plausible that they’re backward branches. Also, looking at the table programs that were written both by Babbage and others there can be little doubt that his intention was for the engine to be what we today call Turing complete. And if the branches go forward it wouldn’t be (though the margin is too small for me to prove that formally).
Note that since the operation and variable cards are moved independently it’s quite possible to run the same operation cards with different variable cards as input as well as the other way round, by branching by unaligned amounts. It also makes programming more error prone though.
Basically it’s clear that the control operations were never fully developed and just because we only know of a limited doesn’t necessarily mean that the finished engine wouldn’t have had a fullfeatured set of control operations. It’s likely that he just never completed the design.
You have now seen the three different ways the analytical engine could be programmed, including the full instruction set as we know it today. Our understanding of the engine is incomplete though and it’s possible that further research into Babbage’s notes will tell us more. But even what we do know gives a clear sense of the flavor of programming the engine supported. My next post will focus on one particular program, the famous first program for computing Bernoulli numbers from Ada Lovelace’s notes on the engine. As you’ve seen the engine is rich in programming and some of it, for instance Menabrea’s small programs above, predate the Bernoulli program. The next post will explain why that program nonetheless deserves to be singled out and celebrated as the first example of what we today understand as programming.
Analytical Programming
This is my third post about Babbage’s calculating engines. The first two were about the difference engine: why it was important at the time and how it worked. This post is about the analytical engine. The analytical engine is famously the first programmable computing machine, and there was much programming involved both in designing and operating it. In this post I’ll take a look at the various ways you could program the engine and the way programs were used to control the engine internally.
Programming the analytical engine
When the analytical engine is mentioned as the first programmable computer the example you almost always see is one particular program, the one for calculating Bernoulli numbers that was given in note G of Ada Lovelace’s notes on the engine. But that’s only the tip of the iceberg. This post is about the rest of the iceberg. (Don’t worry, I’ll give the Bernoulli program a whole post of its own). The engine could be programmed on roughly three different levels and we’ll take a look at each of them in some detail, but first I’ll give an brief overview of each of them.
At the highest level programs were written as tables like the one here on the right. That one is taken from Menabrea’s 1842 article about the engine. Each row in the table is an instruction, a mathematical operation to be performed. In modern terms we would call this a register language since all the operation’s inputs and outputs are given explicitly. This is the format that was used in all contemporary articles about the engine and the format of the Bernoulli program. However, a program in table form could obviously not be run by the analytical engine directly, it was more like what we would call pseudocode today. It describes the program you want to execute but it’s not executable itself.
The way you made executable programs was using punched cards. To run a program written in the table format you would have to translate it into a stack of cards that could be interpreted by the machine. You might think of the cards as a type of bytecode. Babbage seems to have considered this mostly an implementation detail so it’s not super well described, but we still know enough to get a pretty good sense for how cardbased programming would have worked.
At the bottom layer there was an internal “microcode” format that controlled how the engine executed each of the punchedcard encoded instructions. The microcode programs were encoded as rows of pegs on the side of rotating barrels, like the pins on a music box. The pins controlled operations and data flow within the engine and the control flow of the microprograms themselves. Some of the more complex instructions such as multiplication and division had very elaborate implementations of more than a hundred verticals, Babbage’s name for a single microinstruction.
In the rest of this post I’ll describe two of these formats, tables and microcode. The punched card format has a separate post which is linked at the end. First though, a quick note on sources. My source for most of this post is some excellent articles by Allan Bromley: The Evolution of Babbage’s Calculating Engines from 1987 and Babbage’s Analytical Engine Plans 28 and 28a – The Programmer’s Interface from 2000. If you want more information these are the articles to read. (Obscenely they are both behind IEEE’s paywall which I suspect is one reason they’re not as widely read as they deserve to be.)
With that let’s get on to the first language level: tables.
Tables
The basic model of the analytical engine is similar to the difference engine but generalized along several dimensions. The difference engine had 8 columns, what we would call registers, with 31 decimal digits of precision (roughly 103 bits). These could be added together in a fixed pattern, right to left. The analytical engine had a much larger number of columns, Babbage considered 1000 to be realistic, and it could add, subtract, multiply, and divide them in any pattern. The columns also had more precision, 50 decimal digits (roughly 166 bits). Each column had an index, i; the i‘th column is written as V_{i}. The V stands for variable which I’ll use interchangeably with the word column.
The table format for programming the engine, the most highlevel format, represents a sequence of instructions as rows in a table. Each row specifies an operation along with the input and output columns. For instance, to calculate (V_{1} + V_{2} + V_{3}) and store the result in V_{4} you would do something like:
#  op  in  out 

1  +  V_{1} + V_{2}  V_{4} 
2  +  V_{3} + V_{4}  V_{4} 
The first instruction adds V_{1} and V_{2}, storing the result in V_{4}, and the second adds V_{3} to V_{4}. It’s pretty straightforward really – but in this simple example I’ve cheated and omitted a few details. We’ll be adding those back now.
In modern programming languages we’re used to being able to read a variable as many times as we want with no sideeffects. With the analytical engine on the other hand when you read a column what you’re actually doing is transferring the value mechanically from the column to the processing unit, the mill, which causes the column to be cleared. It’s obviously inconvenient if you can’t read a column more than once. To solve this the engine supported two kinds of reads: the simple read where the column is cleared in the process and a the restoring read where the column retains its value. A restoring read works by simultaneously transferring the value to the mill and a temporary storage column and then immediately transferring the value back from temporary storage to the column.
To indicate which kind of read to do there’s an extra field in the table indicating column value changes. If we go back to the program from before, let’s say that we don’t mind that V_{2} and V_{3} are cleared but we need to retain V_{1}. We would express that as
#  op  in  out  vars 

1  +  V_{1} + V_{2}  V_{4}  V_{1} = V_{1} V_{2} = 0 
2  +  V_{3} + V_{4}  V_{4}  V_{3} = 0 
In the first operation we want to restore V_{1} after it’s been read but let V_{2} get cleared. In the second instruction we let V_{3} get cleared and we don’t need to specify what happens when we read V_{4} because that’s where the result is stored.
This program contains the full information you would need to be able to run it on the engine. The original tables annotate programs some more but anything beyond this is more like comments, it doesn’t change the behavior of the program.
One additional piece of information you’ll see in most of the original programs, the one on the right here is another of Menabrea’s, is that all the column names have a second index in superscript. So where I’ve written V_{1} one of the original tables would have something like ^{1}V_{1}. The second index indicates how many times the variable has changed. So ^{1}V_{1} means “the first value stored in V_{1}“, ^{2}V_{1} means “the second value stored in V_{1}, after it had been overwritten once”. This doesn’t mean that you can recover old values of a variable, it’s just for the programmer to keep track of what the current value is of each variable. You can also write ^{0}V_{1} which means the original 0 stored in V_{1} in the case where we haven’t written to that column at all yet. If we add in these indices the program will look like this:
#  op  in  out  vars 

1  +  ^{1}V_{1} + ^{1}V_{2}  ^{1}V_{4}  ^{1}V_{1} = ^{1}V_{1} ^{1}V_{2} = ^{0}V_{2} 
2  +  ^{1}V_{3} + ^{1}V_{4}  ^{2}V_{4}  ^{1}V_{3} = ^{0}V_{3} 
(The ^{0}V_{2} assignment is just a convention, it means the same as resetting V_{2} to its initial state where it contained 0).
This is the language used to write the first computer programs. Even though it’s unusual it will look familiar to any modern programmer familiar with assembly programming. There is no way to specify control flow even though there is some indication in the Bernoulli program that it had been considered. These are basically straightline sequences of mathematical operations on a set of variables. And being pseudocode the conventions weren’t fixed, they were changed and adapted by the authors to fit the programs they were writing.
The microprogram format is at the other end of the spectrum; where the tables were highlevel and meant for communicating programs clearly the microprograms where lowlevel and written and understood only by Babbage, at least until recently.
Microprograms
The analytical engine could perform a number of complex operations including multiplication and division. To give a sense for how complex I’ll give an example of how the engine would multiply two numbers.
Say we instruct the engine to multiply 17932 with 2379. The multiplication logic would first determine which of the operands had the fewest digits and put that in one register. (The computing mill had a number of internal storage columns that were used to hold partial results during individual operations. I’ll call those registers to distinguish them from the useraccessible columns). The other number, the one with most digits would be used to generate a table of all the multiples of that number from 2 to 9, using addition. In this case that’s 17932:
factor  value 

1  17932 
2  35864 
3  53796 
4  71728 
5  89660 
6  107592 
7  125524 
8  143456 
9  161388 
Once this table had been built the engine would scan through the other number, in this case 2379. For each digit it would look up the corresponding multiple in the table, shift it left by an amount corresponding to the significance of the digit (that’s base 10 shift), and add the resulting values as it went:
digit  product 

9

161388

70

1255240

300

5379600

2000

35864000

Adding those four values together you get 42660228, the product of 17932 and 2379, calculated using the primitive operations of addition and multiplication by 10. The whole operation took time proportional to the number of digits of the shortest of the input numbers. Unlike the difference engine which stored numbers as tens complement the analytical engine stored the sign of the number as a separate bit. That way the multiplication could be unsigned and the sign could be computed separately. This meant that the engine had two zeroes, plus and minus.
Back to multiplication. The engine needed an internal control mechanism to take it through this complex process and what it used was a microprogram encoded by pegs on a rotating barrel. You can see a simplified diagram of the barrel here on the right. Each “cycle” of the microprogram proceeds in the same way.
First the barrel is pushed left and the pegs along the vertical edge press against a row of levers which causes them to engage or disengage other parts of the engine. Because of the way the pegs are aligned with the vertical edge of the barrel Babbage called a single such instruction a vertical.
Second, the barrel is pushed to the right and connects to the big gear you see to the right of it in the diagram. That gear, and the gears connected with it, Babbage called the reducing apparatus. That’s what controls the flow of the program. The reducing apparatus rotates the barrel some amount in either direction to select the next vertical to apply. At the same time any other components that were engaged by the current vertical perform their operation, for instance a single step of building the multiplication table. The reducing apparatus takes input from those other components so for instance it may move the barrel different amounts depending on whether the last addition overflowed. That’s the arm on the far right (Babbage called overflow “running up”). The reducing apparatus is controlled by the barrel itself so each vertical explicitly specifies how the reducing apparatus should rotate it to the next vertical. You’ll notice that the three gears you see near the reducing apparatus’ main gear have 1, 2, and 4 teeth respectively. By engaging a combination of them one vertical could have the reducing apparatus rotate the barrel any number of steps between 1 to 7. In modern terms, each microinstruction contains an explicit relative branch, conditional or unconditional, to the next microinstruction. As you can see this is a highly sophisticated and general mechanism. The only disadvantage is that it’s slow – a single cycle takes a few seconds so a multiplication can take several minutes.
As you would expect the diagram above is simplified, in practice there were multiple barrels and they were much larger both in the number of pegs for each vertical and number of verticals per drum. I haven’t been able to find any of Babbage’s actual microprograms unfortunately so for now all I know are the basic principles, and we know that designing them was one of Babbage’s main interests in designing the engine.
The third program format is the punched cards which is what would have been used by an operator of the engine. I’ll look at those in some detail because they give a good sense of what it would have been like to work with the engine in practice. To keep this post to a reasonable length I’ve broken that out into its own post called punched cards.
Difference
This is my second post in a series about Babbage’s mechanical calculating engines. The first post was about why it was so important in the early 1800s to be able to produce accurate arithmetic tables and ended with what I’ll be generous and call a cliffhanger: that Babbage’s difference engine was a groundbreaking solution to that problem. In this post I’ll explain how the difference engine works, how to “code” it and how to interpret what you get back.
Before we get to the engine itself there’s a bit of math to explain the basic principles it works by. To give you a taste of the engine itself before that here is a small JavaScript emulator^{1} that performs a simple calculation. It’s tiny compared to the real engine but works by the same principles just on a smaller scale.
Try stepping it a few times. The model is actually quite straightforward and the computations you can use it for are based on some basic mathematical principles. You can treat it as an exercise before reading the rest if you like: try to work out what it’s calculating, how it does it, and how you can make it calculate other things. Of course you can also just read on an I’ll tell you.
Differences
The difference engine is a very simple device in principle. It’s an adding machine, that’s all it is^{2}. Part of what makes it such an impressive accomplishment is that it took a difficult problem, calculating complex functions, and solved it using a simple enough approach that it could be implemented mechanically using contemporary technology^{3}.
So, how do you calculate complex functions using just addition? Obviously you can’t in general so let’s start off easy by looking just at polynomials.
Consider this simple polynomial, the square function:
The first few values are
The difference engine is based on a technique called divided differences. Divided differences is similar to differentiation but simpler and it’s based on simple arithmetic. It works as follows. You take the values of your polynomial at a fixed interval, here we’ll use the first four values from before:
Then you find the distance between each successive pair of them:
These are the first differences. Then you find the distance between the first differences the same way:
These are the second differences. And one last time to get the third differences:
You can see the similarity to differentiation: it’s a polynomial of degree 2 so the first differences increase linearly just like the first derivative, the second differences are constant just like the second derivative, and so on. We don’t actually need the third differences, they’ll all be 0 anyway, so I’ll leave those out below.
What’s neat is that once you have these values you can extend the table using nothing but addition. You know the difference between the first derivatives is fixed, 2, so you can get the next first derivative by adding 2 to the previous one. And you know the difference between the function values is the first differences so you can get the next value just by adding the next first difference to the previous function value. Okay maybe it’s easier to explain with a concrete example:
Notice that we don’t need the full table at this point, we only need that for calculating the initial values. All we need to generate more values is the last of each of the differences:
This provably works for any polynomial. To generate a sequence of values for a polynomial of degree n all you need is n+1 initial values; from the values you calculate the table of differences using subtraction, and from there on you can calculate as many successive values as you like using just addition. You don’t even need to know the closed form of the polynomial as long as you can evaluate the initial values at fixed intervals.
This is the basic principle of the difference engine, and what it’s named after. The engine has 8 integer registers called columns that can each hold a 31digit integer value which represent the current value of the function and the first to the seventh difference. By cranking the handle those values are added together from right to left. Here is a another miniemulator, this one calculating the square function using the differences we just calculated:
You can see the values are being added together from right to left and the current function value in the leftmost column is printed for each emulated crank on the handle. Printing was also a part of the original difference engine. A common source of errors in mathematical tables was typesetting so to avoid that step the engine would automatically stamp its output in a soft material that could be used directly for printing, as well as print a log on paper.
Being able to evaluate an integer polynomial is just the beginning though. First of all, integers aren’t enough, we need to be able to evaluate realvalued functions. Secondly, so far we’ve only seen positive values, we also need negatives. Finally, polynomials can be useful in themselves but we’re really more interested in more complex functions like logarithms and trigonometric or astronomical functions. But with a few tricks the difference engine can handle all those things.
Precision
First off: how do we use this to evaluate realvalued functions? You use fixedpoint decimal numbers. For instance, say we want to plot the square function from before but this time in steps of 0.25:
These are fractional numbers but if you multiply them by 10^{5} we’re back to integers
Now we’re back to something the engine can calculate:
I’ve added a line between the digits to mark where the decimal point goes. It also gets added to the output (I don’t believe the original engine did this). But the decimal point is purely a matter of interpretation by the operator, the adding mechanism is not aware of it, it’s operating purely on 6digit integer values.
In this case we were lucky because there was a relatively small factor of 10 we could multiply onto the values to get integers without losing precision. That’s unlikely to be the case in general. If you can’t use this trick you multiply the values with as large a factor of 10 as you have precision for and just bite the bullet, round the scaled values to the nearest integers and lose some accuracy. That’s not necessarily as bad as it sounds. The original design had 31 digit precision in base 10 which corresponds to roughly 103 bits, well beyond the already quite large 64bit integers on most modern machines. So you can afford to scale the values up quite a bit before rounding. We’ll see an example in a bit of how long it takes for errors to accumulate.
Negative values
To represent negative values we use the exact same trick as with binary numbers, just in base 10: tens complement. A negative number d is represented as 10^{n}  d where n is the number of decimal digits, so 1 is represented by 999…999 and so forth. The adding mechanism itself has no concept of negative values, just like with twos complement the correct behavior just falls out of how overflow works. It’s up to the operator or printer to interpret the output correctly as signed or unsigned values.
Here is an example of a function that starts off positive, peaks, and then descends into the negative numbers.
You’ll notice that the numbers in the columns are all positive but the ones that represent negative values are printed as negative. As with the decimal point that’s a hack I added in the printer which makes it print smaller integer values as positive and larger ones as negative. But it’s purely a matter of interpretation, the calculating part of the engine is oblivious.
Polynomial approximation
Okay, now we’re getting close to the goal: being able to produce accurate arithmetic tables of general functions.
In my previous post the main example of how important mathematical tables were was how astronomical tables were used by mariners to navigate by lunar distance. I don’t actually know the math underlying those astronomical tables so here I’ll use an example I do understand: trigonometric functions. On the right here is a table of trigonometric functions from 1785. It gives 7 digits of the values of 8 different trignonmetric functions, sin, cos, tan, etc., for each arcminute between 0° and 45°. There’s 60 arcminutes to one degree so that’s 2700 values for each function, 21,600 values in total. The author of this table, Charles Hutton, said about this edition in a later one that it had so many errors that is was basically useless:
Finding, as well from the report of others, as from my own experience, that those editions [...] were so very incorrectly printed, the errors being multiplied beyond all tolerable bounds, and no dependence to be placed on them for any thing of real practice [...]
For this last part about how to calculate complex functions I’ll show how to replicate one column, sin, of this table.
Since we know how to evaluate polynomials the solution that first springs to mind is to approximate the function we want to calculate using a polynomial. Taylor polynomials were well known at this time so that’s an obvious approach. Taylor’s theorem says that for an infinitely differentiable function f (which sin is),
where f^{(k)} means f differentiated n times and a is any point on the function. Since the engine only has 8 columns and we need n+1 columns for a polynomial of degree n we have to limit ourselves to at most the first 7 terms. And in fact, since I want to demonstrate this with the emulator in a little bit and 8 columns of 31 digits takes up an enormous amount of space we’ll limit ourselves even more in this example to 4 columns of 13 digits. This means that we’ll use only the first 3 terms of the Taylor polynomial. For sin those are:
(Conveniently all the even degree terms are 0). This approximates sin quite well around 0 so we’ll use that as the basis for generating the table.
To calculate the differences we first need to produce n+1 values at fixed intervals. The generated table should have an entry per arcminute so we’ll start at 0′ and do steps of 1′:
x  sin(x) 

0′  0 
1′  2.909 10^{4} 
2′  5.818 10^{4} 
3′  8.727 10^{4} 
Then we need to find the nth differences:
x  sin(x)  Δ_{1}  Δ_{2}  Δ_{3} 

0′  0  2.909 10^{4}  2.461 10^{11}  2.461 10^{11} 
1′  2.909 10^{4}  2.909 10^{4}  4.923 10^{11}  
2′  5.818 10^{4}  2.909 10^{4}  
3′  8.727 10^{4} 
All of this is a matter of evaluating a polynomial so that’s not super hard to do by hand with as many decimals as you need, as long as you only need a few of them. From this table we take the last of each of the differences and that’ll be the starting point for the calculation:
0.000872664515235
0.000290888130722
0.000000000049228
0.000000000024614
At this point we need to decide how much accuracy we want, that is, where we want the fixed decimal point to be. We have 13 digits which gives us room enough to multiply by 10^{13} before rounding. That gives us these integer values:
8726645152
2908881307
492
246
And now we’re ready to get tabulating:
If you follow along with the original table you can see that it generates exactly the same values. The values generated by the engine continue to match the table values until 1° 1′, 57 values in, where the table says 0.0177432 and the engine produces 0.0177433, and after that it continues to produce matching values up until 1° 53′, more than 100 values in.
Not bad right? And remember, this is a simplified emulator that can only calculate the third degree approximation where the original could go up to the seventh, and only with 13 digits of precision where the original had 31.
So what’s the source of the deviation? There’s two: the approximating polynomial and the accumulating error of the engine. Let’s first look at the polynomials.
The first plot on the right is of how quickly the approximating polynomials of different degrees deviate from the true sine function. At 1° the approximations are still well within 0.01 billionth of the correct value. Like I said, near 0 these polynomials approximate sin really well.
This suggests that the main source of inaccuracy is the engine itself, the precision we had to discard when fixing the decimal point, and as you can see in the second graph, it is. The engine loses precision faster than the polynomial by a large factor. This makes sense because the inaccuracy accumulates for every step.
Luckily in this case the polynomial deviates slowly enough we can use it to calculate new almostaccurate initial values at fixed intervals, for instance for each degree, and reset the machine to those. However, eventually the polynomial itself will deviate too much and at that point we can use the fact that the Taylor polynomial has an a parameter that specifies the point around which we’re approximating. So say the polynomial that approximates around 0° becomes too inaccurate at 6° we can derive a Taylor polynomial around 6° and use that to continue the calculation. Indeed, since the polynomial approximates equally well on both sides of the point we might as well approximate around 9° and use it for all values between 6° and 12°.
Sin is a relatively easy function to approximate in this way, a function such as log is harder but the same basic principles apply to harder functions. It’s a matter of how often you need to reset to get rid of the accumulating errors and how long the same approximating polynomial remains accurate.
One of the weak points of the engine is that even though it requires less manual work than producing a table completely manually, there’s still a fair amount of manual analysis and computation to be done. That’s not a killer in itself though. Even if it took just as much work to operate, which it surely wouldn’t have, just having a different way to create these tables would have been immensely valuable since two different approaches are likely to produce different errors and hence can be used to crosscheck each other. But as this illustrates, even if the engine had been built it was definitely not a matter of just plugging in a few values and then going to lunch, using it involved a fair amount of work^{4}.
The revolution that didn’t happen
Here’s a video of the only difference engine ever built which was completed in 2002.
Babbage tried to build it and ultimately gave up for a number of reasons including family problems, financial problems, problems working with his engineer, and his gradual change of focus to the analytical engine. Despite what you often hear the technology did exist to build it; the modern one was built from his designs and only with technology that would have been available back then.
It also appears that Babbage’s interests and those of the English government who paid for the whole thing were just too far apart. Babbage was interested in the machine itself whereas his sponsors just wanted accurate tables, whatever way Babbage could produce them. It’s a shame really. It seems from what I’ve read that the difference engine was a failure not of vision or technology but of product management. The technology was so promising that if a successful prototype had been built and he’d delivered the tables the English government wanted it’s not unlikely that they would have continued to fund research in more advanced engines. The ground would have been fertile for mechanical calculation on a larger scale by the mid 1800s. Obviously that wouldn’t have meant a mechanical iPad in every home by 1900 but it would certainly have been a better outcome than what happened, that the designs went in the drawer.
Ultimately Babbage moved on to the analytical engine, the first ever programmable computer. My next post will be about that and in particular the first ever software programs which were written for it.
Sources
For more information about the difference engine a quick introduction is given in the first part of Menabrea’s Sketch of the Analytical Engine from 1842. A more detailed description, including of the underlying mechanics of the engine, can be found in Lardner’s Babbage’s Calculating Engine from the July 1834 edition of the Edinburgh Review.
Notes
1: While the emulator performs the same type of calculations as the difference engine it actually looks nothing like it. I made a point to give the emulator a mechanical feel but it’s inspired more by the Curta calculator, the mechanical calculator I know best, not the difference engine. Note also that I have only tested it on the browsers I have easy access to, Chrome, Firefox, Opera, and Safari on mac. If it doesn’t work on your platform the code lives on github and patches are welcome.
2: Ada Lovelace in her famous notes about it is almost contemptuous of how simple it is compared to the analytical engine:
The Difference Engine can in reality [...] do nothing but add; and any other process [...] can be performed by it only just to the extent in which it is possibly, by judicious mathematical arrangement and artifices, to reduce them to a series of additions.
3: Incidentally, much of the underlying math was developed before Babbage by J. H. Müller.
4: I wonder if it’s possible to automate some of the manual work involved in operating the engine using the engine itself, like calculating initial values.
Tables
I have a thing for mechanical calculators and it recently occurred to me that I knew almost nothing about two of the most famous ones: Babbage’s difference engine and analytical engine. This led me to read some of the papers from the mid 1800s that were written about them. This blog post is the first of a few I’m planning to write about that.
The analytical engine usually gets most of the attention but the difference engine is an interesting invention in its own right. Not only did it solve an important problem, it is the only one of the two that was complete enough to actually be built. This post about what made the difference engine so important that Babbage spent decades trying to build it and why British government was willing to pay the bill of over ₤17,000, more than the price of two warships.
Calculation
Today computation is cheap. Extremely cheap. Imagine the amount of math that goes into just displaying the image on your screen right now: the layouts, colors, and fonts, rendering it all on a physical display, and doing it again and again quickly and smoothly enough that you don’t even notice it’s happening.
Computation is so cheap that it’s easy to forget how expensive it was before electronic calculators. It used to be that if you wanted to add two numbers together you had to actually add those numbers together. Manually. Need to multiply or divide two numbers, even just a few digits? Then you’ll have to get the paper out and do long multiplication or long division. I just did a long multiplication to make the image on the right here. I got it wrong twice before getting it right and I went from “this’ll be fun, I wonder if I still remember how to do this” to “god this is so tedious” in about 30 seconds.
And those are just the basic building blocks of doing a calculation. Most interesting computations like calculating interest or the position of the moon in six months require you to do these manual computations over and over and over again. Or require operations that you can’t easily calculate by hand, like trigonometric functions.
At this point you might be thinking: who cares where the moon is in six months? It turns out, back in those days a lot of people did. In some cases people’s lives depended on it.
Lunar Navigation
On the right here is a table of distances in degrees on the night sky from the center of the moon to various stars at particular times. The first line gives the distance between the center of the moon and Aldebaran on March 3, 1775 at noon, 3, 6, and 9 o’clock. Multiply that by 365 days, then multiply it by a dozen stars, that gives you just some of the tables in this book, the first edition of the Nautical Almanc and Astronomical Ephemeris from 1774, published from the Royal Greenwich Observatory. The audience for the almanac were mariners. The first edition of 10,000 copies sold out immediately.
To determine your longitude at sea you need to know the current time at a fixed point. You can think of it sort of like navigating with time zones. If you know it’s 4 o’clock in the afternoon Greenwich and it’s noon where you are (which you can tell by looking at the sun) then you know you’re in the 4 time zone which is the one that goes through eastern Canada, the eastern Caribbean and central South America. This is a rough analogy but that’s the gist of how it works.
Up until around 1850, before accurate clocks were made that could be carried on long voyages, a reliable way to determine the current time was using lunar distance. The moon and stars in the night sky move as a perfectly predictable clockwork. A given configuration occurs only once, and you can calculate in advance precisely what the sky is going to look like at a later time. And more importantly you can go the other way: given the precise configuration of the sky you can calculate exactly what time it is.
Actually you don’t need the full configuration; all you need to know to calculate the time is the distance in degrees from the center of the moon to any star. That’s where the almanac comes in. It precomputes those distances so that all a navigator needs to do is measure the angle (typically using a sextant) and then look the value up in the almanac. Okay that’s actually just the basic principle, there’s a lot more to it in practice: you have to adjust for the distance from the center of the moon to the circumference, for your position on the earth, for atmospheric refraction, etc. Being a navigator takes a lot of skill. How do you make those adjustments by the way? More tables of course.
All this means that having accurate tables is extremely important. An undetected error in the almanac means a navigation error which can mean shipwreck. This is made worse because many of these tables are time dependent: one line in the almanac is useful on one day only. As a navigator you’re basically beta testing the data for every single day because nobody has had any reason to use the data before.
There are many sources of errors in numerical tables. Teams of human computers carried out the manual calculations, a tedious and error prone process. (Incidentally, it turns out that the better an understand you have of the calculation you’re carrying out the more likely you are to make mistakes as a computer.) Often the same value would be calculated by more than one human computer and then compared to catch errors – but checking is an error prone process in itself, and computers can (and did) copy from each other. Then finally someone has to manually set the values in movable type and print them, also an obvious source of errors.
Enter Charles Babbage.
Babbage
Babbage was an unorthodox and very gifted mathematician. He was a fan of Leibniz which was still something of a heresy at his college Trinity, home of Newton, Leibniz’s arch rival. He was also one of the founders of the Analytical Society whose goal it was to replace Newton’s formalism for calculus with Leibniz’s. Incidentally, besides inventing calculus independently from Newton Leibniz designed a mechanical calculating machine, the stepped reckoner.
Babbage recognized the problem of calculating tables, as most people did, but also had a solution: the difference engine. The idea behind the difference engine is that most of the functions you want to create tables for can be approximated by a polynomial. Here is the sine function along with three approximating polynomials of increasing degree:
As the degree of the polynomial increases the approximation quickly becomes better – the degreeseven polynomial is quite close:
Babbage’s idea was to use mechanical means to calculate the approximating polynomials with high accuracy not just print the result on paper but do the actual typesetting to eliminate even the typographer as a source of errors.
But I’ll stop here before we get to the juicy details of how the difference engine works and save that for my next blog post.
0x5f3759df (appendix)
This post is an appendix to my previous post about 0x5f3759df
. It probably won’t make sense if you haven’t read that post (and if you’ve already had enough of 0x5f3759df
you may consider skipping this one altogether).
One point that bugged me about the derivation in the previous post was that while it explained the underlying mathematics it wasn’t very intuitive. I was basically saying “it works because of, umm, math“. So in this post I’ll go over the most abstract part again (which was actually the core of the argument). This time I’ll explain the intuition behind what’s going on. And there’ll be some more graphs. Lots of them.
The thing is, there is a perfectly intuitive explanation for why this works. The key is looking more closely at the floattoint bitcast operation. Let’s take that function,
int float_to_int(float f) { return *(int*)&f; }
and draw it as a graph:
This is a graph of the floatingpoint numbers from around 1 to 10 bitcast to integers. These are very large integers (L is 2^{23} so 128L is 1 073 741 824). The function has visible breaks at powers of two and is a straight line inbetween. This makes sense intuitively if you look at how you decode a floatingpoint value:
The mantissa increases linearly from 0 to 1; those are the straight lines. Once the mantissa reaches 1 the exponent is bumped by 1 and the mantissa starts over from 0. Now it’ll be counting twice as fast since the increased exponent gives you another factor of 2 multiplied onto the value. So after a break the straight line covers twice as many numbers on the x axis as before.
Doubling the distance covered on the x axis every time you move a fixed amount on the y axis – that sounds an awful lot like log_{2}. And if you plot float_to_int
and log_{2} (scaled appropriately) together it’s clear that one is an approximation of the other.
In other words we have that
This approximation is just a slightly different way to view the linear approximation we used in the previous post. You’ll notice that the log_{2} graph overshoots float_to_int
in most places, they only touch at powers of 2. For better accuracy we’ll want to move it down a tiny bit – you’ll already be familiar with this adjustment: it’s σ. But I’ll leave σ out of the following since it’s not strictly required, it only improves accuracy.
You can infer the approximation formula from the above formula alone but I’ll do it slightly differently to make it easier to illustrate what’s going on.
The blue line in the graph above, float_to_int
(v), is the i
in the original code and the input to our calculation. We want to do integer arithmetic on that value such we get an output that is approximately
the integer value that, if converted back to a float, gives us roughly the inverse square root of x. First, let’s plot the input and the desired output in a graph together:
The desired output is decreasing because it’s a reciprocal so the larger the input gets the smaller the output. They intersect at v=1 because the inverse square root of 1 is 1.
The first thing we’ll do to the input is to multiply it by 1 to make it decrease too:
Where before we had a very large positive value we now have is a very large negative one. So even though they look like they intersect they’re actually very far apart and on different axes: the left one for the desired output, the right one for our workinprogress approximation.
The new value is decreasing but it’s doing it at a faster rate than the desired output. Twice as fast in fact. To match the rates we multiply it by 1/2:
Now the two graphs are decreasing at the same rate but they’re still very far apart: the target is still a very large positive value and the current approximation is a half as large negative value. So as the last step we’ll add 1.5LB to the approximation, 0.5LB to cancel out the 1/2 we multiplied it with a moment ago and 1LB to bring it up to the level of the target:
And there it is: a bit of simple arithmetic later and we now have a value that matches the desired output:
The concrete value of the constant is
Again the approximation overshoots the target slightly the same way the log_{2} approximation did before. To improve accuracy you can subtract a small σ from B. That will give a slightly lower constant – for instance 0x5f3759df
.
And with that I think it’s time to move onto something else. I promise that’s the last you’ll hear from me on the subject of that constant.
0x5f3759df
This post is about the magic constant 0x5f3759df
and an extremely neat hack, fast inverse square root, which is where the constant comes from.
Meet the inverse square root hack:
float FastInvSqrt(float x) { float xhalf = 0.5f * x; int i = *(int*)&x; // evil floating point bit level hacking i = 0x5f3759df  (i >> 1); // what the fuck? x = *(float*)&i; x = x*(1.5f(xhalf*x*x)); return x; }
What this code does is calculate, quickly, a good approximation for
It’s a fairly wellknown function these days and first became so when it appeared in the source of Quake III Arena in 2005. It was originally attributed to John Carmack but turned out to have a long history before Quake going back through SGI and 3dfx to Ardent Computer in the mid 80s to the original author Greg Walsh. The concrete code above is an adapted version of the Quake code (that’s where the comments are from).
This post has a bit of fun with this hack. It describes how it works, how to generalize it to any power between 1 and 1, and sheds some new light on the math involved.
(It does contain a fair bit of math. You can think of the equations as notes – you don’t have to read them to get the gist of the post but you should if you want the full story and/or verify for yourself that what I’m saying is correct).
Why?
Why do you need to calculate the inverse of the square root – and need it so much that it’s worth implementing a crazy hack to make it fast? Because it’s part of a calculation you do all the time in 3D programming. In 3D graphics you use surface normals, 3coordinate vectors of length 1, to express lighting and reflection. You use a lot of surface normals. And calculating them involves normalizing a lot of vectors. How do you normalize a vector? You find the length of the vector and then divide each of the coordinates with it. That is, you multiply each coordinate with
Calculating is relatively cheap. Finding the square root and dividing by it is expensive. Enter FastInvSqrt
.
What does it do?
What does the function actually do to calculate its result? It has 4 main steps. First it reinterprets the bits of the floatingpoint input as an integer.
int i = *(int*)&x; // evil floating point bit level hack
It takes the resulting value and does integer arithmetic on it which produces an approximation of the value we’re looking for:
i = 0x5f3759df  (i >> 1); // what the fuck?
The result is not the approximation itself though, it is an integer which happens to be, if you reinterpret the bits as a floating point number, the approximation. So the code does the reverse of the conversion in step 1 to get back to floating point:
x = *(float*)&i;
And finally it runs a single iteration of Newton’s method to improve the approximation.
x = x*(1.5f(xhalf*x*x));
This gives you an excellent approximation of the inverse square root of x. The last part, running Newton’s method, is relatively straightforward so I won’t spend more time on it. The key step is step 2: doing arithmetic on the raw floatingpoint number cast to an integer and getting a meaningful result back. That’s the part I’ll focus on.
What the fuck?
This section explains the math behind step 2. (The first part of the derivation below, up to the point of calculating the value of the constant, appears to have first been found by McEniry).
Before we can get to the juicy part I’ll just quickly run over how standard floatingpoint numbers are encoded. I’ll just go through the parts I need, for the full background wikipedia is your friend. A floatingpoint number has three parts: the sign, the exponent, and the mantissa. Here’s the bits of a singleprecision (32bit) one:
s e e e e e e e e m m m m m m m m m m m m m m m m m m m m m m m
The sign is the top bit, the exponent is the next 8 and the mantissa bottom 23. Since we’re going to be calculating the square root which is only defined for positive values I’m going to be assuming the sign is 0 from now on.
When viewing a floatingpoint number as just a bunch of bits the exponent and mantissa are just plain positive integers, nothing special about them. Let’s call them E and M (since we’ll be using them a lot). On the other hand, when we interpret the bits as a floatingpoint value we’ll view the mantissa as a value between 0 and 1, so all 0s means 0 and all 1s is a value very close to but slightly less than 1. And rather than use the exponent as a 8bit unsigned integer we’ll subtract a bias, B, to make it a signed integer between 127 and 128. Let’s call the floatingpoint interpretation of those values e and m. In general I’ll follow McEniry and use uppercase letters for values that relate to the integer view and and lowercase for values that relate to the floatingpoint view.
Converting between the two views is straightforward:
For 32bit floats L is 2^{23} and B is 127. Given the values of e and m you calculate the floatingpoint number’s value like this:
and the value of the corresponding integer interpretation of the number is
Now we have almost all the bits and pieces I need to explain the hack so I’ll get started and we’ll pick up the last few pieces along the way. The value we want to calculate, given some input x, is the inverse square root or
For reasons that will soon become clear we’ll start off by taking the base 2 logarithm on both sides:
Since the values we’re working with are actually floatingpoint we can replace x and y with their floatingpoint components:
Ugh, logarithms. They’re such a hassle. Luckily we can get rid of them quite easily but first we’ll have to take a short break and talk about how they work.
On both sides of this equation we have a term that looks like this,
where v is between 0 and 1. It just so happens that for v between 0 and 1, this function is pretty close to a straight line:
Or, in equation form:
Where σ is a constant we choose. It’s not a perfect match but we can adjust σ to make it pretty close. Using this we can turn the exact equation above that involved logarithms into an approximate one that is linear, which is much easier to work with:
Now we’re getting somewhere! At this point it’s convenient to stop working with the floatingpoint representation and use the definitions above to substitute the integer view of the exponent and mantissa:
If we shuffle these terms around a few steps we’ll get something that looks very familiar (the details are tedious, feel free to skip):
After this last step something interesting has happened: among the clutter we now have the value of the integer representations on either side of the equation:
In other words the integer representation of y is some constant minus half the integer representation of x. Or, in C code:
i = K  (i >> 1);
for some K. Looks very familiar right?
Now what remains is to find the constant. We already know what B and L are but we don’t have σ yet. Remember, σ is the adjustment we used to get the best approximation of the logarithm, so we have some freedom in picking it. I’ll pick the one that was used to produce the original implementation, 0.0450465. Using this value you get:
Want to guess what the hex representation of that value is? 0x5f3759df
. (As it should be of course, since I picked σ to get that value.) So the constant is not a bit pattern as you might think from the fact that it’s written in hex, it’s the result of a normal calculation rounded to an integer.
But as Knuth would say: so far we’ve only proven that this should work, we haven’t tested it. To give a sense for how accurate the approximation is here is a plot of it along with the accurate inverse square root:
This is for values between 1 and 100. It’s pretty spot on right? And it should be – it’s not just magic, as the derivation above shows, it’s a computation that just happens to use the somewhat exotic but completely welldefined and meaningful operation of bitcasting between float and integer.
But wait there’s more!
Looking at the derivation of this operation tells you something more than just the value of the constant though. You will notice that the derivation hardly depends on the concrete value of any of the terms – they’re just constants that get shuffled around. This means that if we change them the derivation still holds.
First off, the calculation doesn’t care what L and B are. They’re given by the floatingpoint representation. This means that we can do the same trick for 64 and 128bit floatingpoint numbers if we want, all we have to do is recalculate the constant which it the only part that depends on them.
Secondly it doesn’t care which value we pick for σ. The σ that minimizes the difference between the logarithm and x+σ may not, and indeed does not, give the most accurate approximation. That’s a combination of floatingpoint rounding and because of the Newton step. Picking σ is an interesting subject in itself and is covered by McEniry and Lomont.
Finally, it doesn’t depend on 1/2. That is, the exponent here happens to be 1/2 but the derivation works just as well for any other exponent between 1 and 1. If we call the exponent p (because e is taken) and do the same derivation with that instead of 1/2 we get:
Let’s try a few exponents. First off p=0.5, the normal noninverse square root:
or in code form,
i = 0x1fbd1df5 + (i >> 1);
Does this work too? Sure does:
This may be a wellknown method to approximate the square root but a cursory google and wikipedia search didn’t suggest that it was.
It even works with “odd” powers, like the cube root
which corresponds to:
i = (int) (0x2a517d3c + (0.333f * i));
Since this is an odd factor we can’t use shift instead of multiplication. Again the approximation is very close:
At this point you may have noticed that when changing the exponent we’re actually doing something pretty simple: just adjusting the constant by a linear factor and changing the factor that is multiplied onto the integer representation of the input. These are not expensive operations so it’s feasible to do them at runtime rather than precompute them. If we premultiply just the two other factors:
we can calculate the value without knowing the exponent in advance:
i = (1  p) * 0x3f7a3bea + (p * i);
If you shuffle the terms around a bit you can even save one of multiplications:
i = 0x3f7a3bea + p * (i  0x3f7a3bea);
This gives you the “magic” part of fast exponentiation for any exponent between 1 and 1; the one piece we now need to get a fast exponentiation function that works for all exponents and is as accurate as the original inverse square root function is to generalize the Newton approximation step. I haven’t looked into that so that’s for another blog post (most likely for someone other than me).
The expression above contains a new “magical” constant, 0x3f7a3bea
. But even if it’s in some sense “more magical” than the original constant, since that can be derived from it, it depends on an arbitrary choice of σ so it’s not universal in any way. I’ll call it C_{σ} and we’ll take a closer look at it in a second.
But first, one sanity check we can try with this formula is when p=0. For a p of zero the result should always be 1 since x^{0} is 1 independent of x. And indeed the second term falls away because it is multiplied by 0 and so we get simply:
i = 0x3f7a3bea;
Which is indeed constant – and interpreted as a floatingpoint value it’s 0.977477 also known as “almost 1″ so the sanity check checks out. That tells us something else too: C_{σ} actually has a meaningful value when cast to a float. It’s 1; or very close to it.
That’s interesting. Let’s take a closer look. The integer representation of C_{σ} is
This is almost but not quite the shape of a floatingpoint number, the only problem is that we’re subtracting rather than adding the second term. That’s easy to fix though:
Now it looks exactly like the integer representation of a floatingpoint number. To see which we’ll first determine the exponent and mantissa and then calculate the value, c_{σ}. This is the exponent:
and this is the mantissa:
So the floatingpoint value of the constant is (drumroll):
And indeed if you divide our original σ from earlier, 0.0450465, by 2 you get 0.02252325; subtract it from 1 you get 0.97747675 or our friend “almost 1″ from a moment ago. That gives us a second way to view C_{σ}, as the integer representation of a floatingpoint number, and to calculate it in code:
float sigma = 0.0450465; float c_sigma = 1  (0.5f * sigma); int C_sigma = *(*int)&c_sigma;
Note that for a fixed σ these are all constants and the compiler should be able to optimize this whole computation away. The result is 0x3f7a3beb
– not exactly 0x3f7a3bea
from before but just one bit away (the least significant one) which is to be expected for computations that involve floatingpoint numbers. Getting to the original constant, the title of this post, is a matter of multiplying the result by 1.5.
With that we’ve gotten close enough to the bottom to satisfy at least me that there is nothing magical going on here. For me the main lesson from this exercise is that bitcasting between integers and floats is not just a meaningless operation, it’s an exotic but very cheap numeric operation that can be useful in computations. And I expect there’s more uses of it out there waiting to be discovered.
(Update: I’ve added an appendix about the intuition behind the part where I shuffle around the floatingpoint terms and the integer terms appear.)