Multidimensional arrays and address calculation

Why it exists

A table of numbers, a matrix, an image: data with rows and columns is everywhere, and C offers int m[3][4] for it. But memory has no rows and no columns. It is a single line of numbered bytes. The compiler therefore has to flatten the table into that line, and every access m[i][j] becomes an arithmetic formula on the starting address. GATE asks for exactly this formula, in many dressings: different bounds, row-major or column-major, three dimensions, or only half of a matrix stored.

Prerequisites

Precise definitions

• Two-dimensional array. In C, int m[3][4] is an array of 3 elements, each of which is an array of 4 ints. There are $3 \times 4 = 12$ ints in one contiguous block. There is no separate "row structure": m[i] is simply the $i$-th inner array.
• Row-major order. The elements are stored row after row: the whole of row 0, then row 1, then row 2. C always uses row-major order. Consecutive elements of one row are adjacent; consecutive elements of one column are a whole row apart.
• Column-major order. Column after column. Fortran and MATLAB use it. GATE questions state which one applies when they leave C.
• Address formulas. Let the base address be $B$ and the element size $w$.

For an array with $R$ rows and $C$ columns, 0-based indices, row-major:

$\text{address}(A[i][j]) = B + (i \cdot C + j) \cdot w.$

For general bounds, rows $L_1 \ldots U_1$ and columns $L_2 \ldots U_2$, let $n_1 = U_1 - L_1 + 1$ be the number of rows and $n_2 = U_2 - L_2 + 1$ the number of columns:

$\text{row-major: } B + \big((i - L_1) \cdot n_2 + (j - L_2)\big) \cdot w, \qquad \text{column-major: } B + \big((j - L_2) \cdot n_1 + (i - L_1)\big) \cdot w.$

For three dimensions a[D1][D2][D3] (0-based, row-major):

$\text{address}(a[i][j][k]) = B + \big((i \cdot D_2 + j) \cdot D_3 + k\big) \cdot w.$

The last index varies fastest. The pattern: the number you multiply by is always the product of the sizes of the dimensions to the right.

• What the types are. For int m[3][4]:

Rows: sizeof m / sizeof m[0] $= 3$. Columns: sizeof m[0] / sizeof m[0][0] $= 4$.

• Pointer to an array versus array of pointers. int (*p)[4] is one pointer to an array of 4 ints (this is what m decays to). int *q[4] is an array of 4 pointers to int. The parentheses decide. with 4-byte int and 8-byte pointers, sizeof *p is 16 and sizeof q is 32.
• Declaring and passing. Every dimension except the first must be given, because the compiler needs the row length for the formula above. void f(int a[][4], int rows) is the same as void f(int (*a)[4], int rows). A parameter int a[][] is an error.
• Initialisation. Braces can be nested to give each row. Missing values are zero. If the braces are flattened, values fill the array in row-major order, and only the first dimension may be left out: int b[][3] = {1, 2, 3, 4, 5}; makes 2 rows, {1, 2, 3} and {4, 5, 0}.

How it works

The run below is real. It declares m[3][4] but does not initialise it, so the cells show ?. Look at the addresses: they climb by 4 along a row and then keep climbing into the next row with no gap. The grid you see is only a way of drawing 12 consecutive ints. The last two steps take a pointer to row 2 (m[2], which begins $2 \cdot 4 = 8$ cells after the start) and move one cell along it: m[2][1] sits $2 \cdot 4 + 1 = 9$ cells after the start.

Triangular and tridiagonal matrices

A symmetric, triangular or tridiagonal $n \times n$ matrix has many entries that are known to be 0 (or repeated). Instead of $n^2$ cells, only the useful entries are stored, row by row, in a 1-D array, and an index formula converts $(i, j)$ to a position.

Lower triangular (entries with $j \le i$), stored row-wise, 0-based. Rows 0, 1, ..., $i-1$ hold $1 + 2 + \cdots + i = i(i+1)/2$ entries before row $i$, and $(i, j)$ is the $(j+1)$-th entry in its row:

$\text{index}(i, j) = \frac{i(i+1)}{2} + j, \qquad \text{total} = \frac{n(n+1)}{2}.$

With 1-based indices and 1-based positions, the formula is $\frac{i(i-1)}{2} + j$, so the address is $B + \big(\frac{i(i-1)}{2} + j - 1\big) \cdot w$.

Upper triangular (entries with $j \ge i$), stored row-wise, 0-based. Row $r$ holds $n - r$ entries, so before row $i$ there are $\sum_{r<i}(n - r) = i \cdot n - \frac{i(i-1)}{2}$ entries:

$\text{index}(i, j) = i \cdot n - \frac{i(i-1)}{2} + (j - i).$

Tridiagonal (entries with $|i - j| \le 1$), stored row-wise, 0-based. Row 0 has 2 entries, every other row 3 (except the last, which has 2). The formula collapses to

$\text{index}(i, j) = 2i + j, \qquad \text{total} = 3n - 2.$

The lower-triangular and tridiagonal formulas are checked by programs in the worked examples (the program lists the entries in storage order and compares the position it counts with the formula). The upper-triangular, general-bounds and column-major formulas were checked by a one-off script during the build.

Worked examples

#include <stdio.h>
 
int main(void) {
    int m[3][4];
    printf("%zu %zu %zu %zu %zu %td\n", sizeof m, sizeof m[0], sizeof m[0][0],
           sizeof m / sizeof m[0], sizeof m[0] / sizeof m[0][0],
           (char *)&m[1][2] - (char *)&m[0][0]);
    return 0;
}

