1

我有一个矩阵 [2,2][1,0]。我需要这个 2*2 矩阵的第 n 次乘法。当我使用简单乘法时，我可以在 O(n) 或 O(logn) 中进行。O（登录）代码：

int NUM(int n)
 {
  int F[2][2] = {{2,2},{1,0}};
  if(n == 0)
      return 0;
  power(F, n-1);
  return F[0][0];
 }

/* Optimized version of power() */
void power(int F[2][2], int n)
{
  if( n == 0 || n == 1)
  return;
  int M[2][2] = {{2,2},{1,0}};

 power(F, n/2);
  multiply(F, F);

 if( n%2 != 0 )
   multiply(F, M);
}

它在 n 的小值下工作得很好。但是一旦 n 是 10^9 或更多。int,long int 甚至 long long int 都不起作用。所以，我相信这种方法似乎没有多大帮助.

基本上我的问题是：数字变得相当大，甚至没有 long long int。那我该如何处理。

当 n 为 10^9 时，谁能建议我任何公式或算法来获得 2*2 矩阵[2,2][1,0] 的 n 次方？

谢谢

4

2 回答 2

3

这是作业，还是只是实施中的练习？如果你有选择，取模可能更方便，基本上你在每个幂或乘法之后取你的矩阵模数 M，矩阵的各个条目永远不会超过 (M - 1)^2，但显然结果会是一种模幂运算的算法，因此与您现在所拥有的不同。

因此，对于无符号长整数，您可以拥有高达 65535 左右的模数和无限指数。取矩阵取模某个数字的过程很简单：取每个条目取模该数字。

请记住，随着指数的增加，这种模幂最终会进入一个循环（循环的大小取决于矩阵和模的属性）。

代码看起来像这样（未经测试且不是特别优雅，几乎只是在每次乘法后插入矩阵模数）：

/* Raises the matrix to the exponent n, modulo m. */
int NUM(int n, int m)
 {
  int F[2][2] = {{2,2},{1,0}};
  if(n == 0)
      return 0;
  power(F, n-1, m);
  return F[0][0];
 }

/* Takes a matrix modulo m. */
void modMatrix(int F[2][2], int m)
{
   F[0][0] = F[0][0] % m;
   F[0][1] = F[0][1] % m;
   F[1][0] = F[1][0] % m;
   F[1][1] = F[1][1] % m;
}

/* Optimized version of power() - raises a matrix F to the exponent n modulo modulus */
void power(int F[2][2], int n, int modulus)
{
  if( n == 0 || n == 1) return; // recursive termination condition

  int M[2][2] = {{2,2},{1,0}}; // original matrix for multiplication

 power(F, n/2, modulus); // raise the matrix to half the exponent
 modMatrix(multiply(F, F), modulus); // square the matrix to go the rest of the way

 if( n%2 != 0 ) modMatrix(multiply(F, M), modulus); // if the exponent is odd, multiply one last time
}
于 2012-07-06T20:32:34.790 回答
1

由于它是一个 2x2 矩阵，一种可能的方法是将其扩展为一组 泡利矩阵和一个单位矩阵。然后使用泡利矩阵的属性（正方形是单位矩阵等 - 参见链接页面）计算Nth 次方，这对于纸笔练习并不难（参见 Wiki 链接中的等式（2）以上）。

于 2012-07-07T11:51:47.030 回答