Conway

John Conway is a British mathematician who studied and taught at Cambridge University and is now a professor at Princeton. In the programming community Conway is best known as the inventor of the Game of Life, one of the earliest examples of cellular automata, but he has made significant contributions to mathematics throughout his career.

In 1969, Conway introduced surreal numbers, which include real numbers and ordinal numbers. Every real number is surrounded by surreals, which are closer to it than any other real number. In 1974, Donald Knuth described surreal numbers in his book Surreal Numbers: How Two Ex-Students Turned on to Pure Mathematics and Found Total Happiness. The book is notable because Knuth presents the idea of surreal numbers by way of a fictional dialogue.

In 2004, Conway and Simon Kochen, another Princeton University mathematics professor, proved the Free will theorem. The theorem states that if humans have free will, then elementary particles like atoms and electrons must have free will as well.

Conway is also known for being the inventor of the Doomsday algorithm for calculating the days of the week, the puzzle games Sprouts and Phutball, and for providing all 240 solutions for the Soma Cube.

Conway's recent lectures on mathematics and geometry, including his ongoing (at the time of this writing) lecture series on Free Will and Determinism are available for free download through Princeton University.

Books by John Conway
On Numbers and Games
Winning Ways for Your Mathematical Plays, Vol. 2

Worst CAPTCHA ever?

For those of you who don't know, a CAPTCHA is program that can tell whether its user is a human or another computer. They're those little images of distorted text that you translate when you sign up for Gmail or leave a comment on someone's blog. Their purpose is to make sure that someone doesn't use a computer to sign up for millions of online accounts automatically, or to spam blogs randomly with cries for help from Nigerian princes. They make sure an actual human is filling out the form. They work based on the principle that no computer program can (currently) read distorted text as well as a human can.

I have a confession to make. I fail this scaled-down version of the Turing test on a regular basis. There's probably software out there that can outperform my current success rate of just about 2/3. Then there are those challenges that are impossible for human and computer. Just today I was presented with the following CAPTCHA, presumably containing two words.

The image was presented by reCAPTCHA, probably the best anti-bot service in widespread use on the internet. reCAPTCHA works by taking scanned images from books that Optical Character Recognition (OCR) software finds difficult or impossible read and presenting it in CAPTCHAs deployed all over the internet in order to get humans to read the words that the OCR software can't. The goal is to get a bunch of scanned books efficiently translated into digital form. It's a really clever and elegant solution to two problems in one.

Fortunately for enterprising young programmers, the CAPTCHA half of this problem is far from being solved. The line between what a human can read easily and what a software application can read is blurred and constantly changing. New ideas in the battle against Nigerian princes are always welcome.

---

UPDATE: After receiving a comment from Ben Maurer, the chief engineer at reCAPTCHA (and after Googling him to make sure he really is) it seems I have to eat a little crow. After spending enough time on the reCAPTCHA site for a statistically significant sample, I've determined that the image above is an outlier. My guess is that the word on the left is a scanned image or drop cap. Thanks, Ben, for straightening me out on this.

Bruce Schneier is amused.

I threw a foam brick at my TV set this past Monday evening during 24, at the mention of a backdoor designed into the Blowfish cipher. I'm a long-time fan of the show, but not for its steadfast attention to technical details. The show's creators seem to believe that all you need in order to crack any encryption algorithm is an "open socket" and a high enough security clearance.

Bruce Schneier, the designer of the Blowfish algorithm, was gracious in mentioning the episode on his security blog, even providing an excerpt from the show's transcript.

In a response to a comment, Bruce had this to say:

I've never seen the show, and don't really care to. As to how it feels: it feels surreal. I'm not proud to be mentioned, angry they claimed I put a back door in, annoyed they get the details wrong. If anything, I am amused by the whole situation. It's, well, it's surreal.

I won't be surprised if next season's villain on 24 has a manly beard, twin automatic machine pistols, and the uncanny ability to decrypt a box of Alpha-Bits.

Photo courtesy of Bruce Schneier Facts.

National Pi Day

On Wednesday, the U.S. House of Representatives approved a resolution (H.RES.224) sponsored by Rep. Bart Gordon (D, Tenn.), that officially designates March 14th (3/14) National Pi Day. The resolution is aimed at encouraging "schools and educators to observe the day with appropriate activities that teach students about Pi and engage them about the study of mathematics."

