, , , , , , ,

In his brief 1982 essay (EWD831), computer science giant Edsger Dijkstra examines a topic that (inappropriately, as it turns out) vexes some programmers: Why in the world do computer people count starting at zero? Everyone knows that counting starts at one!

As it turns out, there are two very good reasons for counting from zero!

Dijkstra starts by considering four conventions used to describe a contiguous sequence of numbers — and extremely common programming task. For definiteness, let’s say in this case we mean the sequence of eleven integers from 2 through 12 (inclusive):

  1.    2 ≤ n < 13
  2.    1 < n ≤ 12
  3.    2 ≤ n ≤ 12
  4.    1 < n < 13

All of these work The question is whether any are better than others.

(Note Dijkstra follows the obvious convention of using only less-than and equality operators. See Always Use Less-Than for why that’s such a Good Idea.)

The first observation is that conventions (a) and (b) allow easy calculation of the length of the sequence by subtracting the lower bound from the upper. This seems a positive feature.

A second, related, observation about them is that adjacent sequences share bound value. For example, 13 ≤ n < 18 describes the next five integers following the (a) sequence, and 12 < n ≤ 17 describes the same thing for the (b) one.

So (a) and (b) have two positive features, but no way to decide between them. We need more!

Dijkstra goes on to note that there is a smallest natural number. It doesn’t matter here whether we consider zero or one the start of the natural numbers. What does matter is that conventions (b) and (d), if we desire a sequence starting with that smallest natural number, require an unnatural number as the lower bound!

This suggests we want a convention that uses for the lower bound, as in (a) and (c). Already it seems that (a) is the preferred convention, but there is one further consideration.

What happens if the sequence shrinks to zero-length? If the upper bound is inclusive, we are left a sequence such as 0 < n ≤ -1 (or 5 < n ≤ 4, in the admittedly very rare case of a degenerate sequence with a non-zero index).

Both of those are absurd, so we prefer < for the upper bound, and that means (a) is the winner.


Next Dijkstra considers indexing a sequence of N elements.

Assuming convention (a), if we use 1 for the first index value we have the range: 1 ≤ index < N+1. However, if we use 0 for the first index value we get this range: 0 ≤ index < N.

I think you’ll agree the latter is much nicer! And hence the idiom:

for (int ix=0; ix < max; ix++) {
    /* ...loop stuff... */

Or one very much like it.

{{FWIW, I’ve long used ix (and jx, kx, etc.) as an index variable rather than the simple, harder-to-see, harder-to-search-for, lowly i (and j, k, and so forth). Another good programmer I knew used ii (jj, kk, etc.) which is also good.}}

There is a further advantage in that an elements index says how many elements come before it. The first element, at index zero, has no elements that come before. The second element, at index one, has one element before it, and so on.

Dijkstra doesn’t mention two other advantages:

When cutting off a prefix of a sequence, zero-indexing means the cut boundary is the count of elements desired. For example, substring(5) returns the first five characters of a string (which have indexes 0–4) by pointing to the character beyond the desired sequence.

And, here again, the degenerate sequence (an empty string of zero characters) makes most sense as substring(0).

Finally, there is the situation of multi-dimensional sequences. For example, consider an 8×8 array such as might be used to model a chessboard.

Typically, an array is a contiguous section of memory addressed in either row-first (most common) or column-first order. This leads to a basic formula for calculating the offset of an array cell given a row and column:

cell = (row * ROWSIZE) + col

This only works with zero-indexing! If the array is indexed as (1–8, 1–8), which some programmers feel more comfortable with, then the formula has to be:

cell = ((row-1) * ROWSIZE) + (col-1)

Which just isn’t as pretty. Simply put, zero-indexing makes the math cleaner.

And as we saw, it makes sequence math cleaner in general.

So viva zero-indexing!