How was it decided that if you have an array/struct or anything similiar in a programming language it should be zero-based? Wouldn't it have been easier if it was 1-based. Afer all, when we are taught to count, we start with one.
6
-
10+1 for asking a question most thinking developers wonder about but didnt bother to ask.– DPDApr 23, 2011 at 2:37
-
3Because binary numbers start at zero.– rwongApr 23, 2011 at 4:43
-
10Afer all, when we are taught to count, we start with one. - this is exactly the problem with basic math education, they are on a pre-Peano/Frege/Dedekind level still.– IngoApr 23, 2011 at 12:10
-
7@rwong There's no thing like binary number. There are just numbers and their representations. Unsigned integers starts at 0.– maaartinusApr 24, 2011 at 11:12
-
@maaartinus: yes you're right. In any base-n numeral system, a string of zeros (in base-n) will give you zero, the lowest non-negative number. Zero is also the additive identity, so it is required to be present for calculations. If, however, a programming language choose to start with one, it's just as simple - skip the element [0].– rwongApr 24, 2011 at 20:04
|
Show 1 more comment
9 Answers
All good answers. A good part of my "career" was spent in Fortran, where all arrays are 1-based. It's OK if you're writing math algorithms over vectors and matrices, where indices naturally go 1 .. N.
But as soon as you start trying to do computer-science type algorithms, where you have a big array and you are working on pieces of it, as in binary search, or heap sort, or if it is a memory array and you are writing memory allocation and freeing algorithms, or starting to act like parts of it are actually multidimensional arrays that you have to calculate indices in, that 1-based stuff gets to be a real source of confusion.
For example, if you have a 1-dimensional array A, and you want to treat it as a 2-dimensional NxM array, where I and J are the index variables, in C you just say:
A[ I + N*J ]
but in Fortran you say
A( (I-1) + N*(J-1) + 1 )
or
A( I + N*(J-1) )
If it was 3-dimensional, you had to do
A( I + N*(J-1) + N*M*(K-1) )
(That's if it was column-major order, as opposed to row-major order which is more common in C.)
What I learned to do in Fortran, when doing string manipulation algorithms, was never to think of an index I as being the position of an element in an array. Rather I would think of a "distance" N as being the number of elements coming before the element of interest. In other words, always think in terms of "number of elements" rather that "index of element". That enabled me to work within what was an unnatural indexing scheme.
answered Apr 23, 2011 at 2:56
-
15+1 - the bottom line is that indexing from zero results in simpler programs overall. Once programming language design stopped being overly influenced by mathematical convention, common sense prevailed. Apr 23, 2011 at 3:19
-
2@Mike On the other hand, with 0-based arrays you always have to do
a[pos-1]to get what you want. The only case where 0-base feels natural is when looping, but that's only because the idiomfor(i=0;i<len;i++) a[i];works. Apr 23, 2011 at 9:29 -
In my opinion, this is the "correct" answer, but there are trade-offs. One trade-off, as you mention, is its use in 1 dimensional vs. multidimensional arrays. Base 0 indexing if of huge benefit when calculating multidimensional indexes. In higher-level programming, however, the use of 1 dimensional arrays, however, vastly outweighs the usage of multidimensional arrays. Further, the complexities of multidimensional indexing can be written once and encapsulated within a method (or indexer). [Continued...] Apr 23, 2011 at 14:37
-
1In low level programming, however, say asm or C, where performance is at a premium and inlining might not be available, the use of encapsulation might not be desirable or possible; so the benefits of base 0 indexing really manifests itself. So base 0 indexing is superior at the low end, while base 1 indexing is superior at the higher, more abstracted level. [Cont...] Apr 23, 2011 at 14:37
-
1The problem is, where does one make the switch? The switchover from base 0 at a low level to base 1 at a higher level is extremely dangerous and fraught with innumerable places to forget to add or subtract 1 when making a conversion. So the bottom line is that it's not worth the risk of making the shift. Usually the "shift" occurs only in the output, where the user is shown a list that is (hopefully) numbered 1 to N and not numbered 0 to N-1. (But I've seen plenty of displays that mess this up!) Apr 23, 2011 at 14:37
Think of an array index just as an offset from the start.
-
5That's the real reason. In languages like C the index of an array is actually kind of an offset. E.g. the offset is the index times the data type length. With 1-based arrays this would be much more complicated. Apr 24, 2011 at 6:56
-
Yes. I think C started with the mentality of an assembly programmer. And in assembly it was convenient to use a pointer to the adrress of the zeroth element, and add size times the index to that. Apr 24, 2011 at 15:55
-
2I think the main reason C was able to adopt and maintain this convention is that it did not have a marketing department. Apr 24, 2011 at 22:06
-
Dijkstra answered this very clearly in http://www.cs.utexas.edu/users/EWD/transcriptions/EWD08xx/EWD831.html - though Pascal programmers didn't agree.
-
12
-
16I think Dijkstra's eplanation suits fine. The reason people get peeved at zero-based indices is that they count from 1 and feel that indexing should also start from 1. They fail to understand that indexing is not the same as counting.– DPDApr 23, 2011 at 2:41
-
4Although it's rarely profitable to disagree with EWD, I reject his assumptions as well as his conclusions. In his example, I prefer C) much more than A).– red-dirtApr 23, 2011 at 12:50
-
3@Mike: I disagree that [0, -1] is 100% clear. It definitely wasn't intuitive to one of my co-workers who wrote an HTTP server that needed to deal with empty ranges.– dan04Apr 23, 2011 at 15:14
-
2Furthermore, -1 as the lower bound of an empty array forces the use of signed rather than unsigned indices.– dan04Apr 23, 2011 at 15:16
The difference is that it's not a human counting, it's the computer. It is easier for computers to think of 0 as the first item, as it is usually just an offset from the memory location. It's logical to start at 0000, then 0001, then 0010. If you started at 1, you would either lose available index (acting like 0000 isn't valid) or have awkwardness to make sure that the compiler always knows it should decrement the index by one before it actually works.
Plus it isn't that hard to pick up after your first programming class and you are told this is the way things work.
answered Apr 23, 2011 at 2:08
-
9It is easier for computers to think... - really??? Programming languages are designed for human comprehension first. A compiler can easily handle the detail of 1-based vs 0-based arrays.– btillyApr 23, 2011 at 2:10
-
11@bitlly: 0-based indexes date back to when the extra decrement required to implement 1-based array lookup was a significant performance hit.– BevanApr 23, 2011 at 3:04
-
4@Bevan: Why would there be an extra decrement with 1-based array lookups? The trivial solution is of course to take the indexing into account in defining your base pointer, thus removing altogether any requirements for extra decrementation.– SchedlerApr 23, 2011 at 6:02
-
3@Schedler that only works if you know in advance what the pointer is going to be used for. Unfortunately, this only works when you have strong typing, which you don't really have in C or assembly language. Throw in the fact that you don't normaly have the luxury of keeping the base pointer around (due to lack of registers and/or stack space), and you end up with having to recalculate the address every time.– BevanApr 23, 2011 at 9:36
-
4@Bevan: Citation needed. Also please explain why FORTRAN, invented decades before any currently used 0-based language, managed to get away with 1-based array indexes.– btillyApr 24, 2011 at 6:13
In mathematics for centuries the subscript of a series has been chosen for convenience and meaning. For example in a polynomial, the coefficients are usually labelled a0, a1, a2, a3, etc. because the zero represents the power of the corresponding term. In computer science, the subscript represents the offset relative to the beginning of the array.
-
Yes, but that means in C you have to remember to dimension your coefficient array by n+1, which is oh so easy to forget. Apr 24, 2011 at 15:56
-
It helps to remember to index by the offset but allocate by the length. Alternatively the length is just the offset to the first unused element. Apr 24, 2011 at 20:29
I see two reasons:
The low level one. If you start with 0, than the pointer element indicated by index is pointer of array + index (a[i] and a + i point to the same memory address). This is very convenient.
On a bit higher level of abstraction -- very often you will have to use modulo function for indices. Modulo n always returns values from 0 to n-1. So it's also more convenient when indices start with 0.
From a modern standpoint (i.e. interpreted languages or recently developed languages such as C#) this is likely due to developers and thus language designers learned to develop since languages such as C make use of zero indexed arrays. As to why languages have made use of the zero index for arrays, the index is due to how the array is stored. In C, the use of the array index array[1] is the same as using the pointer reference, i.e. array + 1. Wikipedia also has a bit more on the subject, but that is one reason in a nutshell.
As has been pointed out, not all languages use 0-based indexing. For example in Ada you can define your indexing basis freely. For String type for example 1-based indexing is used.
The benefit of this is that you can define the indexing to best match the intended usage. In some cases it might sense to for example define the array bounds as -1..+1.
For example a symmetric 5x5 kernel for convolution could be defined as
type KernelT is array (-2..+2, -2..+2) of Real;
Similary enumerated types can be used directly for array indexing.
-
1I have seen this (ab)used to create some very unclear code (admittedly, in Algol 68 but the principle is the same). What was worse, the code looked clear at first glance; it was only when trying to convert into a different language that it became clear that things were obscure… Apr 23, 2011 at 14:32
The simple answer is zero is simpler when one tries to calculate the actual address in memory. If an array starts at location 12345 and you wish to access element 678 then adding the two gives the location that needs to be read. Note the above assumes the array holds bytes and is of course bigger than 678. If you used 1 based indexing then an additional subtract 1 would be required. This quickly becomes a pain andall things said 1 does not really buy anything.