In celebration of this nerdy new holiday, tomorrow I plan to dust off my old copy of A History of Pi, and fascinate my friends and family with choice anecdotes about everyone's favorite transcendental number.

C++ Snippets: Time Part 2

In my previous post about telling time in C++, I showed how to display the current Linux system time in a human-readable format. Today I want to go a little bit beyond that and explain how to customize that format.

If you read my previous post, you saw that the asctime function always returns the time in the same format (Thu Mar 12 18:30:50 2009). That's much better than displaying the time in the number of seconds since January 1, 1970, but it still leaves room for improvement.

I'm going to show you how to create a custom format to display the date and time however you choose using the strftime function from the ctime library. I want to rearrange things so the time above would be displayed as:

Thursday, March 12, 2009 06:30:50 PM

First, let's take a look at the arguments that strftime takes.

char *str - A buffer that will hold the formatted output. Strftime was originally a C function, so we can't just return a string. That's okay, though, we'll just make the buffer big enough to hold any time and date in our specified format.

size_t maxsize – The maximum number of characters that will be copied to the output buffer. This should be the same value as the size of the buffer used as the first input parameter.

const char *fmt – Specifies exactly how we want the time to be formatted. There are some special format codes that I'll go over next, but be aware that normal text can be included as well.

struct tm *time - The time value we want to format.

In order to display the time in the desired format, we'll use the following format specifiers:

%A - full weekday name
%B - full month name
%d - day of the month
%Y - year in (with the century)
%I - hour in 12 hour format
%M - minute as a number
%S - second as a number
%p - locale equivalent of AM/PM

We'll combine all of these format codes together, along with normal text delimiters (commas, colons, and spaces) to form one long format string.

%A, %B %d, %Y %I:%M:%S %p

Finally, here's the code:

#include <iostream>
#include <ctime>

using namespace std;

int main ()
{
  struct tm * timeinfo;
  char buffer [80];
  time_t seconds = time(NULL);

  timeinfo = localtime( &seconds );
  char format[] = "%A, %B %d, %Y %I:%M:%S %p";

  strftime(buffer, 80, format, timeinfo);
  cout << "Local time: " << buffer << endl;

  return 0;
}

After compiling the code snippet above, you should see output similar to the following:

$ ./a.out
Local time: Thursday, March 12, 2009 06:53:13 PM

Mediocrity and Genius

Mediocrity knows nothing higher than itself, but talent instantly recognizes genius.

-- Sir Arthur Conan Doyle, (Sherlock Holmes) Valley of Fear, 1915

What Doyle noted nearly a century ago is now known as the Dunning-Kruger effect. It shows that people who are incompetent in areas as widespread as humor, grammar and logic are often blissfully unaware of their own shortcomings. It also shows that incompetent people are often unable to recognize genuine competence in others.

I've talked before about second-order incompetence, and about how it relates to programming. Conventional wisdom among programmers seems to be that being aware of your own shortcomings is really a sign of competence. Knowing that there are things you don't know is a sign of a wise and experienced developer.

This isn't far off the mark, but according to follow-up studies by Dunning and Kruger, it's only a first small step. The skills required for competence in a particular area are the same skills necessary to recognize competence in yourself and in others. It still takes concentrated study in that area in order to raise your competence to the level necessary to be a good judge.

Be Careful What You Measure

Paul Graham's recent post Startups in 13 Sentences got my attention with #7, "You make what you measure." If you want to improve some aspect of your business (or software, or whatever it is you do), measure it. Keep daily track of it and you'll start to notice what sorts of things cause it to go up and down. Do more of those things that make it better.

What I found particular insightful was the corollary, "Be careful what you measure." It made me immediately think of the following quote from Microsoft founder Bill Gates.

Measuring programming progress by lines of code is like measuring aircraft building progress by weight.

If you give programmers incentive by measuring the number of lines of code that they write, then that's what they'll concentrate on. It doesn't really even matter if you want more lines of code or fewer, you'll get exactly what you incentivize. Most likely at the expense of quality.

Eli Goldratt explores this idea in depth in his book Critical Chain. The relevant example in the book is a steel processing plant, but can be effectively adapted to any business. In the book, the new managers of the plant find that employees are cutting corners on quality and efficiency in order to meet their performance incentives. The managers turned the company from the brink of bankruptcy into a profitable company simply by removing the incentives. The lesson? No measurement at all is better than making measurements that cause you to focus on the wrong thing.