在C中将正方形阵列提升到N的幂

问题描述 投票:1回答:1

我正在编写一个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循环的情况下编写它。

c arrays pointers
1个回答
3
投票

您的代码中存在多个问题:

  • arrMult(int M, int M, int R[M][M], int X[M][M], int out[M][M])有一个额外的论点
  • 如果outN == 0矩阵应设置为单位矩阵。
  • 如果outR矩阵应该收到N == 1的副本。
  • 否则outR2开始,但你不太可能将输入和输出相同的矩阵传递给arrMult。您应该使用临时矩阵来存储结果,并将其复制到out内或arrMult内或每次矩阵乘法后。
  • 有一种更有效的算法来计算log 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;
}
© www.soinside.com 2019 - 2024. All rights reserved.