Dijkstra: Why numbering should start at zero

http://www.cs.utexas.edu/users/EWD/transcriptions/EWD08xx/EWD831.html

by thunk • 17 years ago

48 71 17 years ago

cs.utexas.edu

lucumo6• 17 years ago

For my MSc thesis I'm programming some stuff for the Cell B.E. processor. It provides AltiVec vector instructions which allow quick parallel computation. It's great for getting nice speed ups, but it requires a lot of thought and bit twiddling from time to time.

It has two C "intrinsics" called vec_mule() and vec_mulo(). These take in two vectors of integer datatypes (char, short) for multiplication and produces one vector with items that are twice as big. char becomes short, short becomes long. To make room for these larger datatypes it only multiplies the even (vec_mule) or the odd (vec_mulo) items.

It's a nice construction, until you start to wonder which elements are even. Is "element 0" even, or is the "first element" odd? Should I really have to wonder about that?

I have never questioned the utter coolness of starting at index 0, until I encountered this. I do not know why we start at 0 if the rest of the world starts at 1, but it seems silly and without reason.

jacquesm4• 17 years ago

Well, the rest of the world also starts at 0:

1 sheep -> the number of sheep present when there is one

0 sheep -> the number of sheep present when there are none

Because you normally only enumerate things that are there it seems like you are starting at '1', but really you start relative to the situation where there are 'none'.

You can't have 'negative' presence of anything so it took a while longer to realize that there might be negative numbers too.

As for element 0 being odd or even, it's even.

So, it isn't silly and it has a reason.

0 is one of the biggest inventions in the history of mankind, programmers have given it it's natural place because we could not make our computers work if we didn't do that.

Imagine binary logic based on '1' and '2'....

lucumo6• 17 years ago

> Well, the rest of the world also starts at 0

Yes, they do, when they have no elements. But if an array has an element 0, it actually has 1 element, not 0. Whereas if I have a sheep 1, I have 1 sheep. There is no sheep 0.

I think it would be good to note that I have nothing against 0 as a number. It's useful for many purposes including to indicate that a set actually has 0 elements, but I'm not so sure it's such a good idea to actually call the first element element 0.

thunk9• 17 years ago

Er, that's all worng. The question isn't number of, but index of. The index of the first element in a collection is 0. The index of the first sheep in a flock is (conventionally) 1. The total elements up to index n (inclusive) is n+1 -- the opposite parity -- which can be initially confusing.

Radix• 17 years ago

I'm happy to see this. I should have submitted it when I found it. The version I found appears to be handwritten by Dijkstra and I like it better that way.

http://www.cs.utexas.edu/~EWD/ewd08xx/EWD831.PDF

thunk9• 17 years ago

Absolutely. His penmanship is as thoughtful as his bearing. I just hate pdf links.

JMostert2• 17 years ago

Did you read Dijkstra's article? He's making the case for 0, though he's doing it a little abstractly. Simply put, if you start numbering at 1, you are setting yourself up for more boundary problems and off-by-one errors than if you start at 0 (and by extension, inclusive lower bounds and exclusive upper bounds). That's not to say that some algorithms are not in fact easier expressed by numbering things from 1, just that they're not the majority.

Oh, and obviously 0 is even. Why? Because 0 mod 2 = 0, 0 is evenly divided by 2, and that's what "even" means. If you need more intuition, though: 1 is indisputably odd, and even and odd numbers alternate, so 0 is even. The rest is philosophy -- you can probably find definitions for "odd" and "even" where 0 is a problem. That's fine, but those don't help. Ignore them. Mathematically there's no problem whatsoever.

The trickiness only comes if you insist in thinking in terms of "the first element", rather than "element number 0". Some people use "zeroth", but this seems to invite more confusion because it induces two meanings for all the other ordinal forms -- if there's a zeroth element, does that mean the "first" element is in fact the second element? Best to avoid ordinals altogether -- you usually don't need any more than "first" and "last" anyway.

dkersten• 17 years ago

"obviously 0 is even"

Sounds like a bit of an odd statement to me.

lucumo6• 17 years ago

> Did you read Dijkstra's article?

