math, science

Life in Hyperbolic Space 1: Primer

It’s rare that weird, brain-bending ideas and video games meet, but in my experience, when they do, it’s pretty glorious. Portal, Prey, Antichamber, The Stanley Parable, and SUPERHOT are examples I’ve played personally. Also Miegakure (if it ever comes out, grumble grumble) will probably land instantly in that category, being a 4D puzzle game. But my most recent weird-game obsession has been HyperRogue. HyperRogue is awesome. Like Dwarf Fortress, it’s got a bit of a retro look with clean, minimalist graphics. And like Dwarf Fortress, it’s pretty obvious that a lot of love has gone into it. Here’s what the game looks like:

HyperRogue.png

Like many roguelikes (modeled after the ancient ASCII game Rogue), it’s played on a sort of chessboard. It looks at first glance like one of those board wargame or D&D-type hexagonal chessboards, but instead of being just hexagons, it’s got heptagons (7-sided polygons) too. You know what? That reminds me of the description of another geometric object:

Truncated Icosahedron

(Screenshot from the awesome polyhedron program polyHédronisme)

That is a truncated icosahedron, but I’d wager that most people know it better as either A) a soccer ball/football, or B) a molecule of C60: a fullerene, a buckyball.

Don’t worry. It’ll be clear in a moment what the hell I’m going on about. You see, HyperRogue takes place in the hyperbolic plane. A flat piece of paper is a Euclidean plane. The surface of a globe (or the Earth, or a buckyball) is a sphere. The hyperbolic plane is the third brother in the trio, so to speak, and it’s the weird brother. Their relationship makes more sense to me if I think in terms of polygons. Here’s another picture:

1000px-hexagonal_tiling-svg

(From the Wikimedia commons.)

The Euclidean plane (the hexagonal tiling above) consists of hexagons, each of which is bordered by six hexagons. The buckyball (football/soccer ball) farther above, representing spherical geometry, consists of pentagons, each of which is bordered by five hexagons. And at the very top of the page, the world of HyperRogue, representing the hyperbolic plane, consists of heptagons (7-sided polygons), each of which is bordered by seven hexagons. The hyperbolic plane is what would happen if you tried to sew up a soccer ball using heptagonal and hexagonal pieces of leather, rather than the usual pentagonal and hexagonal ones. Here’s what that looks like:

convoluted

(From the page of Frank Sotille, who has awesome templates so you can make your own hyperbolic football. I would’ve done it myself, but all of my Scotch tape has vanished.)

The only buckyball-type tiling that lays flat is the one with hexagons surrounded by hexagons. Pentagons surrounded by hexagons curves into a sphere, and heptagons surrounded by hexagons curls up into what HyperRogue’s creator calls a hypersian rug.

But here’s a more intuitive (though less precise) way to understand the hyperbolic plane. Consider the flat Euclidean plane. Pick a point. Draw a circle centered on that point. Measure the circumference of that circle. Draw another circle with the same center, but twice the radius. Measure the circumference of that circle. The farther you get from your starting point, the larger the circumference, but the increase is very predictable and linear. As a matter of fact, the circumference (the “amount of space”) you cover as you increase the radius of your circle increases exactly like this:

save (1)(1)

(Graphed with FooPlot.com)

Now do the same thing on a sphere: centered on the north pole, draw a very small circle with a given radius (with the radius measured across the curved surface of the sphere, not straight from point to point). Draw another circle with twice the radius. Up until you hit the equator, the circumference will increase, but eventually it maxes out and goes back down:

save (3)

(Circumference in the Euclidean plane in black, circumference on the sphere in red)

There’s another important effect to consider here: the sphere’s radius matters. That plot assumed a sphere of radius 1. Here’s what it would look like with a sphere of radius 2:

save (2)

It doesn’t make much sense to ask for the “scale” or “radius” of the Euclidean plane, because the answer is “infinity.” Any Euclidean plane is indistinguishable from any other, no matter how you swell or shrink it. Spheres, though, are distinguished by their radii: each has an inherent positive curvature.

Of course, on a sphere, the largest circle you can draw has a radius (measured across the surface of the sphere) of ½πR. the circumference of that circle lies right on the sphere’s equator. After that, the circumference decreases as the radius increases, because your circle’s shrinking as it approaches the opposite pole. It reaches zero when the radius is πR, and your radius-line stretches from one pole to the other.

The Euclidean plane has zero curvature. The sphere has positive curvature. The hyperbolic plane has negative curvature. The “radius” of a hyperbolic plane is defined as 1 / sqrt(-K), where K is a measurement called “Gaussian curvature.” (For comparison, the Gaussian curvature of a sphere is 1/(R²) ). K is the thing that’s zero for the plane, positive for the sphere, and negative for the hyperbolic plane. For a hyperbolic plane of K = -1, with a “radius” of 1, the circumference increases like this:

save (1)

(Hyperbolic circumference is the green line. The red line for a sphere with R = 1 (K=1) is included for comparison.)

