5 ms·
Lots of people have a strong opinion on this: Ones that say that 0-based indexing is the only logical way of things, and ones that don't see what the fuss is ab
by 0-_-0 7y ago
Lots of people have a strong opinion on this: Ones that say that 0-based indexing is the only logical way of things, and ones that don't see what the fuss is about and prefer 1 because that's how we count objects. I suspect the people in the first category did some low level programming that needed to do arithmetic on indices. For example, let's say you want to take a string "abc" and repeat it until the length is 10, getting "abcabcabca". Assuming some Python-like language you would start with:
a = "abc"
b = [" "]*10
With 0-based indexing you would do:
for i in range(0,10):
b[i]=a[i%3]
In a 1-based language that becomes:
for i in range(1,11):
b[i]=a[(i-1)%3+1]
So you need to shift the index twice. This is because modulo arithmetic needs 0 to form a ring. As a result, in situations where the difference between 0 and 1 based indexing makes a difference it's ususally 0-based indexing that leads to simpler code.
- kragen 7y agoDijkstra makes, I think, a stronger argument, particularly given that in languages like C, (-2) % 3 == -2 rather than 1 as it should.
- 0-_-0 7y agoThat's likely there to make modulo power-of-two operations faster by turning them into a single AND operation. Otherwise it doesn't make sense to me.
- kragen 7y agoThat's not why, no. Why don't you implement signed integer division (with shifts, masks, and adds/subtracts) and see what you come out with?
- 0-_-0 7y agoAccording to wahern's quote above it was to "avoid incurring overhead in run-time code to check for special case", like the ability to accelerate mod power-of-two by convertig to AND.
- Dylan16807 7y agoYou get a positive number if you use AND.
- 0-_-0 7y agoYou don't mask the sign bit...
- Dylan16807 7y agoIn two's complement? You'd need to add extra masks and shifts to replicate the sign bit. It puts you in much more complex territory than throwing an AND at it.
- wnoise 7y agoThis used to be unspecified behavior. C99 then codified this wrong behavior. Assume positive b for a moment. We want a * (a/b) + (a%b) = a. If a%b is to always be within [0..b), then a/b has to round toward -infinity. C99 instead chose round towards 0.
- kragen 7y agoThat's right. Why do you suppose they chose that behavior to standardize, rather than Python's? Conceivably it's because nobody on the C99 standards committee had enough technical expertise to make the argument you're making, but can you think of another explanation? Because the prior probability on that one is pretty low.
- wahern 7y ago> In C89, division of integers involving negative operands could round upward or downward in an implementation-defined manner; the intent was to avoid incurring overhead in run-time code to check for special cases and enforce specific behavior. In Fortran, however, the result will always truncate toward zero, and the overhead seems to be acceptable to the numeric programming community. Therefore, C99 now requires similar behavior, which should facilitate porting of code from Fortran to C. Source: C99 Rationale v5.10 sec. 6.5.5p10 (http://www.open-std.org/jtc1/sc22/wg14/www/C99RationaleV5.10.pdf http://www.open-std.org/jtc1/sc22/wg14/www/C99RationaleV5.10...)
- bloak 7y agoThanks for that. Now can anyone tell us where the Fortran behaviour came from? (Haskell has both kinds of integer division, called div and quot, which is nice.)
- derriz 7y agoDon't you mean we want "(a/b) + (a%b) = a"?
- kragen 7y ago
- Certhas 7y agoJulia actually just includes a dedicated function for this case (mod1), and that covers the vast majority of places where 0 base is easier. In my cases of numerical code 1 based indexing causes fewer ±1 than 0 based indexing. (Nitpick: In modulo arithmetic 0 = N so having the index run from 1 to N is a ring just as well. The problem is the conventional representation of the equivalence class -N,0,N,2N,3N… in the numbers being 0 (which arises from arithmetics definition of modulo))
- a9h74j 7y agoIn terms of your remark that in counting we start at 1. I'd argue that we start at 0 and repeatedly add one for each item counted. Likewise, in multiplying we start at 1, particularly in this sense: For n>0, n^0 = 1. Multiply 1 by something zero times leaves 1.
- 0-_-0 7y agoThat's a good point!
- contravariant 7y agoIn pretty much any language other than python you'd have to be careful for the case that i might become negative anyway. And in python you could just go: import itertools as it a = ''.join(it.islice(it.cycle("abc"),10)) Also you don't need 0 to form a ring. Modulo arithmetic forms a ring no matter which representatives you pick. Languages just tend to implement one that includes 0 because it's more convenient.
- thomasahle 7y agoAnother example is combining to indices like row*height+column, but which works nice in 0 indexing but is weird and error prone with 1 indexing.
- ulucs 7y agoOr you could just use `cycle >> take 10` and avoid all this meaningless discussion.