Yes, I did. Does it hurt to offer a different perspective? I feel it doesn't. Approaching a subject with an open mind or from a different angle tends to be good for discussion. Offering a contradicting opinion or observation helps everyone to understand an issue better.

> Oh, and obviously 0 is even.

I might counter this with a similar question you asked me: "did you read my post?" I didn't make a case that 0 was odd, I asked how I should look at it: as element 0, or as the first element. If you look at it as element 0, the first element of the vector is an even element. If, on the other hand, you look at it as the first element, you will think it is an odd element. This is the case I made, not that 0 is even.

JMostert2• 17 years ago

> Yes, I did. Does it hurt to offer a different perspective?

No, I was questioning whether you had considered his arguments at all, given the "why do we start counting at 0" question which he tried to answer.

> I didn't make a case that 0 was odd, I asked how I should look at it: as element 0, or as the first element.

You can look at it either way, as both are correct.

> If you look at it as element 0, the first element of the vector is an even element. If, on the other hand, you look at it as the first element, you will think it is an odd element.

Ah, I see your point now. To me this wouldn't be a question because everyone knows programmers start counting at 0 -- a machine instruction would operate on indexes, not ordinals. "The first element" is the element with index 0. It is not "element number one", or if you do want to see it that way, "number one" is the ordinal you use when you start counting on your fingers, which is something we deliberately ignore.

bhousel2• 17 years ago

> I didn't make a case that 0 was odd, I asked how I should look at it: as element 0, or as the first element.

element 0, aka the 0th element..

probablycorey• 17 years ago

I often wonder if Dijkstra's arguments still hold sway, since algorithms written in modern languages differ greatly from those written when Dijkstra wrote this. Rather than writing hash functions or shortest route algorithms, a majority of my algorithms are centered around lists and or dictionary manipulations. There are still many situations where it makes more sense to start indexing at 0, but I wonder if it is still the majority of cases.

lucumo6• 17 years ago

Well, I think that there is a very important human reason to keep sticking to 0 as the start: convention. It has always been this way. Changing it would cause a whole lot of weird bugs.

To be honest, I think one reason why this grew is probably the way C handles array indexing. a[0] = *(a + 0) and this symmetry is a nice property to have in many cases. I think I use that symmetry in my MSc project a lot more than I use vec_mule/vec_mulo.

(Yeah, I'm not of a fixed mind in this matter :-))

g_• 17 years ago

http://en.wikipedia.org/wiki/Evenness_of_zero

Learning that such article could exist (it DOES exist), and reading it was a shocking experience to me.

maweaver2• 17 years ago

Relevant quote from the article:

'A second-year was "quite convinced" that zero was odd, on the basis that "it is the first number you count"'

viraptor• 17 years ago

> you usually don't need any more than "first" and "last" anyway.

Apart from FP people - they need "the first" and "the rest" ;)

TweedHeads9• 17 years ago

I don't care if computers think in 0s and 1s or if arrays should start at 0 because it is the way computers think.

Computers were made to serve us and as such they should translate all their inner thoughts to more human consumable data.

Five is 5, not 101.

So no, numbering should start at ONE, even if most programmers have already been hardwired to start counting from zero.

thunk9• 17 years ago

But he was making the point that there are valid human reasons for zero-based indexing - e.g. keeping the lower bound within the natural numbers; having the upper bound be the number of elements in the preceding sequence, etc. The "way computers think" doesn't enter the discussion.

TweedHeads9• 17 years ago

"keeping the lower bound within the natural numbers; having the upper bound be the number of elements in the preceding sequence, etc."

Read your post and understand the same can be said of using one-based indexing.

scott_s3• 17 years ago

We have this convention for the benefit of humans. Indexing starting at 0 has the convenient property that when we modulus an arbitrary number by the size of a range, the result is a valid index into that range. This comes up when implementing things that map a larger set onto a smaller set, such as buffers or hash tables.

We could still achieve the same effect if we started indexing at 1, but it would require more code, and it would be less clear.

TweedHeads9• 17 years ago

"We could still achieve the same effect if we started indexing at 1, but it would require more code, and it would be less clear."

Really?

How about dealing with strings?

"123456789" how many chars we have? 9

