Session 7

This session produces a working C program: it reads two matrices, checks that they can be multiplied, multiplies them using pointer arithmetic only, and prints the product. It is the first coding session in MCS-217 and the program you write here is the thing you test in Session 8. Write it cleanly, because every test case in the next session refers to a function in this file by name. The manual places this under Testing for a reason: a program with clear functions and validation is a program you can test.

Objectives

• Store a two-dimensional matrix in one contiguous block and reach any element with pointer arithmetic
• Allocate matrices at run time with malloc and release them with free
• Validate dimensions before reading elements, so the program never multiplies incompatible matrices
• Split the program into small functions (read_matrix, multiply, print_matrix, free_matrix) that Session 8 can test one at a time
• Compile with gcc -Wall -Wextra and get zero warnings

Problem Statement

Write a program in ‘C’ language for the multiplication of two matrices using pointers.

Concept

Row-major layout

C stores a two-dimensional array row after row in memory. A 2 x 3 matrix occupies six consecutive integers: row 0 first, then row 1.

 index:   0    1    2    3    4    5
 value: a00  a01  a02  a10  a11  a12
        |--- row 0 ---| |--- row 1 ---|

If m points to the first element and the matrix has cols columns, element (i, j) is at offset i * cols + j. So *(m + i * cols + j) is the same value as m[i][j] would be in a static array. The program never writes m[i][j]; it only moves pointers.

Why one block and not an array of row pointers

Two layouts are common: one malloc of rows * cols ints, or an array of rows pointers each pointing to its own malloc. The single block is simpler to allocate, simpler to free (one call), and matches how the compiler lays out a static int a[2][3]. It also makes the inner loop of multiplication a plain pointer walk, which is the point of this session.

Walking a column with a stride

The product C = A x B needs, for each C(i, j), the dot product of row i of A with column j of B. Row i of A is contiguous, so a pointer that starts at a + i * c1 and increments by 1 walks it. Column j of B is not contiguous: consecutive elements are c2 apart. A pointer that starts at b + j and increments by c2 walks down the column. That stride is the only non-obvious piece of pointer arithmetic in the program.

Why the dimension check comes first

A (r1 x c1) times B (r2 x c2) is defined only when c1 == r2. The result is r1 x c2. If you skip the check, the pointer walk reads past the end of the block and the output is garbage or a crash. The program therefore reads the four dimensions, checks them, and only then asks for elements. Each dimension is also limited to 1 to 100, which rules out zero, negative, and absurdly large sizes.

malloc and free in pairs

Every malloc needs exactly one free on every path out of main, including the error paths. The program frees a when reading b fails, and frees a and b when allocating c fails. free_matrix is a thin wrapper so the test cases in Session 8 have a named function to call.

Program

/*
 * matrix_multiply.c
 * MCS-217 Session 7: multiplication of two matrices using pointers.
 *
 * Each matrix is stored as one contiguous block of rows * cols ints
 * (row-major order). Element (i, j) lives at *(m + i * cols + j).
 * No arr[i][j] indexing is used anywhere; every access goes through
 * pointer arithmetic.
 *
 * Build: gcc -Wall -Wextra -o matrix_multiply matrix_multiply.c
 */
#include <stdio.h>
#include <stdlib.h>

#define MAX_DIM 100

/* Read one positive dimension. Returns 0 on failure. */
static int read_dim(const char *label, int *out)
{
    printf("%s", label);
    if (scanf("%d", out) != 1) {
        printf("Error: dimension must be an integer.\n");
        return 0;
    }
    if (*out < 1 || *out > MAX_DIM) {
        printf("Error: dimension must be between 1 and %d.\n", MAX_DIM);
        return 0;
    }
    return 1;
}

/* Allocate rows * cols ints and fill them from stdin, row by row.
   Returns NULL if allocation or input fails. */
int *read_matrix(const char *name, int rows, int cols)
{
    int *m = malloc((size_t)rows * (size_t)cols * sizeof(int));
    int *p;
    int i, j;

    if (m == NULL) {
        printf("Error: out of memory.\n");
        return NULL;
    }
    printf("Enter %d x %d elements of matrix %s, row by row:\n", rows, cols, name);
    p = m;
    for (i = 0; i < rows; i++) {
        for (j = 0; j < cols; j++) {
            if (scanf("%d", p) != 1) {
                printf("Error: element (%d,%d) is not an integer.\n", i + 1, j + 1);
                free(m);
                return NULL;
            }
            p++;                       /* next element in row-major order */
        }
    }
    return m;
}

/* C = A x B where A is r1 x c1 and B is c1 x c2. C must hold r1 * c2 ints.
   Only pointer arithmetic is used to walk the three matrices. */
void multiply(const int *a, const int *b, int *c, int r1, int c1, int c2)
{
    int i, j, k;
    const int *arow;   /* start of row i of A */
    const int *bp;     /* walks down column j of B */
    int *cp = c;       /* walks C in row-major order */
    long sum;

    for (i = 0; i < r1; i++) {
        arow = a + i * c1;
        for (j = 0; j < c2; j++) {
            sum = 0;
            bp = b + j;                        /* B(0, j) */
            for (k = 0; k < c1; k++) {
                sum += (long)*(arow + k) * *bp; /* A(i,k) * B(k,j) */
                bp += c2;                       /* down one row in B */
            }
            *cp = (int)sum;
            cp++;
        }
    }
}