That’s the weird thing about hyperbolic geometry: a sphere of infinite radius behaves exactly like the Euclidean plane (it is the Euclidean plane). But as the radius shrinks, the sphere contains less and less space (so to speak). To put it another way: if you were knitting a Euclidean plane (which people do, because mathematical knitting is a thing, which is awesome), then you’d need to knit in twice as much thread at radius 2 than you’d needed at radius 1. To knit a sphere, you’d need to knit less than twice as much thread in at twice the radius. And to knit a hyperbolic plane, you’d need to knit in more than twice as much yarn at twice the radius (according to the formula 2 * pi * R * sinh(r/R), where R = 1/sqrt(-K), and r is the radius measured through the plane; the equivalent relation for the sphere is 2 * pi * R * sin(r/R)). Where the Euclidean knit would give you a flat circular rug, and the spherical knit would give you a hacky-sack ball, the hyperbolic knit would give you something like this:

crochet_02

(Knitted by Daina Taimina, exhibited on the website of the Institute for Figuring.)

But the weird thing is that you can still do almost exactly the same geometry on the hyperbolic plane that you can do in the Euclidean plane. In fact, that’s why hyperbolic geometry is interesting: apart from a couple of weird quirks, it behaves just like a plane. That means you can make rigorous, valid, geometric proofs in the hyperbolic plane.

The Euclidean plane gets its name from Euclid of Alexandria, who is responsible for the infinite misery of people (like me) who just couldn’t get along with high-school geometry. But he condensed many centuries of Greek (and other) geometry into a set of postulates (axioms) from which you can prove pretty much anything that’s true in geometry. Here they are:

  1. You can draw a straight line between any two points.
  2. You can extend an existing straight line as far as you like.
  3. Using a compass, you can draw a circle with any center and any radius you want.
  4. All right angles are the same.
  5. If you’ve got two lines running alongside each other and another line running through both of those, and the angles on the insides of the intersections add up to less than a right angle, then the lines will intersect if you extend them far enough, and they’ll intersect on the side where the angle-sum is less than two right angles.

That last one, called the parallel postulate was a thorn in geometry’s side for a long time, because it seems a lot less elegant than the others, and it seems like the kind of thing you might be able to prove from the other axioms, which would mean it’s not an axiom, since axioms are your starting rules and theorems are what you prove using them. A less messy way to write the parallel postulate is:

5. Given any straight line, and given a point which doesn’t lie on that line, there is exactly one straight line through that point which never intersects the first line (the second line being the parallel).

Spherical geometry and hyperbolic geometry are both based on changing the parallel postulate. In spherical geometry, it becomes:

5. Given any straight line, and given a point which doesn’t lie on that line, there are zero straight lines through that point which never intersect the first line.

Or, to put it in simpler terms: because you’re on a sphere, lines that should be parallel (that is, lines which form a total of two right angles when intersected by a third line), inevitably intersect. Think of the north and south poles as two points. Draw the prime meridian from North to South. Now draw another line passing through the equator at 1° East longitude, 0 ° North latitude. At that point, the two lines are as parallel as lines get: they form ninety-degree intersections with the equator, and therefore, the interior angles on either side form exactly two right angles. But keep drawing those lines, and they’re going to intersect at the south pole, even though they should, according to Euclidean intuition, have stayed parallel.

In hyperbolic geometry, the parallel postulate is modified to the other extreme:

5. Given any straight line L, and given a point P which doesn’t lie on that line, there are an infinite number of straight lines through P which do not intersect L.

Poincare Parallels

That’s the Poincaré disk model, which fits the infinite hyperbolic plane into a finite circle. It’s elegant and simple, and it’s the model HyperRogue uses, so I’m going to stick with it. The red lines are the boundaries of the infinite set of lines which pass through P but never intersect L. It looks like the red lines intersect L at one end each, but the Poincaré disk model distorts distances more and more the closer you get to the edge. A picture’s worth a thousand words, so here’s a series of circles of equal radius starting from the center of the disk and moving outward:

CircleChain

(Both images rendered with the awesome (and free) geometry software GeoGebra)

I know they don’t look like circles of equal radius, but that’s just an artifact of the projection. The same way a Mercator map distorts Greenland so that it looks like it’s bigger than North America (when in reality it’s not much bigger than Quebec or Mexico), the Poincaré disk model distorts distances the closer you get to the edge of the circle. As a matter of fact, that bounding circle, as measured within the hyperbolic plane, is infinitely far from the center. You can’t ever reach it: it’s infinitely far from everywhere. So those intersections that seem to exist in the picture with the red and blue lines, they don’t actually exist, because you’d have to go infinitely far to get there. And keep in mind that, from any given point, it feels like you’re at the center of a Poincaré disk, so those lines don’t actually get closer to the line L the way the projection makes it seem. The projection is a necessary evil. You can do spherical geometry on an ordinary globe and remove all distortion, but you saw how messy and rumpled the hyperbolic version of a globe became: just look at the red crochet thing above. That’s not gonna happen. You have to live with the distortion.