char[1] = 1

char[2] = 2

char[9] = 9

Now, let's try the C approach:

"123456789"

char[0] = 1

char[1] = 2

char[8] = 9

where is char "1"? at zero index!

how many elements we have?

last index plus one!

see? there is already confusion in place, or as you say, more code and less clear...

TweedHeads9• 17 years ago

Look at your hand and start counting your fingers while naming them:

[1] thumb

[2] index

[3] middle

[4] ring

[5] pinkie

so we have a simple range [1..5]

which can be represented in so many ways in computer programs:

for i=1 to 5 print finger[i]

for(i in [1..5]) print finger[i]

my first finger[1] is my thumb

my last finger[5] is my pinkie

how many fingers we have? as many as the last index in the list: 5

now, C programmers like to count this way:

for(i=0;i<5;i++) print finger[i]

where finger[0] is thumb

and finger[4] is pinkie

how many fingers we have?

as many as the last index in the list plus one: 4+1

how human-like!

And that's why you get so messy when trying to get the string position of a substring:

if(pos>-1) exists, since pos=0 means the substring is in the starting position

again, how human-like!

But how dare I argue with C programmers without being burned at the stake?

maweaver2• 17 years ago

for i=1 to 5 print finger[i]

for(i in [1..5]) print finger[i]

You're using an inclusive upper range here. Not that that's necessarily wrong, but it isn't standard for the reason Dijkstra mentioned (how many fingers do I have? 5 - 1 = 4. Oops.)

jongraehl3• 17 years ago

What makes you think people who 0-index arrays and prefer half-open intervals count any differently? Is this argument directed at a four year old?

4+1=5 never enters into it. What a rubbish argument. I might as well complain that your [a,b] has (b-a+1) integers in it. (5-0)=5 so the half open interval has 5 things in it.

What's the measure of a real interval 1<=x<=5? 4. 0<=x<5? 5.

edw519• 17 years ago

I write in primarily in 3 languages, 2 start indexes at 0 and the third starts at 1.

Not withstanding Dijkstra's logical arguments, I have adopted starting at 1 for 2 reasons:

1. I don't have to think about "shifting" data in order to look at it in the third language.

2. I don't have to "think" at all. It's intuitive that the first element is "1".

I just insert a null in the first position of any array in a 0-starting language.

cjbos• 17 years ago

I'm a actionscript developer at my day job and I would totally take up this approach if I didn't have to deal with screen/stage coordinates all the time.

You see, the backend of our project is in Coldfusion which has 1 based indexes for Array's and it has led to head-butting screen confusion when requesting the current index from the server. Then the visual side is always 1 based when showing data to the end-user, I'm always thinking I'm the problem in the middle.

There have been numerous occasions where QA have called me to ask why the first slide in a slideshow is called "Slide 0"!

loup-vaillant• 17 years ago

If you ever have to pack multidimentional data in a flat array, I wish you luck, then. In this case, starting at 1 messes up lookup and insertion. You have to insert "-1" or "+1" pretty often. Too hard to get right in my opinion, I prefer the easier way: to start at 0.

pbhjpbhj• 17 years ago

Shouldn't the "index start value" just be a compilation directive?

embeddedradical• 17 years ago

i couldn't bring myself to stick null pointers here and there for the convenience of syntax :P

i see a lot about code being written for humans, but i'm not onboard with it. elegance in how it executes is #1, and elegance of maintenance is #2.

Xichekolas• 17 years ago

For 98% of all software, 'elegance of maintenance' is vastly more important than your #1. Most software doesn't need the absolute fastest hand tuned implementation, it needs an implementation that the poor schlub who inherits it in 15 years can understand.

Now I'm not agreeing about the particular indexing argument put forth by edw519, I think zero indexes lead to cleaner code whenever you have to do math with them, but unless you can make an honest case for maximum performance, I have to disagree with your assertion about elegance.

gjm113• 17 years ago

I am doubtful about the value of reason 2. "Intuitive", very often, just means "familiar", and I think that's the case here. It's not too difficult to get used to starting at 0, at which point there's no loss in "intuitiveness" from doing so.

