Arrays Indexed From One

This essay is an attempt to get to the bottom of the age-old computer science questions: Is it better to index arrays from one, or to index arrays from zero?

There have been many arguments for and against both these styles of array indexing over the years, and some have come from quite famous mathematicians and computer scientists. For example, Edsgar Dijkstra had some things to say on the topic. But to my mind many such arguments either group two notions together in an unjustified way (the issues of index starting points, and end-point inclusion vs exclusion), or ignore syntax or conventions which could work around problems, for example the use of negative indices as demonstrated admirably in the programming language Python (which I will use as a comparison throughout this essay).

If you don't know Python, it has a neat array indexing scheme somewhat similar to C except you can form array slices and use negative numbers to index from the end of the array. (I could have called Python's indexing scheme IndexFrom0CircularExcludeEnd to match how I've named some of the other schemes I describe, but Python is so much more concise.)

Comparison Method

To try to determine whether one-based indexing is better or worse than zero-based indexing, I will examine several array use cases, that is, the things programmers want to do with arrays. After all, an index is only useful if it is a convenient short-hand notation which a programmer can use to write an algorithm. That is the ultimate measure of a good indexing scheme: does it allow the programmer to concisely and unamgibuously express an algorithm?

First, some notation:

• A is the array of things we are manipulating. For the sake of argument, we'll assume it holds the first ten letters of the English alphabet, in uppercase.
• i is an index into the array, in whatever indexing scheme we're using.
• s is the starting index (inclusive) of a slice (a sub-array)
• e is the ending index (inclusive) of a slice (a sub-array)
• n is the number of elements in the slice
• N is the number of elements in the array

Although I've defined e to be the inclusive end-point of a slice, this does not mean I'll ignore the question of whether end-points should be included in a slice. Some definition of e is necessary so we don't become confused half-way through discussing that question.

Use Cases for Arrays

There are many use cases I will examine in the following sub-sections, including:

• Stepping right through the array
• Visiting the first or last N elements
• Slices (sub-arrays)

The purpose here is to gather evidence of whether a particular indexing scheme is better or worse for each purpose.

Array indices

In Python, arrays are indexed from 0, but can also be indexed (from the end of the array) using negative numbers, as illustrated:

	Python:
		  0  1  2  3  4  5  6  7  8  9
		  A  B  C  D  E  F  G  H  I  J
		-10 -9 -8 -7 -6 -5 -4 -3 -2 -1

For comparison study purposes, we can introduce, by analogy, a couple of new indexing schemes which are similar to Python's scheme, but which index from one instead of indexing from zero:

	IndexFrom1Without0:
		  1  2  3  4  5  6  7  8  9 10
		  A  B  C  D  E  F  G  H  I  J
		-10 -9 -8 -7 -6 -5 -4 -3 -2 -1

	IndexFrom1Circular:
		  1  2  3  4  5  6  7  8  9 10
		  A  B  C  D  E  F  G  H  I  J
		 -9 -8 -7 -6 -5 -4 -3 -2 -1  0