/* Print a rows x cols matrix, one row per line. */
void print_matrix(const char *title, const int *m, int rows, int cols)
{
    const int *p = m;
    int i, j;

    printf("%s (%d x %d):\n", title, rows, cols);
    for (i = 0; i < rows; i++) {
        for (j = 0; j < cols; j++) {
            printf("%6d", *p);
            p++;
        }
        printf("\n");
    }
}

/* Release a matrix. Safe to call with NULL. */
void free_matrix(int *m)
{
    free(m);
}

int main(void)
{
    int r1, c1, r2, c2;
    int *a = NULL, *b = NULL, *c = NULL;

    if (!read_dim("Rows of A: ", &r1) || !read_dim("Columns of A: ", &c1) ||
        !read_dim("Rows of B: ", &r2) || !read_dim("Columns of B: ", &c2))
        return 1;

    if (c1 != r2) {
        printf("Error: columns of A (%d) must equal rows of B (%d). "
               "Multiplication not possible.\n", c1, r2);
        return 1;
    }

    a = read_matrix("A", r1, c1);
    if (a == NULL)
        return 1;
    b = read_matrix("B", r2, c2);
    if (b == NULL) {
        free_matrix(a);
        return 1;
    }
    c = malloc((size_t)r1 * (size_t)c2 * sizeof(int));
    if (c == NULL) {
        printf("Error: out of memory.\n");
        free_matrix(a);
        free_matrix(b);
        return 1;
    }

    multiply(a, b, c, r1, c1, c2);

    print_matrix("Matrix A", a, r1, c1);
    print_matrix("Matrix B", b, r2, c2);
    print_matrix("Product A x B", c, r1, c2);

    free_matrix(a);
    free_matrix(b);
    free_matrix(c);
    return 0;
}

Build

gcc -Wall -Wextra -o matrix_multiply matrix_multiply.c
./matrix_multiply

Sample Output

Input: A is 2 x 3, B is 3 x 2. Elements typed row by row.

Rows of A: 2
Columns of A: 3
Rows of B: 3
Columns of B: 2
Enter 2 x 3 elements of matrix A, row by row:
1 2 3
4 5 6
Enter 3 x 2 elements of matrix B, row by row:
7 8
9 10
11 12
Matrix A (2 x 3):
     1     2     3
     4     5     6
Matrix B (3 x 2):
     7     8
     9    10
    11    12
Product A x B (2 x 2):
    58    64
   139   154

Check by hand: C(0,0) = 1*7 + 2*9 + 3*11 = 58, C(1,1) = 4*8 + 5*10 + 6*12 = 154.

Incompatible dimensions (A is 2 x 3, B is 2 x 2):

Rows of A: 2
Columns of A: 3
Rows of B: 2
Columns of B: 2
Error: columns of A (3) must equal rows of B (2). Multiplication not possible.

Zero size:

Rows of A: 0
Error: dimension must be between 1 and 100.

Explanation of the key lines

Complexity

Viva Questions

• Q: Why is *(m + i * cols + j) equal to m[i][j]? A: Because C stores rows consecutively, so row i starts i * cols elements after the base pointer and column j is j more.
• Q: Why does bp increase by c2 and not by 1? A: It walks down a column of B; consecutive elements in a column are one full row, c2 ints, apart.
• Q: What happens if c1 is not equal to r2 and you skip the check? A: The pointer walk reads beyond the allocated block: undefined behaviour, usually garbage or a crash.
• Q: Why accumulate sum in a long? A: Products of two ints can exceed the int range; a wider accumulator delays overflow. The final cast to int can still truncate for very large values.
• Q: Why is free_matrix a separate function when it just calls free? A: It names the operation so it can be tested and replaced, and it keeps main symmetrical with read_matrix.
• Q: What does scanf("%d", p) != 1 detect? A: Non-numeric input or end of input; both mean the element could not be read.
• Q: Why cast to size_t inside malloc? A: rows * cols * sizeof(int) must be computed in an unsigned type wide enough for the result; multiplying two ints first could overflow.
• Q: What is the time complexity for square n x n matrices? A: O(n cubed).

Common Mistakes

• Writing a[i][j] inside multiply and calling it a pointer program. The manual asks for pointers; use pointer arithmetic throughout.
• Reading elements before checking c1 == r2, so the user types a whole matrix and only then sees the error.
• Forgetting to free on the error paths. Every return 1 after a malloc must release what was allocated.
• Using int for rows * cols * sizeof(int), which can overflow before malloc sees it.
• Printing with %d and no width, so columns do not line up and the examiner cannot read the result.
• Leaving compiler warnings. gcc -Wall -Wextra must be clean; an unused variable or a signed/unsigned comparison is a defect you fix, not ignore.

Session Summary

• Source listing of matrix_multiply.c with the file header comment
• The build command and a note that it compiles with no warnings
• Sample run for a compatible pair (2 x 3 times 3 x 2) with the input and the full output
• Sample run showing the dimension mismatch error
• The table explaining the pointer arithmetic lines
• The complexity table