Reason 1 has more force. I don't run into it very often when transferring data from one language to another -- I don't do very much of that -- but I do when, e.g., translating between code and standard mathematical notation.

compay• 17 years ago

People sometimes complain about Lua's tables, which use 1 as their first index when treated like arrays. I suppose it could make some algorithms more complicated but in my day to day programming it's never made any difference to me so far.

JBiserkov• 17 years ago

I wish I was shown this in my "introduction to programming course".

All they told us was "because that's how things are. [MEMORIZE IT!]"

Perhaps I should read more of Dijkstra's writings.

Edit: I love when directory indexing is NOT forbidden. http://www.cs.utexas.edu/~EWD/ewd08xx/

Locke16892• 17 years ago

It's fairly straightforward if you're a C programmer and think of arrays as contiguous blocks of memory.

int * a = (int * )malloc(5);

a is a pointer to the beginning of an integer (default 4 byte) array. a[i] == a + i == ((uint8_t * )a)+i*sizeof(int). Therefore, a[0] == a + 0 == the first element in a contiguous block of memory.

discojesus• 17 years ago

which would also illustrate what K&R said about array indices just being syntactic sugar for pointer arithmetic.

My mind has been blown.

gjm113• 17 years ago

If that blows your mind, you might want to avoid looking at the following: "foo"[2] == ("foo"+2) == (2+"foo") == 2["foo"]. And yes, you really can do that: in general a[b] and b[a] are exactly the same thing in C.

BillGoates5• 17 years ago

I am starting to think Dijkstra is about the worst thing ever happening to software development.

He arguments that option A is the least ugly one, but forgets that computers have maximum numbers.

According to Dijkstra, you should test if a variable is a valid integer like: 0 <= var < MaxInt + 1. The best possible outcome of such a test would be a compiler error.

His argument that sequences defined as min <= i < (max + 1) because (max + 1) - min = total number of items is just silly. Maybe true for maths, not so for programmers. When reading code, you want to know if the code is valid, not how many items there are in a list. And reading i <= Max instead of i < (max + 1) is simpler.

Secondly, his article is about 0 or 1 based arrays, not random selections. And in case of 1 based arrays, the max = total number of elements.

So option C is best.

About whether 0 or 1 based arrays are better. They both have their uses. 0 based for spatial coordinates, 1 based for lists and character positions.

thunk9• 17 years ago

1) The memo has nothing to do with testing for MAXINT. Just test it inclusively.

2) You frequently want to know the length of a subseq, and you frequently want successive subseq ranges to dovetail.

3) What in the world does rand() have to do with this?

BillGoates5• 17 years ago

1) He is using real world math arguments why computer arrays should be 0 or 1 based. His example seems valid, but once you use Maxint it fails, proving his argument wrong.

2) Yes, but that has nothing to do with anything I wrote. Also calculating the length of a subset out of a 0 or 1 based array is the same, making your point completely irrelevant.

3) Where in the world do you read anything about rand()?

TweedHeads9• 17 years ago

"I am starting to think Dijkstra is about the worst thing ever happening to software development."

"0 based for spatial coordinates, 1 based for lists and character positions."

Sums up my thoughts pretty well.

The real reason we do zero-based counting in computers is because of bits, speed and laziness.

billswift• 17 years ago

And, of course, it provides an easy way to separate REAL PROGRAMMERS (TM) from everybody else.

nishta• 17 years ago

"Consider now the subsequences starting at the smallest natural number: inclusion of the upper bound would then force the latter to be unnatural by the time the sequence has shrunk to the empty one."

Maybe it is too late, but I don't understand this sentence.

A sequence starting at the smallest natural number would be: 0, 1, 2. The variant Dijkstra is arguing about is: 0 <= i <= 2. How can the latter be unnatural? And what does he mean with "shrunk"?

jongraehl3• 17 years ago

    [0,1) = (0)
    [0,0) = ()
    [0,0] = (0)
    [0,x] = ()

Probably you'd say x=-1 but if you're using unsigned indices, then you can't distinguish the biggest possible sequence from the empty one (this is true of all schemes, actually, but at least the other don't require negative numbers).

Dijkstra: Why numbering should start at zero

Related Stories