c++ - 计算矩阵的 n 次方

Question

我正在尝试优化我的代码以计算矩阵的 n 次方。

之前我只会调用 multiplySquare n 次，但那太慢了。问题是，它构建得很好，但是当我运行它时，我遇到了退出值 1 的失败。我相信我的算法是正确的，那么是什么原因造成的呢？

[编辑] 添加了递归终止条件，但我仍然遇到同样的错误。

[再次编辑] 我再次重写了递归部分，现在它似乎可以工作，但仅适用于 n 的某些输入。我将不得不更多地使用它。任何帮助，将不胜感激。

void multiplySquare(long long A[2][2], long long B[2][2]){

    long long result[2][2];
    for (int i = 0; i < 2; i++){
        for (int j = 0; j < 2; j++){
            result[i][j] = 0;
            for (int k = 0; k < 2; k++){
                result[i][j] += A[i][k] * B[k][j];
            }
        }
    }

    for (int i=0; i<2; i++){
        for (int j=0; j<2; j++){
            A[i][j] = result[i][j]; 
        }
    }
}

void power(long long A[2][2], long long B[2][2], long long n){
    if(n/2 != 0){   
        power(A, B, n/2);
    }
    if(n%2 != 0){
        multiplySquare(A, B);
    }
}

Answer 1

有效计算数字 x 的 N 次方的算法是:

如果N为零，返回1。
如果N为1，返回x。
计算 (N/2) 次方。 y = x^(N/2)
如果 N 是偶数，返回 y*y
如果 N 是奇数，返回 x*y*y

如果您将该逻辑转化为您的案例，您将需要以下内容:

// Assuming that the result is returned in B.
void power(long long A[2][2], long long B[2][2], long long n)
{
   if ( n == 0 )
   {
      makeIdentity(B);
      return;
   }

   if ( n == 1 )
   {
      assign(A, B);  // Make B same as A.
      return;
   }

   power(A, B, n/2);

   multiplySquare(B, B);
   if(n % 2 != 0)
   {
      multiplySquare(B, A);
   }
}