How is the formula for calculation in row/column major obtained?

Question

In my book, this formula is given for calculation of address of row major order's element $[I,J]$:

Address of $[I,J]$th element in row major order $= B + W[n(I-L_r)+ [J-L_c]]$

where B denotes base address, W denotes element size in bytes, n is the number of columns; $L_r$ is the first row number, $L_c$ is the first column number.

A similar formula is given for address in column major order.

I would like to know how this formula is obtained.

Answer 1

Row-major order stores the rows of the array one after another in memory. That is, the array

a d g j
b e h k
c f i l

is stored as

a d g j b e h k c f i l

To determine the address of an element in this list, we need to know how many elements come before it. For element $[I,J]$, this is the number of complete rows above row $I$ times the length of a row, which is $(I-L_r)\times n$, plus the number of elements before it in the current row, which is $J-L_c$.

Since the first element is at address $B$ and each element takes $W$ bytes, the addresses of the elements are $B$, $B+W$, $B+2W$, ... and, in general, if there are $k$ elements before you, your address is $B+kW$. For element $[I,J]$, we have calculated that $k=n(I-L_r)+(J-L_c)$.

For column-major, the argument is basically the same. If you understand the above, it should be easy to adapt it.

Answer 2

B is the base address where the first element residents. For simplicity, let's assume that the array indexes start at zero, so $L_r$ and $L_c$ are both zero.

So the first element $[0,0]$, we have I=0 and J=0, you get address = B +W[n(0-0)+[0-0]] = B.

In row major arrays, each element of row i is contiguous in memory, followed immediately afterwards with the elements of row i+1, etc.

So element $[0,1]$ comes W bytes after element $[0,0]$. Its address = B+W[n(0-0)+ [1-0]] = B+W. Similar for each element j in the first row, each element is W bytes past the previous one, so the Jth element is W*J bytes from the base address B. Address of element [0,j] = B+W[n(0-0)+[J-0]] = B+W*J

Each row i+1, contains n elements of W bytes, so row i+1 starts in memory nW bytes after the previous row. Element $[0,0]$ is at address B, and element $[1,0]$ is at address B+W*n = B+W[n(1-0)+[0-0]].

Combining those two concepts, you can find any element [I,J] using the formula. The first term in the enclosed sum computes where the row starts in memory relative to the start, and the second term computes where the jth element starts relative to that row.

The terms Lr and Lc just generalize things if your indexes do not start with zero. By subtracting these from the indexes, you are treating the indexes as if they did start with base zero.

Here is an example using C. Notice that we can index element in array a2D using indexes, or your formula. Both work and in fact the C compiler treats them the same.

In C, two-D arrays are stored in memory as row-major. Read this post for a good explanation. Arrays are arranged in memory such that the first row appears first, followed by the second and so on. Each row consists of COL elements, so the way to define this would be:

typedef int A2D[ROW][COL];
A2D     a2d  = {0}; // Declares 2D array a2d and inits all elements to zero

Then to access the element at row i, column j, use:

a2d[i][j]

Here is a sample C program to demonstate:

#include <stdio.h>
#define ROW 5
#define COL 10
#define Lc  0
#define Lr  0
#define W   sizeof(int)
#define n   (COL)
#define ELEMENT_ADDR(B,I,J) (*((int *)(((void *)B)+ (W)*((n)*(I-Lr)+(J-Lc)))))
typedef int A2D[ROW][COL];


int main(int argc, char** argv)
{
  A2D a2d  = {0};
  int r,c;

  /* Access element using indexes */
  a2d[1][2] = 12;

  /* Access elements using address formula */
  ELEMENT_ADDR(a2d,4,5) = 45;

  for(r=0; r<ROW; r++)
  {
    printf("Row %d: ", r);
    for(c=0; c<COL; c++)
       /* Equivalent to: printf("%2d ", a2d[r][c]); */
       printf("%2d ", ELEMENT_ADDR(a2d,r,c));
    printf("\n");
  }
}

This produces the following output:

Row 0:  0  0  0  0  0  0  0  0  0  0 
Row 1:  0  0 12  0  0  0  0  0  0  0 
Row 2:  0  0  0  0  0  0  0  0  0  0 
Row 3:  0  0  0  0  0  0  0  0  0  0 
Row 4:  0  0  0  0  0 45  0  0  0  0 

Now the best thing is to get out a piece of paper, draw out this array as it is laid out in memory assuming 4 bytes per int, and see if you can reproduce the calculations to find the addresses of some array elements.

Try it again using different size elements, and with $L_r$ and $L_c$ set to values other than zero.

I noticed that you included the label Java but I provided an answer in C.

Why?

Because Java stores Arrays as objects. Each row is an Array object with an array of n Integers. To connect up the rows, there is an Array object that contains the object references to each of the row objects.

Each row object is stored contiguously, but each row will be stored non-contiguously on the heap, so they are not contiguous and this formula will not work.

You still access an array in Java using the notation A[i][j], but the index i provides an object reference to the ith row object, and j provides an index into that Array, but your formula will not work in that case.