1

行列[2,2][1,0]があります。この2*2行列のn番目の乗算が必要です。単純な乗算を使用する場合、O（n）またはO（logn）で実行できます。O（logn）コード：

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でも機能しないため、この方法はあまり役に立たないと思います。 。

基本的に私の問題は、数値がかなり大きくなり、長い整数でさえも来ないということです。それでは、どうすればそれに対処できますか。

nが10^9のときに2*2行列[2,2][1,0]のn乗を取得するための式またはアルゴリズムを誰かが私に提案できますか？

ありがとう

4

2 に答える 2

3

これは宿題ですか、それとも実装の演習ですか？選択肢がある場合は、モジュロの方がおそらく便利です。基本的に、各累乗または乗算の後に行列をモジュロで数Mとすると、行列の個々のエントリが（M-1）^ 2を超えることはありませんが、結果は明らかになります。べき乗剰余のアルゴリズムであるため、現在のアルゴリズムとは異なります。

したがって、unsigned longの場合、最大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行列であるため、可能な方法は、 パウリ行列と単位行列のセットに拡張することです。次に、パウリ行列のプロパティ（正方形は単位行列など-リンクされたページを参照）を使用してN、紙と鉛筆の練習の難しいことではない乗数を計算します（Wikiリンクの式（2）を参照）その上）。

于 2012-07-07T11:51:47.030 に答える