Addressing Formula of the (i,j)th Element of an m*n Matrix in Column-Major Order

In Column-Major Order, a 2D matrix is stored column by column in linear memory. This means all elements of the first column come first, then all elements of the second column, and so on. To find the exact memory position of any element, we use an addressing formula that converts its row and column into a single index.

Column-Major Order Formula

The memory address of element A[i][j] can be calculated using the following formula:

LOC(A[i][j]) = base_address + w × [m × j + i]

Where:

• base_address: Address of the first element in the array (A[0][0])
• w: Word size (number of bytes occupied by each element). This depends on the data type (e.g., 4 bytes for int on most systems)
• m: Number of rows in the array
• i: Row index (starting from 0)
• j: Column index (starting from 0)

Note: We assume a 2D array A[m][n] with m rows and n columns, stored in column-major order.

Formula Explanation

1. Column Offset (M × j): The term (m × j) calculates how many elements to skip to reach the beginning of the j-th column. Since each column contains m elements, we multiply the column index by the number of rows.
2. Row Offset (+ i): Adding the row index i moves to the specific element within that column.
3. Memory Scaling (× w): Multiplying by w converts the element count to actual bytes, accounting for the size of each element in memory.
4. Base Address (+ base_address): Finally, adding the base address gives the absolute memory location of element A[i][j].

Problem To Solve

Let’s calculate the address of element A[1][2] in a 4×3 matrix stored in column-major order.

Given:

base_address = 2000
w = 4 bytes (integer size)
m = 4 rows
i = 1 (row index)
j = 2 (column index)

Calculation

LOC(A[1][2]) = base_address + w × [m × j + i]
 = 2000 + 4 × [4 × 2 + 1]
 = 2000 + 4 × [8 + 1]
 = 2000 + 4 × 9
 = 2000 + 36
 = 2036

Thus, the memory address of element A[1][2] is 2036.