The cool thing about the Poincaré disk model, though, is that it preserves angles, which makes it easy to do the kind of straightedge-and-compass geometry that’s so handy for geometric proofs.

And guess what? Just like we experience the world an almost-flat Euclidean space (relativity says it’s not perfectly flat, but it’s very close in our neighborhood, which I have to say to stop the nitpickers from yelling at me), there are three-dimensional spaces with spherical curvature, and there are three-dimensional spaces with hyperbolic curvature. In the next part, I’m going to talk about life in a highly-curved hyperbolic space. But before I go, let me leave you with a picture of something. In the Euclidean plane, you can only pack six equilateral triangles (all angles and edge-lengths the same) around a single point. The result looks like this:

1-uniform_n11.svg.png

(Source.)

In the hyperbolic plane, though, you can fit seven equilateral triangles around a vertex, and it looks like this (and don’t forget, those triangle are just as perfect and equilateral as the ones above; it just doesn’t look like it, because of the projection):

1024px-H2_tiling_237-4.png

(Source.)

You can actually fit eight triangles around a vertex too, although the triangles have to be larger (largeness being a slightly complicated concept in hyperbolic geometry, but we’ll get to that next time):

1024px-H2_tiling_238-4.png

(Source.)

And actually, it’s perfectly allowable to fit an infinite number of equilateral triangles around every vertex. That looks like this:

H2_tiling_23i-4.png

(Source.)

And remember, those triangles are still perfect and equilateral and regular. Hyperbolic space is weird. Remember that thing Christopher Lloyd said in Back to the Future? Get ready: we’re gonna see some serious shit.

Standard
biology, Dragons, physics, thought experiment

Dragon Metabolism

As you might have noticed, I have a minor obsession with dragons. I blame Sean Connery. And, because I can never leave anything alone, I got to wondering about the practical details of a dragon’s life. I’ve already talked about breathing fire. I’m not so sure about flight, but hell, airplanes fly, so it might be possible.

But I’ll worry about dragon flight later. Right now, I’m worried about metabolism. Just how many Calories would a dragon need to stay alive? And is there any reasonable way it could get that many?

Well, there’s more than one type of dragon. There are dragons small enough to perch on your shoulder (way cooler than a parrot), and there are dragons the size of horses, and there are dragons the size of cathedrals (Smaug again), and there are, apparently, dragons in Tolkein’s universe that stand taller than the tallest mountains. Here’s a really well-done size reference, from the blog of writer N.R. Eccles-Smith:

dragon-size-full-chart

The only downside is that there’s no numerical scale. There is, however, a human. And, if you know my thought experiments, you know that, no matter what age, sex, or race, human beings are always exactly 2 meters tall. Therefore, the dragons I’ll be considering range in size from 0.001 meters (a hypothetical milli-dragon), 1 meter (Spyro, number 3, purple in the image) to 40 meters (Smaug, number 11), and then beyond that to 1,000 meters, and then beyond to the absolutely ludicrous.

Continue reading

Standard
Cars, physics, thought experiment

Supersonic Toyota? (Cars, Part 2)

A while ago, I wrote a post that examined, in much greater and (slightly) more accurate detail what speeds my 2007 Toyota Yaris, with its stock drivetrain, could manage under different conditions. This post is all about Earth at sea level, which has gotta be the most boring place for a space enthusiast. Earth at sea level is what rockets are built to get away from, right? But I can make things interesting again by getting rid of the whole “sensible stock drivetrain” thing.

But first, since it’s been quite a while, a refresher: My Yaris looks like this:

2007_toyota_yaris_9100

Its stock four-cylinder engine produces about 100 horsepower and about 100 foot-pounds of torque. My drivetrain has the following gear ratios: 1st: 2.874, 2nd: 1.552, 3rd: 1.000, 4th: 0.700, torque converter: 1.950, differential: 4.237. The drag coefficient is 0.29 and the cross-sectional area is 1.96 square meters. The wheel radius is 14 inches. I’m totally writing all this down for your information, and not so I can be lazy and not have to refer back to the previous post to get the numbers later.

Anyway…let’s start dropping different engines into my car. In some cases, I’m going to leave the drivetrain the same. In other cases, either out of curiosity or for practical reasons (a rarity around here), I’ll consider a different drivetrain. As you guys know by now, if I’m gonna do something, I’m gonna overdo it. But for a change, I’m going to shoot low to start with. I’m going to consider a motor that’s actually less powerful than my actual one.

An Electric Go-Kart Motor

There are people out there who do really high-quality gas-to-electric conversions. I don’t remember where I saw it, but there was one blog-type site that actually detailed converting a similar Toyota to mine to electric power. That conversion involved a large number of batteries and a lot of careful engineering. Me? I’m just slapping this random go-kart motor into it and sticking a couple car batteries in the trunk.

