A two dimensional array is stored in column major form in memory if the elements are stored in the following sequence $$A[0][0] A[1][0] A[2][0]...A[n_1-1][0] ... A[0][1] A[1][1] ... A[n_1-1][1] .... A[0][n_2-1]...A[n_1-1][n_2-1]$$

The left most index varies most rapidly if we look at the looping changes.

For a particular element $A[i_1][i_2]...[i_m]$ of an $m$ dimensional array $A[n_1][n_2]...[n_m]$ if we denote $e_m$ as the number of elements stored in memory before the given element, we can see the following

$$ e_1 = i_1$$ $$ e_2 = i_1 + i_2 \times n_1$$ $$ e_3 = i_1 + i_2 \times n_1 + i_3 \times n_1 \times n_2$$

How to show that generally

$$ e_m = e_{m-1} + i_m \times \prod_{j=1}^{m-1}{n_j}$$

If we look at the two dimensional array, the number of elements stored before a particular array location can be calculated as the column number of the element we are looking for summing with the $row \times column$ number of elements. How does the above recurrence relation work?

  • $\begingroup$ Can you figure out the formula with 4 columns? Then 5 columns? Then 6 columns? Then ...? $\endgroup$ – Apass.Jack Jan 6 at 19:51
  • $\begingroup$ Why is $ e_1=,i_1$? Shouldn't it be $i-1$? @Apass.Jack $\endgroup$ – kauray Jan 6 at 20:41
  • $\begingroup$ Let us start with one dimensional then. Let $A$ be a one-dimensional array, $A[0], A[1], \cdots, A[n_1]$. How many elements are before $A[i_1]$? For example, how many elements are before $A[0]$? before $A[1]$? ... $\endgroup$ – Apass.Jack Jan 6 at 21:14
  • $\begingroup$ Oh...$i_1$ elements $\endgroup$ – kauray Jan 6 at 22:07
  • 1
    $\begingroup$ I will work it out further and write one $\endgroup$ – kauray Jan 7 at 14:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.