Возведение квадратного массива в степень N в C

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])
• есть дополнительный аргумент * матрица out должна быть установлена ​​в матрицу единиц, если N == 0.
• матрица out должна получить копию R, если N == 1.
• , в противном случае out начинается с R ² , номаловероятно, что вы можете передать ту же матрицу, что и для ввода и вывода, на 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;
}