The first scheme omits zero, but this may have some benefits. For example, zero could be used as an error marker, or be used to indicate the start or end of the array in some context-specific manner (much as -1 is used specially in Python to indicate a sub-string isn't found, and slices can omit the start or end points so too we could use zero to indicate some special point in the array).

In the discussions below I'll refer to IndexFrom1 as a generic name for any indexing scheme which indices from one. Only where the negative indexing or inclusion of end-points becomes significant will further qualification be given.

Obtain an element

To obtain an element from an array, we use this notation:

	A[i]

Note, this A[i] notation works for all schemes so far discussed. There is no apparent benefit to either indexing scheme.

So far, so good. Let's look at another use case.

Iterate over all elements

A common operation is to visit all elements of an array. This is one of the most common idioms a programmer uses. Each language has some way to do it:

	Python:
		for elem in A:
			print A

	IndexFrom1:
		for elem in A:
			print A

	C:
		int i;
		for (i = 0; i < N; i++)
			printf("%d\n", A[i]);

	C++:
		for (int i = 0; i < N; i++)
			printf("%d\n", A[i]);

		// or, more generally

		iterator it;
		for (it = A.begin(); it != A.end(); ++it)
			printf("%d\n", *it);

	C#:
		foreach (int elem in A)
			System.writeln(elem);

	Java:
		for (int elem : A)
			System.writeln(elem);

Slices

A slice is a sub-array. Often the programmer will know the starting point of the slice, and either its desired length or else an end point. We'll use the Python notation of a colon : to separate the starting index from the ending index, but we'll use a comma to separate a starting index from a slice length (number of elements).

There are three variants of our hypothetical IndexFrom1 scheme, depending on whether we include or exclude the end-points of slices, or simply use the length of the slice instead of an end-point:

So here are the cases:

	You know the starting element s, and the length n:
		C:
			int i;
			for (i = s; i < s+n; i++)
				printf("%d\n", A[i]);

		Python:
			A[s:s+n]

		IndexFrom1ExcludeEnd:
			A[s:s+n]

		IndexFrom1IncludeEnd:
			A[s:s+n-1]

		IndexFrom1UseLength:
			A[s,n]

	You know the starting element s and the (inclusive) end element e:
		C:
			int i;
			for (i = s; i <= e; i++) /* note the extra equals sign */
				printf("%d\n", A[i]);

		Python:
			A[s:e+1]

		IndexFrom1ExcludeEnd:
			A[s:e+1]

		IndexFrom1IncludeEnd:
			A[s:e]

		IndexFrom1UseLength:
			A[s,e-s+1]

	You know the desired (inclusive) end element e and the length n before it:
		C:
			int i;
			for (i = e-n+1; i <= e; i++) /* note the +1 and the equals sign */
				printf("%d\n", A[i]);

		Python:
			A[e-n+1:e+1]

		IndexFrom1ExcludeEnd:
			A[e-n+1:e+1]

		IndexFrom1IncludeEnd:
			A[e-n+1:e]

		IndexFrom1UseLength:
			A[e-n+1,n]

Note also that C programmer can hide some of the complexities of these cases by subtlely adding an equals sign here or there, or using pre-incrementing in the loop test instead of post-loop incrementing. Because these solutions vary the basic idiom seen in the first case, they could hinder comprehension or debugging. (C also has no built-in way to create slices, it simply uses a for loop to visit parts of the array, so in a sense the comparison is overly broad.)

There is a problem we can immediately see with end-inclusion slice indexing... how do you specify an empty slice? We must assume that slices with end-points leftwards of their starting point are empty. I.e. there is no implicit leftwards stepping. This isn't too bad an assumption; Python doesn't let slices implicitly step leftwards if the length is negative either (but you can do it explicitly). It does mean that the slice A[5:5] contains one element (the fifth) but A[5:4] or A[5:0] contain no elements (this latter case could cause problems if we wanted to use zero to indicate the end of the array, since A[5:4] or A[5:1] would be empty but A[5:0] would contain all the elements from 5 onwards).

First n elements

A common case is you wish to find or visit the first n elements of an array, or the first elements up to some known included end-point e.

In Python, this is fairly straightforward and there are many ways to do it. You can take a slice of the first up to n elements, or iterate over the elements from 0 to n-1 inclusive using the range function:

	Python:
		A[:n]
		A[0:n]
		A[:e+1]
		A[0:e+1]
		for i in range(0, n):
			print A[i]

Indexing from 1 but excluding end-points is slightly different from Python because it also introduces several +1 terms when using the length n:

	IndexFrom1ExcludeEnd:
		A[:n+1]
		A[1:n+1]
		A[:e+1]
		A[1:e+1]
		for i = 1 to n+1:
			print A[i]

One advantage this has over Python is regularity; there's always a +1 term in all these cases.

Let's look at the situation when we include end-points:

	IndexFrom1IncludeEnd:
		A[:n]
		A[1:n]
		A[:e]
		A[1:e]
		for i = 1 to n:
			print A[i]

Let's use some examples to see how IndexFrom1IncludeEnd works. To find the first 10 elements of an array, we can form a slice up to and including index 10, hence A[:n], or we can get all elements from element 1 up to and including element 10 A[1:n]. To find a slice which includes element 10, it's the same situation, because the end-point is included, hence A[:e] and A[1:e]. To iterate over the first ten elements we can step from 1 to 10 inclusive.

But what if we use lengths in slices?

	IndexFrom1UseLength:
		A[,n]
		A[1,n]
		A[,e]
		A[1,e]
		for i = 1 to n:
			print A[i]

Some proponents of indexing from 1 schemes stop there and simply note how nice the numbers are. But there are hidden costs is you delve further. Before we do that, a side discussion about ordinals and cardinals.

Ordinals and Cardinals

In mathematics, the term cardinal refers to the (positive) integer numbers, starting 0, 1, 2, 3 and so on. By constrast, the term ordinal refers to the order of a sequence of things, hence first, second, third, fourth, fifth and so on (or, equivalently, 1st, 2nd, 3rd, 4th, 5th). There is no such thing as a zeroth element of a sequence; such a term was invented by computer scientists to simplify (by conflation) their use of cardinals as array indices.

I argue that such blurring of the distinction between the ordinals and cardinals as exemplified by the invention of the term zeroth doesn't help. In fact, it confuses the issue. What is the first element of an array? If we allow the use of the term zeroth when talking about Python or C programs, then we might be talking about A[0] as the first term, or the first term might actually refer to A[1] because the zeroth term is A[0]. It's just confusing.

For the purposes of this essay, I will avoid the term zeroth. Instead, when I refer to the first element of an array, this will be A[0] in the case of Python or C, and it will be A[1] in the case of an index from 1 scheme.

Last n elements

	Python:
		  0  1  2  3  4  5  6  7  8  9
		  A  B  C  D  E  F  G  H  I  J
		-10 -9 -8 -7 -6 -5 -4 -3 -2 -1

	IndexFrom1Without0:
		  1  2  3  4  5  6  7  8  9 10
		  A  B  C  D  E  F  G  H  I  J
		-10 -9 -8 -7 -6 -5 -4 -3 -2 -1

	IndexFrom1Circular:
		  1  2  3  4  5  6  7  8  9 10
		  A  B  C  D  E  F  G  H  I  J
		 -9 -8 -7 -6 -5 -4 -3 -2 -1  0

	Python:
		A[-n:]

	IndexFrom1Without0:
		A[-n:]

	IndexFrom1Circular:
		A[-n+1:]

Depending on whether the end-point is included or excluded or we use lengths in slices, there are a few other schemes we can examine here:

	IndexFrom1Without0ExcludingEnd:
		A[-n:]
		A[-n:0]

	IndexFrom1Without0IncludingEnd:
		A[-n:]
		A[-n:-1]

	IndexFrom1Without0UseLength:
		A[-n,n]

The third scheme, where length is used as the second parameter in the slice, requires the length to be used twice in this use case. This is only a problem when n is computed in an expression within the array brackets, for example A[-(x-y+z),(x-y+z)] seems quite cumbersome, while A[-(x-y+z):-1] is far simpler and doesn't require the expression to be duplicated. A hack of using some suitably large constant like A[-(x-y+z):10000] is the only other solution, and it's an incredibly poor and error-prone solution at that. There's no other way out of this problem with using lengths in slices; there's no way to uniquely refer to the end of the array using that scheme. This can be considered a flaw in the length-based slice scheme.

Clearly, a language syntax which allows slice end-points to be omitted resolves some discrepancies and renders some arguments about which indexing scheme is better moot.

First element

Suppose we want the first element of an array, the very first thing which exists in it:

	C:
		A[0]

	Python:
		A[0]

	IndexFrom1:
		A[1]

Seventh element

To find the seventh element, C and Python add six to the first element's index:

	C:
		A[6]

	Python:
		A[6]

	IndexFrom1:
		A[7]

Last element

To find the last element, you often need to know the length of the entire array N, unless you have a negative indexing scheme as in Python.

	C:
		A[N-1]

	Python:
		A[-1]
		A[N-1]

	IndexFrom1Without0:
		A[-1]
		A[N]

	IndexFrom1Circular:
		A[0]
		A[N]

There's also a symmetry that's worth noting about the IndexFrom1Without0 scheme: the first element is A[1] and the last element is A[-1]. Likewise, the second element is A[2] and the second last element is A[-2]. In general the nth element is A[n] and the nth last element is A[-n]. There's something nice about that.

By contrast, Python necessarily involves a difference of -1 in forward indexing compared with negative indexing, so that, for example, the indices of the second element A[1] and the second last element A[-2] use different numbers.

Identities

It is worthwhile considering the identities or invariants that an indexing scheme affords a programmer. That is, what facts can you rely upon to help you while programming?

Here is the slicing invariant:

	Python:
		A == A[:n] + A[n:]

	IndexFrom1ExcludeEnd:
		A == A[:n] + A[n:]

	IndexFrom1IncludeEnd:
		A == A[:n] + A[n+1:]

	IndexFrom1UseLength:
		A == A[,n] + A[n+1,]

	IndexFrom0UseLength:
		A == A[,n] + A[n,]

Proponents of zero-based indexing schemes often unnecessarily equate "one-based indexing" with "includes end points" and conclude that such schemes are poor because they introduce these +1 terms. I think the use cases up until now show that both indexing approaches suffer from +1 terms, depending on the task at hand, so not only is this argument mis-attributed to "one-based indexing", it's also only one data point in a complex comparison.

Empty slice

Forming an empty array slice is sometimes necessary. It is useful to have a way to reliably produce such an empty slice.

	Python:
		[] == A[i:i]

	IndexFrom1ExcludeEnd:
		[] == A[i:i]

	IndexFrom1IncludeEnd:
		[] == A[i:i-1]

	IndexFrom1UseLength:
		[] == A[i,0]

Including the end-point makes things harder. We must assume that if the end-point is before the start-point that the slice is empty. If we can assume that, then A[10:9] is guaranteed to be empty. But there's a problem. If we apply this identity to index 1, we get the slice A[1:0]. Previously we have noted there are schemes such as IndexFrom1Without0ExcludingEnd where 0 might be used as a special marker indicating the start or end of the array. If 0 marks the end of the array, then the slice A[1:0] would refer to the entire array, but A[2:1] would refer to the empty slice! This inconsistency is a strong argument against using 0 as a context-dependent start-or-end-of-array marker.

The last scheme, in which the length of a slice is explicitly stated, has the simplest mechanism to form an empty slice, simply set the length to zero.

Modulo indexing

Using a modulus operator, such as C's % operator, to generate indices into an array is a common and useful idiom. It works because taking a positive number modulo N (the length of the array) produces a number between 0 and N-1, which then works well as an index into any part of a zero-based array:

	C:
		A[i % N]

	IndexFrom1Without0:
		A[i % N or N]

	IndexFrom1Circular:
		A[i % N]

Some would argue that using modulo arithmetic to generated indices is a hack in the first place, so we shouldn't expect it to be as easy in a different language. But, I think it's a valid use case, and it's something programmers will expect to be able to simply do: given some large (perhaps random) number, form a valid array index.

Using the number 0 as a special marker indicating the end of the array (as in IndexFrom1Circular) solves this problem, but the price is that element 0 is at the end instead of at the start of the array.

Stepping left

Stepping left (from high indices to lower indices) through an array may be less common than stepping from first to last, but it's still worthy of consideration. It isn't as simple as merely reversing the terms:

	C:
		int i;
		for (i = e; i >= s; i--)
			printf("%d\n", A[i]);

	Python:
		A[e:s-1:-1]
		for i in range(e,s-1,-1):
			print A[i]

	IndexFrom1ExcludeEnd:
		A[e:s-1:-1]
		for i = e to s-1 step -1:
			print A[i]

	IndexFrom1IncludeEnd:
		A[e:s:-1]
		for i = e to s step -1:
			print A[i]

Trying to use an array as a circular data structure can cause issues:

	Python:
		A[2] then A[1] then A[0] then A[-1] then A[-2]

	IndexFrom1Without0:
		A[2] then A[1] then A[-1] then...

Conventions

So far, this discussion has tried to focus on use cases of arrays without introducing any historical or domain-specific reasons for preferring indexing from zero or indexing from one.

In this section, such conventions will figure in the reasoning.

Yes, it'd be good if we could prove in some purely mathematical and abstract way which indexing strategy was superior (as Dijkstra tried to show), but sometimes a discussion just isn't complete unless you examine the context in which the discussion is taking place.

Here then are some reasons for preferring one indexing scheme over the other, as illustrated by some real cases.

Binary integer limits

Suppose that to index an array, we use an integer stored in a fixed-sized binary format inside a computer, such as a 8-bit int within the C programming language. Such an integer has a fixed-size within memory, and as such has numerical limits because there are only so many bits of data which can fit within it. In the case of a 8-bit unsigned int, the maximum value it can represent is 255, and the minimum value is 0. Zero-based indexing allows 256 values to be indexed (from 0 to 255).

A problem with one-based indexing is that using such a fixed-size integer as an index only allows you to index 255 elements (indexed 1 to 255, 0 is not allowed), one fewer than a zero-based indexing scheme would allow. A circular scheme which places index zero at the end of the array fixes this problem (but may cause others). Adding one to the index before using it as an index also solves the problem, but requires that the 8-bit integer can be promoted into a larger integer (to store the extra number 256 which is now possible).

Arguably this fixed-size integer problem isn't a huge problem for high-level languages such as Python where numerical types are not limited by bit size in this way. But it is something to consider, particularly when a table of characters must be indexed (for example, during an upper-case to lower-case conversion).

Pixel arrays

Pixel arrays are typically indexed from 0. The point (0,0) is typically the top-left co-ordinate of a bitmap or the screen, with the X axis increasing to the right, and the Y axis increasing downwards (a fact which confuses many a mathematician and physicist more familiar with a Y axis which increases going upwards - another example of different conventions creating confusion).

The fact that zero is used as the basis for pixel arrays means that any computer graphics program which uses arrays to represent pixels will invariably desire zero-based arrays. To use anything else would be unconventional and introduce +1 and -1 terms.

Multi-dimensional arrays

To map multi-dimensional arrays into computer memory (which uses a linear address space) is strongly biased towards zero-based indexing. Indeed, many mathematical operations run smoother when zero is the first index of an array.

This argument sails close to that other argument which says "arrays are just blocks of memory, and indices are just memory offsets (multiplied by the sizes of elements), therefore the first element must use offset zero, and we should index that way accordingly."

The problem with that argument to a proponent of a one-based indexing scheme is that it's tantamount to saying the low-level design of computers is a reason to limit high-level expressions within programming languages. It seems a case of the tail wagging the dog. Low-level details of the computer shouldn't affect language design. If there's a good reason to create a higher level abstraction in the language, we should do it.

The real issue then isn't so much the fact that simulating multi-dimentional arrays inside a one-dimensional array introduces many +1 or -1 terms. The real issue is interoperability with devices, hardware, memory architectures, and indeed, other programming languages.

Interoperability with other programming languages

Perhaps the strongest argument against indexing from one is that it defies common convention in so many frequently used languages (C, C++, Java, C#, Python, the latest Visual Basic offerings, etc), that it makes it hard for programmers to interoperate with those languages.

Proponents of one-based indexing have claimed it simplifies learning for students who haven't programmed before, by giving the first element of an array the index one. While this may be true, it applies only to students who haven't programmed before in one of the other popular languages. It also only simplifies the transition from school to a teaching language at university, but considerably complicates things when that student now wants to learn one of the popular languages in later years, or get a job and not make simple off-by-one errors in daily programming tasks.

Therefore, claiming that indexing from one is simpler for learners is like saying it's easier for people to be taught to drive in a car controlled by joystick instead of steering wheel and pedals: such a style of teaching doesn't prepare people for actual use of other systems, the majority of which aren't designed that way. This interoperability problem is one that designers of teaching systems often ignore or shrug off by focusing only on the problems faced by new learners not by ongoing learning activity, but I consider it a key issue in this debate.

Yet another problem is that of linking C code to an interpreted language. Python, for example, has a mechanism which allows a programmer to compile C code and link it at run-time into the program so an external function can be called from within a Python program. Lua is another interpreted language which just such a capability, however, Lua has used arrays indexed from one, whereas C uses arrays indexed from zero. Passing an array from Lua to C is therefore a slightly trickier operation, because any array indices must have -1 or +1 terms added depending on which direction the data is flowing. Arguably, this is a minor concern, because it would be rare and confined to language implementors, rather than general users. But one of the selling points of interpreted languages like Python and Lua is that they can act as "glue" for quickly tying functions and libraries together. This translation problem hinders that goal by slowing integration of functions from other languages.

Indexing in other domains

The desire for a clean mapping between the ordinals and the cardinals is, I believe, one of the key driving factors for proponents of indexing from one schemes. For them, it is confusing and non-intuitive that the first element of an array has index zero, and that a +1 or -1 shift must occur whenever the discussion shifts between discussing orderings within the array to discussing the array index. Indexing from one solves the issue for them because the first item is A[1] - simple!

But, to take the contrary viewpoint for a moment, there are many numbering schemes outside the domain of computers which use zero-based numbering. Measurements of lengths start at zero: when was the last time you saw a ruler which started at length one? Measurements of a person's age start implicitly at zero: a child's "first birthday" is in fact not their birth-day, it is their first anniversary, so that counting their age up until that moment would begin at 0 years 0 days and run up to 0 years 364 days then tick over to 1 year 0 days.

Proponents of one-based numbering counter this argument by saying that array indices are not continuous or real numbers, and we're not generally talking about measurement when we use arrays. Instead, we're counting discrete objects, and just as we would number a list starting from item 1, so too should we number an array from 1.

Sometimes, supporters of one-based schemes confuse the discussion by pointing to cases where measurements do start from one. For example the Gregorian calendar starts at 1 A.D., so the first 1000 years were numbered from 1 to 1000 inclusive, and the second millenium was numbered from 1001 to 2000 inclusive, and the third millenium (the 21st century) started in the year 2001. But look at the interesting confusions that result in this labelling of time. Many people mistakenly thought the year 2000 was the start of the third millenium, because "all the numbers changed". Here too we have the +1 -1 confusion between ordinals and cardinals... the 20th century began in 1901 and ended in 2000, and so 20th meant (for the most part) 19xx. Likewise the 21st century is prefixed 20xx. Ordinals just don't play nicely when mixed with cardinals.

These arguments seem to confuse more than enlighten because for every example there is a counter-example. The general rule, however, seems to be that engineers and people who measure things for a living require zero-based measurement systems. While most other people who simply count things want one-based schemes. Zero-based schemes are good for talking about distance, so the first inch on a ruler goes from 0 to 1. One-based schemes are good for talking about objects, particularly in ordered sequences. "The first thing on my list is to get her phone number, the second thing is to look up the movie times, the third thing is to call her." Confusion reigns when you want to do both, such as happens with time; we wish to both count time and also subtract times. Thus, seconds and minutes run from 0 to 59, while hours run from 1 to 12 and days within a month run from 1 to 31 but years can run from 0 or 1 depending whether we're talking of a person's age (measurement) or the Gregorian calendar (index). Conventions, though it'd be nice to ignore them, force themselves into this debate.

To cut through this confusion about ordinals and cardinals we must be prepared to consider the merits of both numbering schemes and weigh the gains and losses from choosing any one scheme.

Flexible Indexing

A particular scheme which hasn't been discussed here is that employed in the language Pascal, in which any array can have explicitly defined starting and ending points. Hence a programmer can define array[1..10] of int or array[-100..100] of char. This flexible scheme gives the choice to the programmer, and side-steps the whole religious debate. But there is a cost, which is that each iteration must be independently crafted to suit the array indexing scheme, and a statement like A[1] no longer has a unique meaning in such a language (whether these are real problems is a matter for conjecture). This flexible scheme does allow a programmer the choice to get the best of both worlds.

Another somewhat hacky solution is to use zero-based arrays and simply ignore A[0] if you'd rather use a one-based array (simply make the array one element larger so that A[1] up to A[n] are all valid). I've certainly used this approach in calendar programs to avoid +1 or -1 terms in some calculations. Sure, it wastes a small amount of memory for those unused A[0] cells, but if it makes the program more maintainable and understandable, and is well documented, it can be strategic. Note, a one-based indexing scheme doesn't let you do this trick in reverse, only a zero-based scheme facilitates this trick.

Conclusion

However, the thing which tips the balance in my mind is historical convention and interoperability issues. There are so many existing applications for zero-based indexing, and many existing languages which use it, that interoperability and learnability are biased in favour of that camp in my opinion. It is disheartening that the result of an intellectual discussion should be settled with "that's the way we've always done things" but in this case it seems a justified conclusion.

That being said, I think for certain specialised or high-level languages, I hope there is a place for one-based indexing, because I feel it has been an inadequately explored solution to the job of addressing elements of an array. I hope this essay has shown that there are some inherently good things about these schemes, and I also hope that future discussions of the issue won't unnecessarily conflate indexing from one with including end-points in loops or slices; although related, the two are not the same issue.

Loki Patrick