The motor in question produces up to 4 newton-meters (2.95 foot-pounds). That’s not a lot. That’s equivalent to resting the lightest dumbbell they sell at Walmart on the end of a ruler. That is to say, if you glued one end of a ruler to the shaft of this motor and the other end to a table, the motor might not be able to break the ruler.

But I’m feeling optimistic, so let’s do the math anyway. In 4th gear (which gives maximum wheel speed), that 4 newton-meters of torque becomes 4 * 1.950 * 4.237 * 0.700 = 21 Newton-meters. Divide that by the 14-inch radius of my wheels, and the force applied at maximum wheel-speed is 59.060 Newtons. Plug that into the reverse drag equation from the previous post, and you get 12.76 m/s (28.55 mph, 45.95 km/h). That’s actually not too shabby, considering my car probably weighs a good ten times as much as a go-kart and has at least twice the cross-sectional area.

For the electrically-inclined, if I was using ordinary 12 volt batteries, I’d need to assemble them in series strings of 5, to meet the 48 volts required by the motor and overcome losses and varying battery voltages. One of these strings could supply the necessary current of 36 amps to drive the motor at maximum speed and maximum torque. Ordinary car batteries would provide between one and two hours’ drive-time per 5-battery string. That’s actually not too bad. I couldn’t ever take my go-kart Yaris on the highway, but as a runabout, it might work.

Continue reading

Standard
Uncategorized

Approaching Infinity

One of the cool (and terrifying) things about math is that it’s almost a trivial task to construct a number which is not only larger than any number a human being will ever be able to use, but is also larger than any number that occurs in the Universe, even if you measure its mass in electron masses or its volume in Planck volumes.

The average human’s mathematical circuits are not that hard to overload. If I give you a deck of one hundred photographs and give you one hour to memorize all of them, you might very well be able to do it, but odds are you’ll miss some details. If I ask you to remember a 500-digit number, unless you’re a savant (like Daniel Tammet, who once recited pi to over 22,000 digits from memory, and who allegedly has a distinct mental image for every integer from 1 to 10,000), you’ll need some sort of fancy technique to do it. When it comes to counting objects, human beings don’t need very many numbers. I am one person. You (the reader), and I are two people having a sort of conversation. When I’m talking to a friend and somebody annoying butts in, that’s three people. If I have three apples, and I can ford a river to get to a tree with four apples, at the cost of dropping the ones I already have, I’ll do it. Numbers like three, five, and seven show up in most of the world’s myths and superstitions. Occasionally, you’ll get to seven or nine or even eleven, but rarely much farther than that. On a basic hunter-gatherer level, one hundred is a bit excessive. It’s only science, mathematics, and economy that have made a hundred of anything meaningful.

Take the number one trillion. That’s 10^12, or 1,000,000,000,000. (According to the American number scale, anyway.) It’s a big number. Draw a square. Divide it with ten vertical and ten horizontal lines. Divide each of those boxes with ten pairs of lines. Do this eight more times, and you’ve got a trillion squares. I should, of course, point out that, if you’re working on regular letter-size paper, by the time you get to a trillion boxes, the lines will be so close together that a virus will take up more than one square. Even if you drew your grid in the heart of Asia, where there’s a nice big squarish landmass 3,780 kilometers on an edge (stretching from the coast of China to the Caspian Sea along the east-west axis and from Siberia to the Himalayas on the north-south axis), the squares would be the size of a small closet.

But I already talked about a trillion at length in a previous post. A trillion green peas would just about fit on a football field (for most reasonable definitions of “football”). It’s a lot, but it’s a sensible, comprehensible number.

And a trillion is the largest number you’ll see mentioned frequently in serious astronomy, although there’s also the pleasant-sounding number “ten sextillion.” It sounds like something Lewis Carroll would’ve come up with. Ten sextillion is 10,000,000,000,000,000,000,000. That’s how many stars there are in the visible universe, according to Carl Sagan’s estimation. If you took the heart of Asia from before and divided it into ten sextillion squares, the lines would be separated by less than a hair’s breadth: about 30 microns. Cramped lodgings even for an amoeba.

But with nothing but digits and a few symbols, we can effortlessly construct numbers so massive that there’s no sensible way to describe how massive they are. Consider one trillion again. One trillion is 10^12. That’s the number 10 to the 12th power: 10 multiplied by itself 12 times. Here’s a number that will hurt your head: 10^(10^12). Simple: just take 10, and multiply it by itself one trillion times. I thought I’d be able to actually copy-and-paste that number, but it turns out that, in a 12-point font, I’d need almost 218 million pages (printed both sides). That’s a whole library’s worth of dictionary-sized books, just to hold the digits of a number I described using ten characters a second ago. If you divided the diameter of the observable universe into 10^(10^12) pieces, the distance between them would be 999,999,999,938 orders of magnitude smaller than the Planck length, which is just about the smallest length that makes sense, according to our current physics.

