Sunday, January 27, 2008

Really big numbers. And I mean, REALLY big.

onsider a favorite song of mine, Built To Spill’s “Randy Describe Eternity”:

Built to SpillRandy Described Eternity

The song asks you to imagine a very large number by means of an analogy. The full lyrics go like this:

every thousand years

this metal sphere

ten times the size of Jupiter

floats just a few yards past the earth

you climb on your roof

and take a swipe at it

with a single feather

hit it once every thousand years

`til you’ve worn it down

to the size of a pea

yeah I’d say that’s a long time

but it’s only half a blink

in the place you’re gonna be

where you gonna be

where will you spend eternity

I’m gonna be perfect from now on

I’m gonna be perfect starting now

stop making that sound

stop making that sound

I will say I forgot

but it was only yesterday

and it’s all you had to say

Despite the technical difficulties of having a metal sphere that large pass that close to the Earth, it’s a cool metaphor. So how long of a time are we talking about here? Let’s come up with an estimate.

First consider how much a swipe of a feather would remove from the sphere. Let’s take a guess and say that 100 swipes would remove a square millimeter. (That’s being conservative, I think; could you really complete dissolve a grain of sand by brushing it a hundred times with a feather?)

Now consider the size of the sphere, “ten times the size of Jupiter”. Let’s assume they mean ten times the volume, which would be 10 × 1.43128 × 1015 km³, or 1.43128×1016 km³, which in cubic millimeters is 1.43128 × 1034 mm³. The “size of a pea” amount left over is incidental.

So if we just multiple that figure by 100 (feather swipes) times 1000 years, and we get 1.43128 × 1039 years. Let’s call this Randy’s number. Is it older than the current age of the universe? Yes, by a long shot. The universe is only about 1.37 × 1010 years; Randy’s number is 100 000 000 000 000 000 000 000 000 000 times larger. Yeah, I’d say that’s a long time.

Clifford Pickover’s Mazes For The Mind mentions a few other large (estimated) numbers:

  • The talking number — the total number of words spoken by humans since the dawn of history: 1016

  • The Coney Island number — the total number of grains of sand on the beach at Coney Island: 1020

  • The ice age number — the total number of ice crystals necessary to form the ice age: 1030

Douglas Hoftstadter in Metamagical Themas mentions a few others:

  • The Hemoglobin number — the number of hemoglobin molecules in the human body: 6 x 1021

  • Rubik’s constant — the number of possible configurations of a Rubik’s cube: 4.3 x 1019

Huge numbers, to be sure. Larger still is the infamous googol, which is 10100. Now consider the googolplex, which is 10googol. It is said that such a number could never be written down, as it would require more space than is available in the known universe.

But even these numbers are peanuts compared to some other numbers which have been envisioned. Consider tetration, Knuth’s up-arrow notation, Steinhaus-Moser notation, or Conway’s chained arrow notation.

Finally, just to fry your brain a little more, consider a number proposed in the excellent web comic XKCD, in his strip What XKCD Means”:

The Ackermann function with Graham’s number as its arguments is a number orders of magnitude larger than we can imagine. Actually, you can hardly say it’s “orders of magnitude” larger since that only implies exponentially larger; this number goes way, way, way beyond that!

But it’s still finite. And if you divide it by infinity, you still get zero. That kills me.

Quick and Dirty 3-D Rendering

By using a handy shortcut, you can render 3D objects painlessly.

Usually this is done using transformation matrices. This sort of matrix manipulation was actually discovered back in the 18th century, but like many great mathematical discoveries, had no real practical application. Until the modern era, that is, when someone discovered that this trick was perfect for rendering 3D graphics. It lets you rotate, scale, shear, etc. any image, and the really nice thing is that once you decide all the transformations you want, you can reduce them to a single matrix and so compute the positions of everything you want to draw rather quickly.

But unless you live and breathe the stuff, it’s too complicated to remember how to set it up off the top of your head, and a lot of code even if you know how. So here’s a tip that will get you rendering 3D objects in no time.

First, draw yourself a set of axises, like so:

It doesn’t have to be very accurate, just so as it looks fairly proportional. Now, imagine that each of the arrows is one unit long. You need to write functions that return x and y for a given (x,y,z) point. So ask yourself — for each unit of x, how much do we actually move horizontally? How about for each unit of y? For each unit of z, we don’t move horizontally at all, but for the other two, you can make a guess. Let’s say the tip of the x axis is 16 pixels to the right of the origin, and the tip of the y is 20. Again, accuracy isn’t important, as long as you’re in the ballpark and the numbers are proportional. Since you want it to appear in the center, add an offset that’s half the width of the screen. So your method for determining the screen x coordinate of your point will look something like this:

private int getX( Point p )
return CENTER_X + p.x*16 + p.y*20 + p.z*0;

Obviously, the p.z*0 could have been left out, but I leave it there for illustration.

Similarly, the screen y coordinate can be determined just by guessing the offset of the tips of the x, y, and z axises on our sketch. Looks like about -10, 5, and -20 respectively (remember y coordinates count down from the top in most computer graphics systems). So our function for determining the screen y of your point will look like this:

private int getY( Point p )
return CENTER_Y + p.x*-10 + p.y*5 + p.z*-20;

Let’s see it in action. Here’s an applet that defines a few lines in terms of their 3D endpoints, and then draws them on our 2D screen using the methods described above. Specifically, it defines all the lines necessary to draw the cube that stretches from -1 to 1 on each axis. Give it a click to run it:

Enable Java in your browser to see it.

(Java source for main class here. Parent applet here.)

Not bad, huh? It’s handy for quick visualizations, and you’ll probably see it again here before long.

Towers of Hanoi

Any discussion of beauty in programming must necessarily begin with recursion in general, and the Towers of Hanoi in particular. This will be review for anyone who’s studied computer science, but that’s okay since I won’t have many readers at this point anyway.

The Towers of Hanoi is a puzzle of simple construction but fascinating complexity. It consists of three pegs. To start with, on one of the pegs is a number of disks, stacked from largest to smallest. The object is to move the stack of disks to one of the other pegs, with the restrictions that you can only move one disk at a time, and a disk may never be placed on a disk that’s smaller than it.

There’s a beautiful computer algorithm to solve it, and that I want to talk about. But the Towers of Hanoi was a toy long before there were computers. So first, have a play at solving it by yourself. Increase the number of disks if you find it too easy to start with. Most people, when they first start playing with it, end up moving disks pretty much randomly at the start. After a point you may find yourself making small goals, like “Okay, I need to get these smallest three disks over to this peg, so I can move the next biggest disk…” Eventually you realize that, if you’re starting with, say, six disks, you’re going to have to move five of them out of the way (onto the extra peg), then move the sixth and largest disk to the target peg, then move the first five on top of it.

So let’s look at the actual program that solves it. The number of disks has been made a parameter so we can eventually solve it for any number of disks. I’ll add comments to make it exceedingly clear what’s going on.

private static void hanoi( int numberOfPegs, String fromPeg,
String targetPeg, String otherPeg )
// First, move all but the largest disk to the extra peg.
if (numberOfPegs > 1)
hanoi( /* move */ numberOfPegs-1, /* pegs */
/* from the */ fromPeg,
/* to the */ otherPeg,
/* via the */ targetPeg);

// Next, move the largest disk to the target page. We'll just print
// out the move we're making.
System.out.println("Move a disk from " + fromPeg + " to " + targetPeg);

// Lastly, move the disks that we moved out of the way on top of
// the largest disk.
if (numberOfPegs > 1)
hanoi( /* move */ numberOfPegs-1, /* pegs */
/* from the */ otherPeg,
/* to the */ targetPeg,
/* via the */ fromPeg);

We’ve had to add the extra peg as the last parameter, just to keep track of it. But notice how similar it is to the original plan, of moving all but the largest disk out of the way, then moving the largest disk, then moving all the remaining disks on top of it. But as an algorithm it looks like it only sketches the broad plan. It just doesn’t look complex enough to solve that first step — moving all but the largest disk out of the way — not to mention he third step, which is just as complex. But miraculously, it works! Try running the code yourself. How could it possibly do all those intermediate steps?

It turns out that the problem of how to move n-1 disks from the “from” peg to the “other” peg is just a smaller, simpler version of the problem of moving n disks from the “from” peg to the “target” peg. It’s just that we’re now using the “extra” peg as our target peg, and the target peg as the extra peg. So this method will just be solving the problem for smaller and smaller versions of the problem, until eventually it has to solve it for only a single disk. And if you trace the code for what happens when there’s a single disk (when numberOfPegs==1), you’ll see that all it will do is the print statement.

To me, the Towers of Hanoi problem is the most beautiful algorithm there is. And it fits the requirements for a recursive algorithm perfectly; it can be broken up into smaller problems, until it reaches an exceedingly simple case (just moving a single disk).

I wonder how long it took after the first computers were made until the Towers of Hanoi was successfully programmed. Very probably it was done in machine code, using a stack of some sort. But what was the first language that would have allowed it to be done with a nice readable recursive function? I would love to have been a fly on the wall.

There’s lots more to the Towers of Hanoi, which I will cover in a later post.

Hello, world!

Hello, World! And welcome to Computronium.

In this forum I’ll be talking about things that thrill my brain. Mostly, as the name implies, it’ll be about computing, especially the recreational variety, but I’ll be taking brief interludes into math, physics, astronomy, or whatever else strikes my fancy. I’ll be focusing on the bits that are just fun, or interesting, or beautiful to me. Hopefully they will be to you too.

I have met a number of people in my life who enjoy computer programming for its own sake. But there’s also people who think that anything created on a computer is inherently soulless, and that any art created on a computer is cold and robotic. I couldn’t disagree more. Art created on a computer is as human as the person who makes it. But the logic underneath too is beautiful in and of itself.

Though I’ll be presenting things that give me “intellectual” thrills, my goal will always be to simplify, and to explain clearly, without dressing things up in fancy language. I’ll be writing about what I know but also about what I don’t — things I’m curious about. So I’m counting on input from you all. Not everything I’ll be writing about will be deeply profound — some of the topics I’m pondering will require just a few sentences. But even in dusting off these old ideas that I’ve pondered before, I’ve come up with new ways of looking at them, as well as some completely new ideas. I’m sure, with the participation in this forum that I’m hoping for, there’ll be lots and lots of other things that come up.

So, the main topic: computing. Computers themselves are ghastly, I believe, BUT, they’re the only things that let you compute. We’ll not be arguing here the merits of Java versus C++, or talk much about the flavor du jour of software processes. I have preferences in these matters, of course, but the underlying algorithms are what really interest me. Some languages do indeed encourage you to look at problems in interesting ways, but for much of what I’ll be talking about, the choice of programming language is pretty much moot. And as far as process — while I’m totally convinced of the necessity of good software practices, I don’t find a lot of joy in talking about it.