By popular request

If you like Penn & Teller and zombies, well, this short film has two of those three:

On the other hand, if you need a Penn fix, you can watch Penn talk about stuff instead. (Which, incidentally, is how I learned about the aforementioned video.)

Comeback against cancer

I probably should have posted about this earlier, but I’m going to be up around Purdue this weekend for the big Ship of Fools / Andy Ober Orchestra show, and hanging around for the Ship of Fools‘ performance much later Saturday evening / Sunday morning for Relay for Life, to raise funds for against cancer.

Also, I’ll be performing a bit in that latter show.

Sorry, chess fans, but I probably won’t be doing much to advance the ongoing game while I’m there.

Not the kind of chess master I had in mind

When I started this correspondence-chess-by-blog-comments experiment, I said I didn’t know what would happen, and it turns out I was right:

(11:40:01 AM) Renee: Pawn to D4.
(11:40:01 AM) me <AUTO-REPLY>: Your move.
(11:59:40 AM) me: 1. … d5
(12:01:28 PM) Renee: I roll 3 d6′s for stealth check.
(12:02:45 PM) me: Which piece are you trying to bluff?
(12:02:57 PM) me: Or, um, stealth
(12:03:49 PM) Renee: your knight and that ogre in the corner with the mustache and glasses
(12:04:29 PM) me: You pass your check
(12:04:44 PM) Renee: woo!
(12:09:24 PM) me: The knight can’t see out of his armor and the ogre is distracted by the shiny knight armor
(12:10:37 PM) Renee: I wish to unsheath my sword with a free move, and move towards the
(12:11:50 PM) me: The ogre doesn’t notice
(12:12:21 PM) Renee: am I close enough to strike?
(12:13:03 PM) me: Yes
(12:13:15 PM) Renee: I roll d20 for attack
(12:13:35 PM) Renee: hrm, 10
(12:15:11 PM) me: You swing your sword clumsily and hit the ogre in the kneecap for 7 damage
(12:15:19 PM) me: The ogre notices you
(12:15:54 PM) me: He clubs you for 8 damage
(12:16:07 PM) Renee: ouch
(12:16:33 PM) me: Could’ve been worse — he rolled 1d10 + 1d8
(12:16:42 PM) Renee: am I lucid enough to retaliate?
(12:17:05 PM) me: Yes
(12:17:25 PM) Renee: 14
(12:20:46 PM) me: Um… ok… you 14 the ogre in the eye for 11 damage
(12:21:12 PM) Renee: haha
(12:21:42 PM) me: The ogre is confused by the use of integers as verbs and runs away, dropping his +2 club of clubbing
(12:22:52 PM) Renee: alright!
(12:23:23 PM) Renee: can I discard my sword and take the club of clubbing?
(12:23:36 PM) me: Sure
(12:24:30 PM) me: You pick up the club of clubbing and feel you could attract hot ogre chicks at the disco, assuming your search check is able to locate hot ogre chicks, which are slightly more elusive than the Higgs particle
(12:26:47 PM) Renee: Can I ask the confused knight where the nearest disco is?
(12:28:53 PM) me: The knight offers you directions to The Rook’s Castle on h5. He also comments that his friend as a club just like yours.
(12:30:23 PM) Renee: I thank the knight, and offer him my loose change as a tip for the service
(12:31:28 PM) me: The knight points to the nightclub in the next square, but gives you a long set of directions involving a series of L-shaped hops
(12:33:01 PM) Renee: I disregard his roundabout directions and attempt to move directly into the next square
(12:33:30 PM) me: You succeed
(12:34:38 PM) Renee: I attempt to enter disco through front door
(12:37:06 PM) me: The bouncer (a lawful neutral bishop) asks you to pay the cover before allowing you through. The cover charge is precisely the amount of loose change you previously had.
(12:37:58 PM) Renee: dang
(12:38:16 PM) Renee: I offer to trade goods for entry in place of the cover charge
(12:39:26 PM) me: The bishop impatiently taps a “no bartering” sign with his crosier.
(12:40:16 PM) Renee: I curse myself for not making a character who can read and head back to the neighboring square where the knight was
(12:40:43 PM) me: The knight greets your cordially
(12:41:33 PM) Renee: I remind him of the tip and ask if there’s anyway he would give it back in exchange for something else
(12:42:10 PM) me: He offers to return your tip in exchange for you returning the knowledge of the location of the nightclub.
(12:43:16 PM) Renee: I snicker to myself, and agree
(12:44:29 PM) me: The knight brandishes his +1 sword of neurosurgery and asks if there is any other knowledge you would like to have excised from your cranium during the procedure.
(12:46:06 PM) Renee: I use a free move to hold my club of clubbing up in front of me as if trying to hide behind it, stammering something about maybe there being something else the knight wants instead
(12:48:17 PM) me: The knight dejectedly sheaths his sword and laments that his line of work offers so few opportunities to use his medical degree
(12:49:28 PM) Renee: I sympathize whilst backing towards the door
(12:52:48 PM) me: You find yourself outside on a rectilinear grid. The ground is dark.
(12:54:31 PM) Renee: I roll for “Where to hell am I?” check
(12:55:50 PM) me: You check your CPS receiver and see you are on g5
(12:56:44 PM) Renee: I check for loot
(12:57:56 PM) me: Roll me a search check
(12:58:19 PM) Renee: 16
(12:59:52 PM) me: You find a pointy hat with a diagonal slit in the top sitting on the ground five feet away.
(01:00:29 PM) Renee: cool, always wanted one of these. I take the hat
(01:03:30 PM) me: It looks surprisingly clean, but a little big. It miter might not fit you. [The DM points out he did restrain himself from making any "knightclub" jokes so far.]