It’s easy as pie to create a scarier number. I’ll do it right now! (10^12)^(10^12). That is, (1,000,000,000,000)^(1,000,000,000,000). Multiply a trillion by itself a trillion times. This is where things not only get horrifying and migraine-inducing, but where they start to get strange: (10^12)^(10^12) isn’t really all that much larger than 10^(10^12). A trillion to the trillionth power is only 10^(12,000,000,000,000), or ten to the twelve trillionth power. That’s because of the way exponents work: the twelve in the first exponent gets multiplied by the trillion in the second exponent. Simple.

Don’t worry, though. With hardly any work, we can construct a function which will generate numbers as scary as you like with almost no effort.

Let’s say that the function M[1](a,b) is just a * b. Simple multiplication (which is really just adding a to itself b times, or vice versa). Let’s extend the concept by saying that M[2](a,b) is a^b, or a multiplied by itself b times. There’s no reason we can’t define M[3](a,b). It would just be a nested series of M[2] being applied over and over, exactly b times. For example, M[3](2,8) is 2^(2^(2^(2^(2^(2^(2^2)))))). You know you’ve wandered into the weird part of mathematics when you get a headache just from dealing with the damn parentheses…

There is no way to write M[3](2,8) out. As a matter of fact, there’s no way to write out its number of digits (which, after all, is only ten times smaller than the number itself). Here’s the closest I can get to writing M[3](2,8). Prepare for an absolutely horrific number-salad. I PROMISE this is the only time in this article that I’m going to do this:

[HUGE NUMBER GOES HERE]

If you’re mad at me right now, I understand. But if it makes you feel better, trying to work out that formatting has both given me a headache and made me physically nauseous. And I still screwed it up.

Nope. Couldn’t do it. It was just too damn hard to look at. Suffice to say, most of the article would have been digits, if I’d pasted that ugly bastard in.

But even the M[3](2,8) thing is unwieldy. We need better notation. Thankfully, Donald Knuth (who, at the age of nineteen, created an entire system of measurement based partly on the thickness of Mad magaizne, issue 26) provided a more elegant solution.

(I should, at this point, mention that the enormous number I copy-and-pasted above was so big that it was making the WordPress text editor lag, so I had to copy it into a Notepad file so that I can continue writing. You’ll never see it, but up above, I’ve written “[HUGE NUMBER GOES HERE]”. I have a headache.)

Knuth’s up-arrow notation is just like my M-notation, but it’s (slightly) easier on the eyes. No easier on the brain, though. In Knuth notation, a ^ b is replaced by a↑b, that is, a multiplied by itself b times. For example: 2↑8 is 256.

Things get scary very, very fast. a↑↑b is defined as a↑(a↑(…↑a)), where a is repeated a total of b times, with all the associated symbols. That’s too damn abstract for me, so let’s compute 2↑↑3. That’s 2↑2↑2, or 2^(2^(2)), which is only 16. 2↑↑4 is 2^(2^(2^(2))), or 65,536.

We can go further, though, although my headache is telling me to stop. a↑↑↑b is just a↑↑a↑↑a…↑↑a, with a repeated b times. 3↑↑↑2 is 3↑↑3 or 3^(3^(3)), which is about seven and a half trillion. 3↑↑↑3, on the other hand, is a number so large that I can’t express it in decimal notation. Hell, I can’t even express it using exponentials or up-arrows. It’s equal to 3↑↑3↑↑3, which is equal to 3↑↑(3^(3^3)), which is equal to 3↑3↑…↑3, where there are over seven trillion threes. That means a tower of exponents seven trillion threes tall. My word processor tells me that a superscript is 0.58 times the size of a regular letter, and by the time we get to the 7.6 trillionth three, it’ll be infinitely smaller than a proton.

That’s the level we’re at. Even trying to describe the typography of this ridiculous number is impossible.

What about a↑↑↑↑b? Well, 3↑↑↑↑2 is 3↑↑↑3, which we just saw was the most horrible thing in the world. 3↑↑↑↑3 is 3↑↑↑(3↑↑↑3). That is to say, 3↑↑↑3↑↑↑…↑↑↑3, with 3↑↑↑3 threes.

But I’m not letting you get off that easy. Let’s say that a↑[c]b means a↑…↑b, with c arrows in total. So a^b would be a↑[1]b. 3↑↑↑3 would be 3↑[3]3.

You know what I’m going to do. I can’t stop myself. If I knew any Medusas, I’d be a statue by now, because I wouldn’t be able to resist sneaking a peek.

There’s no turning back. It’s too late for you now. Too late for me.

Consider the number 3[3↑↑↑3]3. That’s 3↑…↑3, with seven trillion arrows. Think of the endless eternities of parentheses and arrows and evaluations, and that wouldn’t even get you close to the number of digits in this horror. Let’s call this horror X.

Now consider 3↑[X]↑3. Call it Y.

I imagine that my punishment in Number Hell will be evaluating 3↑…↑3, with Y arrows. And that’s infinitely smaller than 3↑[3↑…↑3 with Y arrows]↑3.

