5 ms·

I've implement a few string search algorithms and translating between 1- and 0- based offset functions was the source of a huge number of bugs, as you might exp

I've implement a few string search algorithms and translating between 1- and 0- based offset functions was the source of a huge number of bugs, as you might expect. For some reason a lot of sources present the algorithms as 1-based.

ivanbakel 7y ago
>For some reason a lot of sources present the algorithms as 1-based. Because that's a natural mathematical model. "the n-th element" being at position n is handy and natural. What's nuts is that array indexing based on pointer offsets has made its way into nearly all high-level languages.
- ahelwer 7y ago
  Yeah that makes sense. I recall 0-based actually making most index calculations easier though, as in fewer +1/-1 offsets.
- derefr 7y ago
  One might say that computing doesn't care about ordinal numbers, only cardinal numbers. On an infinite tape, there is no "first byte", only "a byte placed where the tape already was when you started" (i.e. at offset=0.) Similarly, there is no "first byte" of a random-access memory, because the ordering of memory is not guaranteed (i.e. some memories have bit-planes, some memories have banks, some memories are big/little-endian, etc.) The only thing you can say about a memory (and thereby about a RAM-word machine, or about an array) is what exists at address 0 of it, at address 1 of it, etc. It would be incorrect to describe address 0 as "the first byte" of memory, as this would impose a canonical iteration order.
  - DeathArrow 7y ago
    >On an infinite tape, there is no "first byte", only "a byte placed where the tape already was when you started" (i.e. at offset=0.) Maybe, but human brain likes things starting at 1.
- a1369209993 7y ago
  > Because that's a natural mathematical model. No it's not; it's a artifact of humans numbering items based on "total I have, including this one" rather than the more sensible but contrary to a implementation detail of human neuropsychology "number of items preceeding this one". > "the n-th element" being at position n is handy and natural. Yes, starting with the 0th element at position 0.
04091948 7y ago
maybe it's because of Pascal. I remember even Cormen used to have pascal style pseudo-code.

ivanbakel 7y ago

>For some reason a lot of sources present the algorithms as 1-based. Because that's a natural mathematical model. "the n-th element" being at position n is handy and natural. What's nuts is that array indexing based on pointer offsets has made its way into nearly all high-level languages.

ahelwer 7y ago
Yeah that makes sense. I recall 0-based actually making most index calculations easier though, as in fewer +1/-1 offsets.
derefr 7y ago
One might say that computing doesn't care about ordinal numbers, only cardinal numbers. On an infinite tape, there is no "first byte", only "a byte placed where the tape already was when you started" (i.e. at offset=0.) Similarly, there is no "first byte" of a random-access memory, because the ordering of memory is not guaranteed (i.e. some memories have bit-planes, some memories have banks, some memories are big/little-endian, etc.) The only thing you can say about a memory (and thereby about a RAM-word machine, or about an array) is what exists at address 0 of it, at address 1 of it, etc. It would be incorrect to describe address 0 as "the first byte" of memory, as this would impose a canonical iteration order.
- DeathArrow 7y ago
  >On an infinite tape, there is no "first byte", only "a byte placed where the tape already was when you started" (i.e. at offset=0.) Maybe, but human brain likes things starting at 1.
a1369209993 7y ago
> Because that's a natural mathematical model. No it's not; it's a artifact of humans numbering items based on "total I have, including this one" rather than the more sensible but contrary to a implementation detail of human neuropsychology "number of items preceeding this one". > "the n-th element" being at position n is handy and natural. Yes, starting with the 0th element at position 0.

04091948 7y ago

maybe it's because of Pascal. I remember even Cormen used to have pascal style pseudo-code.