I thnk the moral of the story is, if you ever play chess with Renee, bring a source book and some polyhedral dice.

Comments Off

Is the only winning move not to play?

I have no idea how well this is going to turn out, or how long it will last, or even what will happen, but there’s only one way to find out:

1. e4

True or false?

Ryan asks what the point of the true and false programs are. By design those two programs do nothing, either successfully (for true) or unsuccessfully (for false).

Programs that do nothing might at first seem pointless. And if those programs were only ever run by themselves, they would be. However, they become useful tools to have when you start writing shell scripts.

It might not be apparent if your only Unix experience with shells is the command line, but the shell is actually a full-fledged programming language, albeit one with a fairly lean intrinsic feature set. Unix shells provide basic constructs for control flow and variables and such, but rely on other programs to do the “real” work.

In this context, the true and false programs can play the role as boolean values in conditional tests in shell scripts. For example, the following crude reimplementation of yes uses true:

#! /bin/sh
if [ -z $what ]; then
while true; do
    echo $what

The condition of a while loop is actually a command to execute; as long as that command is successful, the loop will continue.

It’s worth noting that the condition of the if also takes a command. Here, the command is [. Yes, that’s the name of a program on Unix. (Or technically, a link to the test program.)

Another use for test is in a makefile. Makefiles execute a series of commands for a target, and abort if any one of those commands fail. You can stick a “|| true” at the end of a command to get around this, like so:

    rm program 2>/dev/null || true
    rmdir tempfiles 2>/dev/null || true

make runs each line in the target using the shell, and gives up once one of the lines reports an error. The || does a short-circuiting logical or on the exit status of the two commands on either side. In this case, if the command on the left fails, it runs the command on the right and reports its exit status as the overall exit status of the command. The end result is that make sees the line as succeeding even if rm reported an error. If we didn’t do that, then in our example rmdir wouldn’t get called if rm failed.

Of course, neither of those examples is necessarily the best way to do things, but they serve their didactic purpose.

Now, if you’re wondering what the point is of trying to implement the functionality of true or false in as small a program as possible, it’s just for either curiosity’s sake and/or bragging rights. In particular, true and false are the simplest possible programs on Unix — all they do is quit immediately — and so any attempt to make the smallest program possible will necessarily reimplement their functionality.

Golf with an elf

I came across this page about making the smallest possible executable binary file using Linux’s ELF executable format. Supposedly with judicious use of absolutely evil hacks, you can get the file down to a scant 45 bytes — which is the size of the ELF header.

Or at least, you could on older kernels. On kryten’s slightly dusty 2.6.18 kernel, the two smallest (and evilest) versions of the program crash, but the antepenultimate one, the 64 byte one, works fine. Which is still quite impressive.

Note that I said 45 (or maybe 64) bytes is the smallest executable binary program you can execute successfully. If you switch over to a shell script, you can get quite a bit shorter. In fact, an empty file will execute successfully:

$ touch empty
$ chmod +x empty
$ ls -l empty
-rwxr-xr-x 1 paul paul 0 2008-03-17 22:32 empty
$ ./empty
$ echo $?

It’s the same basic functionality as /bin/true, which on kryten, weighs in at 22,120 bytes.

Does your computer appreciate ? Day?

It’s that time of year again, when we all reflect on what the ratio of a circle’s circumference to its diameter means to us. But have you ever stopped to ponder what it means… to your computer?

For C programmers at least, the answer might first seem to be found in the the standard library’s math.h header:

# define M_PI           3.14159265358979323846  /* pi */

The M_ prefix denotes it as a constant provided by the math part of the standard library, though you can pronounce it as “mmmm, pie” if you like. Either way, though, that certainly seems like a perfectly reasonable approximation to the transcendental number.

But is it?

To find out, first we need to consider how your computer represents real numbers internally. (OK, technically only rational numbers, and even then only a subset of them.) Most likely, your computer uses the standard floating point representation, which works pretty much like a binary version of scientific notation.

As you’ll recall, since scientists often work with really large or really small numbers that are obnoxious to write in normal notation, they like to move the decimal point around to make the number between 1 and 10, and then multiply the result by the appropriate power of 10 to compensate. For example, instead of writing the number of atoms there are in a gram of 12C as about 602,214,790,000,000,000,000,000, they’d write 6.0221479 × 1023.

Floating point works pretty much the same way, but in binary instead of decimal. For example, the number 13.40625 would be 1101.011012 (using the subscript 2 to denote a binary number), or 1.101011012 × 23.

Of course, floating point stores both the fractional part and the exponent as binary integers, but the precise details aren’t important for this discussion. What is important is how many bits are used to store the fraction and the exponent, and in C we have a few options:

Type Sign bit Exponent bits Fraction bits Total bits
float 1 8 23 + 1 32
double 1 11 52 + 1 64
long double 1 15 64 80

The sign bit denotes whether the number is positive or negative. The more exponent bits we have, the larger and smaller (in the “distance from zero” sense) the numbers we can represent, since we can move the binary point (not a decimal point!) farther to the left or right. The more fraction bits we have, the more precisely we can represent a number, just like 2.718281828459045 is more precise than 2.718.

If you’re paying attention, you might protest that the rows in that table don’t add up. How can we have 1 sign bit, 8 exponent bits, and 24 fraction bits in a 32-bit value, where clearly that’s 33 bits? Easy. In scientific notation, remember how we move the decimal point until the fraction part is between 1 (inclusive) and 10 (exclusive)? In floating point, we move the binary point until the fraction part is between 12 (inclusive) and 102 (exclusive). That means that the fraction part always looks like 1.something2. Since that first bit is always a 1, we don’t need to bother storing it. Woo, free bit! That’s why I wrote 23 + 1 in the table and not 24: 23 stored bits plus 1 implied bit.

The long double type is the oddball, since it’s much more platform-dependent than the other two. On x86 machines, it’s the 80-bit floating point value that the FPU uses internally. Other architectures will probably use something different. Also, the long double format explicitly stores that guaranteed-to-be-a-1 bit at the front of the fraction, presumably because that makes the FPU’s work easier.

Now, with that background out of the way, back to our question: just how accurately can our computer represent ?, without rolling our own data type? Here’s how the three types fare, compared with the true value:

Type Value
float 1.100100100001111110110112 × 21
double 1.10010010000111111011010101000100010000101101000110002 × 21
long double 1.1001001000011111101101010100010001000010110100011000010001101012 × 21
? 1.10010010000111111011010101000100010000101101000110000100011010011…2 × 21

(If you want to check for yourself, here’s the source code I used.)

Now, I may be a master of computer science, but even I have trouble looking at those numbers and seeing how they compare to our buddy M_PI, a.k.a. 3.14159265358979323846. Fortunately, it’s not too hard to compute the maximum rounding error in our floating point values. In general, the magnitude of the rounding error in base b is the number with digit b/2 in the position immediately after the last digit in the rounded number, and zeroes everywhere else. If it were otherwise, the number would’ve been rounded to something else. For a decimal example to make that clearer, the error in rounding ? to 3.14 is at most ±0.005: the true value of ? must be between 3.135 and 3.145, otherwise it wouldn’t've been rounded to 3.14.

Crunching the numbers for our three data types, we get:

Type Maximum error in ?
float ±2-23 ±10-6.9237 ±0.0000001192092895507811309
double ±2-52 ±10-15.6536 ±0.0000000000000002220446049
long double ±2-63 ±10-18.9649 ±0.0000000000000000001084202

To make it clearer still, let’s look at what the decimal values of ? in those types look like, both written out to 21 digits and truncated before we run into any errors:

Type Value Truncated Accurate Digits
float 3.14159274101257324219 3.141592 7
double 3.14159265358979311600 3.141592653589793 16
long double 3.14159265358979323851 3.141592653589793238 19

Moving from float to double roughly doubles the precision we get before losing accuracy, and moving on to long double adds a few more.

For comparison:

Constant Value Accurate Digits
M_PI 3.14159265358979323846 21
M_PIl 3.1415926535897932384626433832795029L 35

It turns out that M_PI is more precise than any of our options for storing it in a floating point value! That makes the GNU extension M_PIl, specifying a long double version of the constant, a bit silly, since we can’t use those extra 14 digits anyway! The only functional difference between the two is the L suffix at the end, telling the compiler to treat the constant as a long double instead of an ordinary double. Without that suffix, assigning M_PI into a long double would still only give us the precision of a double, with those extra fraction bits set to 0.

Of course, in C, storage limits of the different data types is machine-dependent. It’s certainly possible for those same definitions to be used on a machine with larger floating point types that can make use of those extra digits. But for poor old kryten here, it is not meant to be.

For extra ? Day fun, consider that many programs don’t want to depend on having a math.h header recent enough to define M_PI for them, and so define their own version of the constant as a backup. A Google Code search for C programs with “#define M_PI” in them turns up no shortage of hits. Amusingly, many programs have their own ideas as to how many digits M_PI should be defined with.

One particularly fun one is this hit for a 97-digit version of M_PI, if only for the comment in front of it:

 * Ok, so some systems require magic incantations for M_PI to be defined.
 * It's not important enough to worry about.
#ifndef M_PI
#define M_PI 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342117

Also amusing are the “you fail at math” examples, like this one:

#ifndef M_PI
#define M_PI 3.14159263

OK, it’s not as bad as the Indiana state legislature’s infamous attempt to implicitly define ? as 3.2. To say nothing of defining PI to be 12. But still.

So now you know: the great thing about ? is that there’s so many different values for it lurking in your computer. Of course, all the x86 assembly programmers are laughing about this whole mess, since they’ll just use the FLDPI instruction to have the FPU use its value for ? and be done with it.

Comments Off

Great portrait, or the greatest portrait?

Portrait of Stephen Colbert

This weekend I went to the National Portrait Gallery to see the famous portrait of the only man more patriotic than George Washington playing baseball while duct-taped to Abraham Lincoln: Stephen Colbert. Or, more specifically, the portrait of him standing in front of a portrait of himself standing in front of a portrait of himself, hung above his totally-real fireplace during the second year of The Colbert Report.

As fans of the Report know, after being rejected by the National Museum of American History (like anyone really cares about a pair of red shoes), Colbert’s hackey sack skills persuaded the director of the gallery to display the portrait in no less a place than the restrooms just outside the Hall of Presidents:

I can assure you, the portrait is every bit as magestic in person as it was on the Report, with the added benefit of ready access to indoor plumbing. The portrait itself is ridiculously popular — apparently the NPG’s attendance has doubled since it went on display — and is in a comically bad location, with the walls of the lavatorial nook blocking any lateral visibility of the portrait. But that’s not stopping thongs of Heroes and It-Getters from flocking to see it and, naturally, have their picture taken while standing in front of it. Or at least, trying to do so before someone who’s entering xor leaving the restrooms unwittingly walks into the shot.

If you want to get in on the magesty yourself, keep in mind you have until April 1. No joke.

Fun fact: the portrait of Benjamin Harrison on display in the Hall of Presidents is on loan to the Smithsonian from Purdue University’s Harrison Hall.