I’m not exaggerating for dramatic effect: I am genuinely smelling rotten eggs right now. I think I might have given myself a stroke. But before the aphasia sets in, let me introduce you to the Devil Incarnate: the Ackermann Function.

The Ackermann Function is the kind of thing they must’ve tortured Winston Smith with in 1984. It’s the reason some mathematicians walk around with that horrified thousand-yard stare. It’s an honest-to-goodness nightmare.

The Ackerman function is dead-simple. You write it A(a,b), for positive integers a and b. Here’s how you evaluate it.

If = 0, then A(a,b) = b+1

If a > 0 and b = 0, then A(a,b) = A(a-1,1)

If > 0 and b > 0, then A(a,b) = A(a-1,A(a,b-1)).

Simple rules. Not simple to apply. For instance, A(2,2) = A(1,A(2,1)) = A(1,A(1,A(2,0))) = … a horrifying mess of parentheses that ultimately gets you to 7. At least it’s a sensible number. So is A(3,2). It’s 29. A(4,2), on the other hand, is over 19 thousand digits long. When I typed Ackermann(4,4) into WolframAlpha, it actually told me “(too large to represent).” It’s always nice when a computation engine built by one of the masters of symbolic computation says “Hell with this. I give up.”

You know how evil I am. You know what I’m going to do. You know how psychotic and depraved I’ve become after looking at unfathomable numbers for an hour.

The Number of the Devil isn’t 666. It’s Ackermann(666↑↑↑↑↑↑666,666↑↑↑↑↑↑666).

Sleep well. I know I won’t.

Standard
Uncategorized

How Many Novels Can There Be?

I like reading. I like writing. When you’ve been writing for a while, you start to get really obsessed with word counts. Anybody you talk to about publishing something you’ve written will want to know your word count. For short fiction, you sometimes get paid by the word. And the number of words in the thing you’ve written determines whether it counts as a short story, a novella, a novel, as War and Peace, or as an encyclopedia.

Every year, I participate in National Novel-Writing Month. Unless, you know, I don’t feel like it. But I’ve participated more years than not, and I’ve produced a surprising number of novels. Every single one of them terrible, but that’s not NaNoWriMo’s fault. The goal in NaNoWriMo is to write a novel of at least 50,000 words in 30 days. And I got to thinking: how many novels that length are there?

Well, in the English language, there are somewhere between 100,000 and 1,000,000 words. But you’ll be able to understand 95% of everything written in English by knowing only the 3,000 most common ones. After all, even though it’s a valid word, people generally don’t go around calling each other antipodean anymore.

The question is: “How many 50,000-word novels are possible, using mostly the 3,000 most common words?” The naive answer is to allow each word to be any of those 3,000, which means the number of possible novels is 3,000^(50,000). That’s 1.155 x 10^173,856. You’ll be happy to know that this number is so large that, when I tried to copy and paste it into this article, it crashed my browser.

Of course, this will include novels that consist entirely of the sentence “Anus anus anus anus anus!” over and over again, which is so avant-garde it makes me want to go pee on Samuel Beckett. The list will also contain more coherent, although still somewhat dubious works, like Stuart Ashen’s peerless desk reference, Fifty-Thousand Shades of Grey. But Fifty-Thousand Shades of Grey is actually constructed of coherent sentences. (Well, one coherent sentence, at least…) Most of the novels in this ridiculously long list will be more along the lines of “Him could carpet but also because you die but but the but the but the butt.”

We’re working from a flawed assumption: that a text is just a bunch of words stuck together. But unless you’re James Joyce (or, to a lesser extent, Stephanie Meyer), that’s not how it works. A novel is a bunch of words stuck together in a particular way. Although “that that” is grammatically valid (even though it looks weird on the page), “the the” isn’t, and “centipede cheese carpet muffin” is the kind of thing I say when I haven’t been getting enough sleep.

We’ve been working from the assumption that any word is equally likely to follow any other word. That is, that all word-pairs are equally likely. They’re not. “Our way” is a lot more common than “our anus,” for instance. Naively, the probability of any two-word combination is (1 / 3,000)^2, or 1 in 9,000,000. To put it another way, there are 9,000,000 two-word pairs, 25,000 of which would make up our nonsensical novel. It’d be much closer to reality to assume that, on average, there are only 50 words that make sense after a given word (the number will be much higher (in the thousands, I’d imagine), for words like “the”, and lower for words like “hoist.”) So, in reality, there are only 150,000 two-word combinations that make sense.

We could extend this to three-word combinations, but there are two problems with that: 50,000 isn’t evenly divisible by three, and that repeating decimal will drive me crazy. More importantly, the longer your word-block, the more words become possible at the end, until you’re getting close to 3,000 possibilities again. For example: “The” could be followed by any noun in our 3,000-word list. “The man” must be followed by a verb, the start of an adjective phrase (example: “The man I met last summer“), or something like that. “The man talked” will likely be followed by a word like “to” or “about.” But there’s an enormous range of things that the man could be talking to or about, so pretty much any noun or participle is fair game, bringing the number of possibilities back up into the thousands again.

