Do you know why the C++ array is indexed from zero and not one?
Suppose we have an Array A where the size of data type is W (2 or 4 bytes for int depends on the compiler) then the logical address of element at ith index is calculated as:-
Logical Address(A[i]) = Base Address(L0) + ( i - 1 ) * W
in this formulae, we have to perform 3 arithmetic operations +, -, and * but when we take the zero as the starting index then the formula becomes:-
Logical Address(A[i]) = Base Address(L0) + ( i ) * W
which have only 2 arithmetic operations + and *
so if the size of an array is n then the formula with starting index one will execute slower due to one extra operation overhead. thus, affecting the time taken by the program for larger values of n.
The above discussion was for the 1-D array but when it comes to 2-D or multidimensional arrays the case is even worse, suppose i and j are respectively the ith row and jth column in a 2-D matrix then the address when considered 0 as the first index is given as:-
Logical Address(A[i][j]) = Base Address(L0) + ( i* n +j ) * W
having 4 arithmetic operations, but when taken ONE as the starting index we have
Logical Address(A[i][j]) = Base Address(L0) + ( (i-1)* n +(j-1)) * W
this is having 6 arithmetic operations so it keeps on increasing as the dimension of the array increases too.
And hence, we use ZERO as the Starting index rather than ONE.
Top comments (10)
sizeof (int) need not be 2 or 4, just >= 1.
Other than that, the insight here is that zero is the additive identity, just as one is the multiplicative identity, which makes these good choices for origins, as they require no compensation. :)
Lua is one indexed, bit of useless trivia for you.
you can refer to this lua-users.org/wiki/CountingFromOne....
That link is great :)
I do love Lua very much wish it was more popular in webdev π
Could someone please dumb down this explanation for me? :(
I'm having a tough time grasping it
I will try to explain how I have understood it - please correct me if I'm wrong.
The way I picture arrays in general is as follows:
An array is a certain block in memory. You can think of it as a drawer unit. Each drawer (element in your array) in that unit has a certain height (your data size W).
Now the Base Address(L0) refers to the handle of your first drawer.
If you use the first formula (Logical Address(A[i]) = Base Address(L0) + ( i - 1 ) * W)
You would essentially say the following as an example: I want the 3rd drawer handle, so I look at my first handle (L0) and add the height (W) of 2 (i - 1) drawers to it => then I reach the third handle.
Now instead of refering to the 3rd drawer as A[3], we can use zero-based numbering and refer to it as A[2]. By doing so, we have eliminated the need for the substraction in (i - 1), thus saving us calculations.
I hope that explanation makes sense.
Thank you very much :D
Moving from a position to an offset is easier if the first position is already at an offset of zero. :)
Imagine all the CPU clock cycles that have been saved thanks to this nifty trick! Thanks for sharing. I learned something new today. π