将方形数组提高到 C 中的 N 的幂

Question

我正在编写一个C程序来计算一个增加到N次方的方形数组。

我想将它们写在单独的函数中以保持干净。我有一个功能

arrMult(int M, int R[M][M], int X[M][M], int out[M][M])

这基本上out = R*X.为了将其提高到某个 N 次方，我编写了这个函数：

int arrNthPow(int M, int N, int R[M][M], int out[M][M])
{
    // Initialize
    arrPrint(M, M, out);
    arrMult(M, R, R, out);
    for (int i = 1; i < N - 1; i++){
        arrPrint(M, M, out);
        arrMult(M, R, out, out);
    }
    return 0;
}

但是，我意识到这并没有给我带来我期望的结果。相反，如果我这样做

arrMult(M, R, R, out1);
arrMult(M, out1, R, out2);
arrMult(M, out2, R, out3);

out3得到了我正在寻找的答案。我假设我必须以某种方式使用指针在arrMult后复制每个数组输出的值，然后再使用 arrMult 进行下一次迭代，但我不确定如何。

但是，我对指针不是很熟悉，并且不知道如何在不将值复制到temp变量并使用额外的 for 循环的情况下编写指针。

Answer 1

代码中存在多个问题：

• arrMult(int M, int M, int R[M][M], int X[M][M], int out[M][M])中还有一个额外的参数
• 如果N == 0，则应将out矩阵设置为单位矩阵。
• 如果N == 1，out矩阵应接收R的副本。
• 否则out从R ² 开始，但您不太可能将相同的矩阵作为输入和输出传递给 arrMult 。您应该使用临时矩阵来存储结果，并将其复制到arrMult内部或每次矩阵乘法之后的out。
• 有一种更有效的算法可以计算日志 N 步的功率，而不是发布的 N 步：https://en.wikipedia.org/wiki/Exponentiation_by_squaring

下面是一个简单的实现：

void arrIdentity(int M, int out[M][M]) {
    /* initialize array to identity matrix. */
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < M; j++) {
            out[i][j] = (i == j);
        }
    }
}    
void arrCopy(int M, const int mat[M][M], int out[M][M]) {
    /* copy a matrix. */
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < M; j++) {
            out[i][j] = mat[i][j];
        }
    }
}    
void arrMult(int M, const int R[M][M], const int X[M][M], int out[M][M]) {
    /* compute matrix multiplication: out = R * X. */
    int temp[M][M];
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < M; j++) {
            int sum = 0;
            for (int k = 0; k < M; k++) {
                sum += R[i][k] * X[k][j];
            }
            temp[i][j] = sum;
        }
        arrCopy(M, temp, out);
    }
}
int arrNthPow(int M, int N, const int R[M][M], int out[M][M]) {
    /* Naive matrix exponentiation */
    if (N < 0)
        return -1;
    if (N == 0) {
        arrIdentity(M, out);
        return 0;
    } else {
        arrCopy(M, R, out);
        for (int i = 1; i < N; i++) {
            arrMult(M, R, out, out);
        }
    }
    return 0;
}

以下是使用维基百科文章中解释的方法的更有效的替代方案：

int arrNthPow2(int M, int N, const int R[M][M], int out[M][M]) {
    /* Matrix exponentiation by squaring */
    int X[M][M];
    if (N < 0)
        return -1;
    if (N == 0) {
        arrIdentity(M, out);
        return 0;
    }
    if (N == 1) {
        arrCopy(M, R, out);
        return 0;
    }
    if (N == 2) {
        arrMult(M, R, R, out);
        return 0;
    }
    arrIdentity(M, out);
    arrCopy(M, R, X);
    while (N > 1) {
        if (N & 1)
            arrMult(M, X, out, out);
        arrMult(M, X, X, X);
        N >>= 1;
    }
    arrMult(M, X, out, out);
    return 0;
}