So how many novels can there be? Well, the upper bound is probably (as we’ve seen), (3,000 * 50)^25,000, which is 1.912 x 10^129,402. That’s still a number so large there’s no name for it, but it’s smaller than our first number by almost fifty thousand orders of magnitude, which is something.

But let’s take it one step further. To simplify the math, I’m going to skip right to four-word combinations. And let’s say that any two-word combination forms the start of a phrase, and that the third word in the phrase can only be one of 10 words, on average. And, to take into account the fact that the number of choices start rising again with a long enough phrase, let’s say the fourth word can be any one of 500 words. The number of possible 50,000-word novels is now (3,000 * 50 * 10 * 1,000)^(12,500), or 1.382 x 10^114,701. So we’ve chopped off another ten thousand orders of magnitude. Still, that’s a big number. And, although I don’t have the math or linguistics background to prove it, I’m guessing that’s pretty close to the number of actual, sensible novels you could construct with 50,000 words: it takes into account the rough structure of the English language. This is related to the idea of a Markov Chain, which is a mathematically-formal way of saying “where you’re likely to go next depends on where you’re at now.”

For your amusement, I’m going to back up this post, and try to copy and paste (3,000 * 50 * 10 * 1,000)^(12,500) just below. If you see a horrific salad of numbers, you’ll know it worked. If you see an apology, you’ll know it crashed my browser again. Wish me luck!

Sorry. It didn’t work. Browser crashed again. But that’s probably good news for you, the reader, since, when I pasted the number of possible sensible novels into my word processor, it produced a document 32 pages long consisting of nothing but digits in 12-point Helvetica. I think that’d make most people’s eyes bleed. Or explode. Or sprout wings and fly away.

The moral of this story is: don’t worry about machines taking over the writing of novels. If a computer could output one word of its current novel every Planck time (which is generally agreed to be close to the shortest time interval that makes sense in our physics), the time it would take would be larger than the current age of the universe. And that’s an understatement. It would actually be so much larger than the current age of the universe, that if I were to express it as a multiple (in the same way I say 10^24 is a trillion trillion times larger than 1), then I’d have to write out the word “trillion” 9,558 times just to express it. If I allow the convention that 1 googol googol is (10^100) * (10^100), or 10^200 times bigger than 1, then I’d need to write “googol” over 1,100 times. There is simply no good way to express the size of this number. It’s 10^110,000 times larger than the age of the universe in Planck times, the diameter of the observable universe in Planck lengths, and the number of particles in the universe.

Boy oh boy. I started out talking about novels, and now I’m getting into numbers that trip the circuit breakers in my brain. Math can be scary sometimes. And you wanna know the scariest thing? There are numbers, like Graham’s number and the outputs of the Ackerman function for inputs larger than (6,6), that make the number of possible novels look exactly like zero by comparison, for any practical definition.

…I need to go lie down now. Although I’m probably going to come back later and talk about really enormous numbers, because part of my brain seems to want me to have a stroke.

Standard
Uncategorized

The curse of dimensionality.

(The coolest part of this article will be that “The Curse of Dimensionality” is an actual legitimate term from computer science, even though it sounds like something from H.P. Lovecraft’s nightmares. But it’s a real scientific thing. Take a look.)

I like cellular automata. A cellular automaton is a bunch of cells arranged on some kind of grid. Each cell has a “state” variable. Each time-step, it decides which state to go into next according to a rule which looks at its current state and the state of all the cells around it. It’s about as simple as a computer simulation gets, but even in one dimension, it can produce amazing psychedelic patterns like this one:

Image

(The picture is two-dimensional, of course. Each timestep, the one-dimensional line of cells is rendered as a line of colored pixels, with its distance from the top increasing as time goes on. Click on the picture to get a version that isn’t all compressed and horrible.)

It doesn’t take much processing power to run a program like this. For instance, a 1-D cellular automaton with 1,000 cells and 8 possible states would only require 1,000 bytes of memory.

2-D automata take up a little more space, but they can still run smooth as butter on most computers, especially with neat, streamlined code. In two dimensions, an 8-state cellular automaton on a grid measuring 1,000 by 1,000 (1,000,000 cells) would only require a megabyte.

But you know me. I don’t like it when things are easy. I like it when things are weird. What if, for instance, we imagined a 3-dimensional cellular automaton? Here, each cell has 27 neighbors (itself and the cells adjacent to it and touching its corners and edges). If this cube of cells measured 1,000 cells on an edge (and each cell could still be in one of 8 states), then the cellular automaton would need 1 gigabyte of memory. I’m old enough to remember when that was an impressive amount, and indeed, processing a gigabyte of at 30 frames per second takes a bit of power. More power than a Pentium III chip had in 1999, at least.