48 16 4 3 4 24

#include <stdio.h>
 
int main(void) {
    int m[3][4];
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 4; j++) m[i][j] = i * 4 + j;
    int (*pa)[4] = m;
    printf("%d %td %d %zu %zu\n", *(*(m + 2) + 1), (char *)(pa + 1) - (char *)pa,
           pa[1][3], sizeof *pa, sizeof pa);
    return 0;
}

9 16 7 16 8

#include <stdio.h>
 
int main(void) {
    int a[2][3] = {{1}, {4, 5}};
    int b[][3] = {1, 2, 3, 4, 5};
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 3; j++) printf("%d ", a[i][j]);
        printf("| ");
    }
    printf("\n%zu:", sizeof b / sizeof b[0]);
    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 3; j++) printf(" %d", b[i][j]);
    printf("\n");
    return 0;
}

1 0 0 | 4 5 0 |
2: 1 2 3 4 5 0

#include <stdio.h>
 
int main(void) {
    int a[2][3][4];
    printf("%td %zu\n", (char *)&a[1][2][3] - (char *)&a[0][0][0], sizeof a);
    return 0;
}

92 96

#include <stdio.h>
 
int main(void) {
    int n = 5, idx = 0, found = -1;
    for (int i = 0; i < n; i++)
        for (int j = 0; j <= i; j++) {
            if (i == 3 && j == 2) found = idx;
            idx++;
        }
    printf("%d %d %d\n", found, 3 * 4 / 2 + 2, idx);
    return 0;
}

8 8 15

#include <stdio.h>
 
int main(void) {
    int n = 6, idx = 0, ok = 1;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (j >= i - 1 && j <= i + 1) {
                if (idx != 2 * i + j) ok = 0;
                idx++;
            }
    printf("%d %d %d\n", ok, idx, 3 * n - 2);
    return 0;
}

1 16 16

#include <stdio.h>
 
int sum(int a[][4], int rows) {
    int s = 0;
    printf("%zu %zu ", sizeof a, sizeof a[0]);
    for (int i = 0; i < rows; i++)
        for (int j = 0; j < 4; j++) s += a[i][j];
    return s;
}
 
int main(void) {
    int m[3][4];
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 4; j++) m[i][j] = i * 4 + j;
    printf("%d\n", sum(m, 3));
    return 0;
}

8 16 66

Cheat box

Traps and GATE patterns

Connections

The row-major formula is the one-dimensional array formula applied twice. The type rules rely on pointer arithmetic and on the way an array name decays. The reason loops that run along rows are faster than loops that run down columns is the cache, which is the subject of cache mapping: in row-major order the elements of a row are neighbours in memory. Passing a 2-D array to a function is a special case of parameter passing.

PYQs

Consider the following ANSI C program.
#include <stdio.h>
int main() {
    int arr[4][5];
    int i, j;
    for (i = 0; i < 4; i++) {
        for (j = 0; j < 5; j++) {
            arr[i][j] = 10 * i + j;
        }
    }
    printf("%d", *(arr[1] + 9));
    return 0;
}

What is the output of the above program?

Consider the following C program.
#include
int main () {
int a [4] [5] = {{1, 2, 3, 4, 5},{6, 7, 8, 9, 10},{11, 12,
13, 14, 15}, {16, 17, 18, 19, 20}};
printf ("%d\n", *(* (a+**a+2) +3));
return (0);
}

The output of the program is _______.

What is the output of the following C code? Assume
that the address of x is 2000 (in decimal) and an integer
requires four bytes of memory.
#include <stdio.h>
int main()
{
unsigned int x[4][3] = {{1, 2, 3}, {4, 5, 6},
{7, 8, 9}, {10, 11, 12}};
printf("%u, %u, %u", x+3, *(x+3), *(x+2)+3);
}

For a C program accessing X[i][j][k], the following
intermediate code is generated by a compiler. Assume
that the size of an integer is 32 bits and the size of a
character is 8 bits.

t0 = i * 1024

t1 = j * 32

t2 = k * 4

t3 = t1 + t0

COMPILER DESIGN

t4 = t3 + t2

t5 = x[t4]

Which one of the following statements about the
source code for the C program is CORRECT?

Consider the following two C code segments. Y
and X are one and two dimensional arrays of size n
and n×n respectively, where 2 ≤n≤10. Assume that
in both code segments, elements of Y are initialized
to 0 and each element X[i][j] of array X is
initialized to i+j. Further assume that when stored
in main memory all elements of X are in same main
memory page frame.

Code segment 1:
// initialize elements of Y to 0
// initialize elements of X[i][j] of X to i+j
for (i=0; i<n; i++)
Y[i] += X[0][i];
Code segment 2:
// initialize elements of Y to 0
// initialize elements of X[i][j] of X to i+j
for (i=0; i<n; i++)
Y[i] += X[i][0];
Which of the following statements is/are correct?

S1: Final contents of array Y will be same in both
code segments
S2: Elements of array X accessed inside the for loop
shown in code segment 1 are contiguous in main
memory
S3: Elements of array X accessed inside the for loop
shown in code segment 2 are contiguous in main
memory

Self-check

#include <stdio.h>
 
int main(void) {
    int m[2][3] = {{1, 2, 3}, {4, 5, 6}};
    printf("%d %d\n", *(*(m + 1) + 1), **m + *(*m + 2));
    return 0;
}

5 4

Revision card

References