I've recently been reading through Knuth's new "Art of Computer Programming" fascicle on bitwise tricks, and thoroughly enjoying myself. Especially in trying to hunt down information on the many side topics which Knuth alludes to in the text. For instance, the fact that really the only bitwise operator that had any historical interest to mathematicians was XOR; also known as the "nim sum", because of it's ability to give a winning solution to the game of nim. Nim is great, and I highly recommend the Wikipedia article about it, but in this post I'm going to talk about something else, related to something Knuth says about our understanding of the power of bitwise operations to generate complexity.
"A famous chain of operations known as 'Gosper's hack,' first published in 1972, opened people's eyes to the fact that a large number of useful nontrivial functions can be computed rapidly."
I've heard of Bill Gosper a few times before, mostly because he is responsible for writing the majority of the short articles that make up the body of work known as HAKMEM. A collection of hacks, tricks, and mathematical curiosities discovered by folks at MIT in late 60s/early 70s. I also have it on pretty good authority that many in that time and place jocularly referred to Gosper as the best 19th century mathematician living today. Most of the examples published in HAKMEM were coded in PDP10 assembly, but I can read a little of that so I set out to find the original source on the subject, Gosper's Display Hack, aka HAKMEM item 145.
Item 145 is one of the shorter items in HAKMEM so I will produce it here in it's entirety. Though the article in the context of other hacks can be found here.
0/ TLCA 1,1(1) 1/ see below 2/ ROT 1,9 3/ JRST 0This is a display hack (that is, it makes pretty patterns) with the low 9 bits = Y and the 9 next higher = X; also, it makes interesting, related noises with a stereo amplifier hooked to the X and Y signals. Recommended variations include:
CHANGE: GOOD INITIAL CONTENTS OF 1:
none 377767,,377767; 757777,,757757; etc.
TLC 1,2(1) 373777,,0; 300000,,0
TLC 1,3(1) -2,,-2; -5,,-1; -6,,-1
ROT 1,1 7,,7; A0000B,,A0000B
ROTC 1,11 ;Can't use TLCA over data.
AOJA 1,0
Okay, this is about as simple as you can get. One key thing you need to be aware of is the PDP10 is a 36-bit architecture. That is, registers and words are 36-bits long. So when he's talking about using The rightmost pair of 9-bits as x and y coordinates for display he's talking about quarter words. So, if we attempt to do this on a standard architecture without any emulation it makes sense to use 8-bits of the word to represent our coordinates. This also means that our screen will be 256x256 instead of 512x512 as in the original hack, but this is actually a pretty good size for a little processing app.
With that in mind lets break down what each line does:
0/ TLCA 1,1(1) 1/ see belowThe TLCA pneumonic stands for Test Left Compliment and Always skip, which takes the immediate value on the right side of the comma, and bitwise-XORs it with the left-half of accumulator 1, storing the result in AC1. Note that the program itself is written in the accumlators 0-3. There's no rule against this on the 10. Thus, accumulator 1 is actually one of the lines of the program which this instruction is always skipping over as it manipulates it. The immediate value of this instruction is actually the contents of the right half of accumulator 1 incremented by one, because we are using 1 as an index register to do the calculation. Fun stuff! The instruction can be reduced to something semantically similar, but written in a C-style for converstion to the Processing Language:
int i = INITIAL_VALUE; // Different values make different pictures i = i ^ ((i + 1) << 16);The "see below" from Gosper's code is what I've called INITIAL_VALUE. Okay that's a start. What about?
2/ ROT 1,9 3/ JRST 0Well, that ROT instruction just rotates accumulator 1 9 bits to the left (we'll rotate by 8), and JRST is just the prefered jump instruction causing us to do all this in a loop. So putting all 4 PDP10 assembly instructions together and turning them into something C-like again we get:
loop: int i = INITIAL_VALUE; // Different values make differnet pictures i = i ^ ((i + 1) << 16); i = (i<<8) | (i>>>(32-8)); // Sadly this is how we must rotate point(i&0xff, (i>>8)&0xff); // We want to plot this on the screen! goto loop;
That's it. This is basically the inner loop of our processing app. In reality since the draw() function is polled by the processing environment we dont need the loop explicitely we just put the code in the draw function. You can do a view source on this page to see the whole thing, there's a lot more there but most of it is to allow for the slide bar controls which reset the initial conditions of the loop.
As Gosper originally noted a great deal of complexity is generated from such a simple program. It's very reminiscent of 1-d cellular atomata. Since the PDP10 is a 36-bit machine the recommended initial conditions above don't map directly to the 32-bit case, so experiment with the scrollbars to control the initial values for the left and right half of our initial 32-bit word. The simplest interesting case I've found is 0 0 (Drag both sliders all the way to the left). That one creates some patterns reminiscent of rule 90, and if you let it run long enough it takes on some interesting fractal like properties. A friend of mine, @hallsa also noticed that 7fff 4797 makes some interesting patterns with totally different characteristics. The slider bars may not be as fine grained as one might like, so I may add some keyboard input controls to allow for tweaking of the initial conditions by increments as fine as 1. Have fun!