Matrix Multiply

Naive algorithm: triple nested loop, O(n³). For each element C[i,j], compute the dot product of row i of A and column j of B.

Cilia

func multiply(Matrix A, B) -> Matrix {
    Int m = A.rows()
    Int n = A.columns()
    Int o = B.rows()
    Int p = B.columns()

    assert(n == o, "A.columns() must equal B.rows() for matrix multiplication")

    Matrix C(m, p);

    for i in 0..<m {
        for k in 0..<n {
            for j in 0..<p {
                C[i, j] += A[i, k] * B[k, j]
            }
        }
    }

    return C
}

C++

#include <cassert>

auto multiply(const Matrix& A, const Matrix& B) -> Matrix {
    int m = A.rows();
    int n = A.columns();
    int o = B.rows();
    int p = B.columns();

    assert(n == o && "A.columns() must equal B.rows() for matrix multiplication");

    Matrix C(m, p);

    for (int i = 0; i < m; ++i) {
        for (int k = 0; k < n; ++k) {
            for (int j = 0; j < p; ++j) {
                C[i, j] += A[i, k] * B[k, j];
            }
        }
    }

    return C;
}