But couldn’t we go bigger? OF COURSE! In a 4-dimensional cellular automaton, every cell has 81 neighbors, we’ve got a trillion cells, a terabyte of data (you’re probably going to need an extra hard drive), and our throughput would strain even a modern graphics card.

But let’s go BIGGER! I like the number 6, so let’s imagine a cellular automaton in 6 dimensions. Every cell has 729 neighbors adjacent to it. (Remember the good old days, back in 2 dimensions, when every cell had a measly 9 neighbors?). We’re going to need 1 million hard drives to store all those 8-bit numbers (there are 1,000,000,000,000,000,000 of them, after all), and we’re going to need a supercomputer more powerful than any currently in existence to handle the 60 exaFLOPS needed to maintain a smooth 60-FPS framerate. We will also need an air conditioning unit the size of a house, but don’t we always when I’m around?

But this is baby stuff. When scientists talk about high-dimensional mathematics, they’re not talking about hypercubes in 4 or 6 dimensions. They’re talking about crazy curves and datasets in, say, 256 dimensions! 256-D sounds like fun, so let’s go there!

Okay. I think I went too far. Again. For a start, every cell in our 256-D automaton will have 139008452377144732764939786789661303114218850808529137991604824430036072629766435941001769154109609521811665540548899435521 neighbors, which is more than a googol, which is a LOT. Second, the full 1,000 by 1,000 by 1,000 (by 1,000 until you hit 256) automaton would require

1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

bytes to store. That’s 768 zeroes. We’re talking numbers without names here.

What the hell happened? I mean, 256 isn’t exactly a small number. It’s certainly larger than the number of pounds of cilantro you’d want to eat, but it’s hardly huge.

Well, that’s the Curse of Dimensionality. A cube’s N-dimensional “content” (which is an analogue for 3-dimensional volume or 2-dimensional area) is equal to S^N, where S is the length of an edge. And as anybody who’s ever played with numbers knows, throwing exponents into things makes numbers get scary very fast.

And there’s another odd problem that you don’t notice much in two or three dimensions. A circle with a diameter of 2 has an area of (approximately) 3.142, while a square with an edge length of 2 has an area of 4. The ratio of square area to circle area is 1.273. A sphere with a diameter of 2 has a volume of 4.189, while a cube with an edge length of 2 has a volume of 8. The ratio is now 1.910. Well, the ratio keeps going up. And it goes up FAST. A 256-dimensional cube with edge length 2 has a hyper-volume (content) of 115792089237316195423570985008687907853269984665640564039457584007913129639936, which is a lot. Meanwhile, a 256-dimensional sphere with a diameter of 2 has a content of 1.1195×10^-152. That’s an absurdly small number. 1.1195×10^-152 universe diameters (and in case you forgot, the universe is so large that trying to fit its size into your head would probably physically kill you) is ten million trillion trillion trillion trillion trillion trillion trillion times smaller than the smallest distance which makes any physical sense (Side note: isn’t it weird that there’s a smallest physically-sensible distance? Reality has a finite resolution!)

What this all boils down to is that the vast majority of a hyper-cube’s content is in its corners. And, as anybody who’s ever tried to dust a room knows, corners are a pain in the ass. Which is why it’s so hard to work on data-sets in high-dimensional space.

Here’s another interesting fact. I was talking about Lovecraftian horrors at the start. And, although he gets binned as a horror writer, he was actually kind of a horror/sci-fi writer. He liked thinking about non-Euclidean geometry and extra dimensions and other such stuff that was wild and revolutionary at the time. Before I go get some much-needed sleep (I keep having weird dreams about having to take tests so I can work at a pizza parlor. Trust me, they’re exhausting.), let’s work out just how large a 256-dimensional creature would be.

A human being contains approximately 7×10^27 atoms. That’s a lot. If we take (7×10^27)^(1/3) (the cube root), we get how many atoms would lie along the edge of a cube with that many atoms. A cube about the density of a human containing about the same amount of stuff as a human would be 40 centimeters on an edge (Don’t try to imagine ways to make a human into a perfect cube. None of them are nice.) What about a 6-dimensional human? Well, because you can pack so much stuff into a 6-cube, a creature with as many atoms as a human and the same approximate atom-to-atom distance as a human would form a cube 8.7 microns on an edge, about as large as a medium-large bacterium or a human cell. In 256 dimensions, you’d actually run out of atoms before you ran out of places to put them. Imagine you put down one atom at one corner of a big 256-D grid. Then, you start putting atoms in the neighboring cells. Well, in 256-D, there are 115792089237316195423570985008687907853269984665640564039457584007913129639935 neighboring cells, which is more than the number of atoms in a person, so our 256-D human would be no more than two atoms across (no larger than a molecule, in other words) along any dimension.

I don’t know about you, but I’ve succeeded in tripping all the circuit breakers in my head. I’m going to lie down. But I’ll see you again soon, after I find something else headache-inducing to think about.

Standard