Math trickery for 1D & 2D arrays

Once upon a time, there was a language that didn’t have 2 dimensional arrays. This greatly upset the programmer. Fortunately, the programmer was swift in the art of arithmetic and overcame this obstacle easily.

Lets say for example, we only have access to a 1 dimensional array data structure and it has 50 elements in it.

Lets break this array up into 10 rows and 5 columns to make a grid. So how do we get access to a position say data[4][3]?
There are two things I’m going to teach you now:
1) Retrieve the column & row numbers from a linear index counter.
2) Retrieve the index from a row & column numbers.

Before I continue, i want you to notice that the row and column numbers are zero based. So they start at zero, not one.

Lets do #1 first:

Here, “col” and “row” will contain the column and row number for index #6 in the linear array.

Here, we are taking advantage of dividing up a long linear array up into sections (rows), hence the division operator. So we have 10 rows / sections. We get a particular one by using the formula index / numRows.

If we were to loop through the linear array (0-50), moding (%) each number with some maximum number (say 5), we would obtain a series of numbers that went like the following: 0,1,2,3,4,0,1,2,3,4,0,1,2,3,4… (index % numCols). Notice how it repeats between 0 & numCols – 1? Where numCols is 5 in this case. Where index goes through 0 – 50, our column repeats from 0 – 4. Nifty huh? This works because the mod operator returns the remainder of a division (4 % 2 = 0 because there is no remainder).

As a side note: col could also be written like such: col = index – numRows * row. See below for why.

Now lets do #2:

This is a pretty simple idea. We basically took the formula from #1 above and rearranged it. (row = index/numRows). Here we are also using col as an offset into the row. So we just add it on.

If you take index = numOfRows * row + col, you can solve for col, since we already solved for row. Hence the formula in #1’s side note: col = index – numRows * row

Example program:

The output for this program is:

Leave a Reply

You must be logged in to post a comment.