Thursday 10 September 2009

My son Max is taking a computer class in high school, and described a class exercise involving a deck of cards numbered 0 to 51. I asked him if there was any discussion in class about why it wasn’t 1 to 52. He said the teacher told them that if they learned C++, they’d understand why it started from zero.

I guess the teacher meant pointer arithmetic makes it obvious, but I remembered a more scholarly exposition: Edsger Dijkstra wrote a brief paper called Why Numbering Should Start at Zero. He lays out a mathematical explanation that has nothing directly to do with pointers.

I’m impressed by Dijkstra because of his methodical approach to even the seemingly most trivial detail of computing. He was willing to stop, think through, and explain why something should be done a certain way, no matter how small.

Earlier today over lunch, we discussed the amazing foresight of the AT&T engineers who laid out the North American area codes. We marvelled at the care they took with designing a solution to a problem that wouldn’t hit for a decade or so. How often do we see that kind of care and attention to detail in day-to-day work?

Both examples made me stop and admire true professionals, engineers building carefully, making sure to get it right no matter how far off the consequences. Thanks, guys. We should each try to channel your spirit in our own work.

## Comments

Alistair11:58 PM on 10 Sep 2009I was only talking about the same sort of thing with someone at work recently regarding the foresight of some of the early Google engineers to recognise issues with, say data growth & management - which led them into creating a system which would facilitate that going forward.

You're absolutely right though, some things in everyday life which are taken for granted actually took someone to really sit down and work through a problem to get it right. Others people don't even see, Google's GFS as an example and simply use the product without any care of understanding about just how incredible the GFS service is.

Giacomo1:55 AM on 11 Sep 2009On the other hand, "premature optimization is the root of all evil"...

Ned Batchelder5:30 AM on 11 Sep 2009@Giacomo: you are right, and maybe this is where some of the hard engineering is: knowing the difference between premature optimization and the important design properties to get right up front, even if you won't have to worry about it for ten years.

andrew5:40 AM on 11 Sep 2009good use of "pernicious"

Juho Vepsäläinen6:37 AM on 11 Sep 2009Nice find!

rather than in Python.I might be inclined to write

Using range might give some tiny performance penalty compared to latter. Hence if it's performance you are after you might write a code generator to replace it with latter. But if you are after performance you won't be writing this kind of code in Python anyway. :)

[1] Writing < and = together (no whitespace) seems to break your preview and possibly the post text (not tested) by cutting it right there.

Doug L.10:40 AM on 11 Sep 2009Tangentially related: "Should array indices start at 0 or 1? My compromise of 0.5 was rejected without, I thought, proper consideration." -- Stan Kelly-Bootle

Ed Davies11:45 AM on 11 Sep 2009Well, pixel numbering should start at 0.5.

Jeff Kaufman1:28 PM on 11 Sep 2009When you actually look at the paper, the reasoning he gives for numbering starting at 0 is:

What this actually comes down to, after stripping all the mathematical language away, is a claim that "0 <= i < N" is nicer than "1 <= i < N+1". I happen to agree, but I don't think this should convince anyone who already prefers to start at 1. To me the "uglyness" of starting at 0 is small (I'm used to it) while to someone else the uglyness of ending with N+1 outweighed by the simplicity of starting at 1.Ben Karel3:52 PM on 11 Sep 2009As others have mentioned, Dijkstra's reasoning is valid, but I'm not sure it's sound.

One consideration he doesn't address is the significant cultural preference, if you will, towards naming indices by the positive integers. Even as a C++ programmer long past the stage of uncomfortableness with 0-based indexing, in my head I still say "the first element," "the second item," "the third thing," and so on.

There is also the issue of exactly what operations on intervals should be optimized. The interval [A, B) makes it "easy" to determine the length of the interval and the first element but not as easy to determine the maximum element of the interval. (A, B] makes it easy to determine the length and the maximum element, but not the minimum element. And [A, B] makes the min and max easy, but not the length. Finally, the half-open intervals are easier to add; another point in their favor.

Even if we grant his having established the mathematical superiority of closed/open intervals starting at 0, the real question then becomes: does the mathematical attractiveness outweigh the impedance mismatch with entrenched habits?

It would be nice and simple to categorically say "yes," but it's not clear that that's true. Off-by-one pointer errors in C due to the above-mentioned disconnect, for example, have had measurable economic impact.

Charles Monk4:45 PM on 11 Sep 2009I agree with Jeff Kaufmann. The argument seems to hinge on "Nicer", which is simply introduced without any justification.

Dijkstra uses the 0..n-1 for his page numbering in this note. Dogma has apparently triumphed over elegance and convention here. Wouldn't this be even more confusing if the total number of pages were also displayed? The final page would be labelled "Page 2 of 3". Now that would cause some

realproblems in an examination!Kerry3:34 PM on 13 Sep 2009So why not use 1 <= i <= N ?

Jeff Kaufman6:11 PM on 13 Sep 2009@Kerry: the reasoning he gives against 'start <= i <= end' is at

the beginning of his paper. He says that 'A <= i < B' and 'A < i <= B' are better because they:

Shannon Love8:13 AM on 20 Nov 2009As long as we're dreaming, I would like division to be based on the number of "cuts" made to divide instead of the number of resulting pieces. Doing so would eliminate the divide by zero problem.

So, 9/2=3, 8/2=2, 6/1=3, 4/1=2, 1/1=0.5 and most importantly n/0=n.

Now, I just have to persuade everyone to overturn millennium of mathematical convention just so I don't have to watch for divide by zero exceptions.

## Add a comment: