2

行列指数関数を実行するために、（再帰を使用して）繰り返し二乗アルゴリズムを使用しようとしています。配列を使用する代わりに、NEWMATライブラリのヘッダーファイルをインクルードしました。元の行列には（-5,5）の範囲の要素があり、すべての数値は浮動小数点型です。

# include "C:\User\newmat10\newmat.h"
# include "C:\User\newmat10\newmatio.h"
# include "C:\User\newmat10\newmatap.h"

# include <iostream>
# include <time.h>
# include <ctime>
# include <cstdlib>
# include <iomanip>

using namespace std;

Matrix repeated_squaring(Matrix A, int exponent, int n) //Recursive function
 {
    A(n,n);
    IdentityMatrix I(n);

    if (exponent == 0) //Matrix raised to zero returns an Identity Matrix
    return I;

    else 
    {

        if ( exponent%2 == 1 ) // if exponent is odd
        return (A * repeated_squaring (A*A, (exponent-1)/2, n));

        else //if exponent is even
        return (A * repeated_squaring( A*A, exponent/2, n));
    }
  }

 Matrix direct_squaring(Matrix B, int k, int no) //Brute Force Multiplication
  {
B(no,no);
Matrix C = B;
for (int i = 1; i <= k; i++)
    C = B*C;
return C;
   }

    //----Creating a matrix with elements b/w (-5,5)----


float unifRandom()
{
int a = -5;
int b = 5;
float temp = (float)((b-a)*( rand()/RAND_MAX) + a);
return temp;
}

Matrix initialize_mat(Matrix H, int ord)
{
H(ord,ord);
for (int y = 1; y <= ord; y++)
    for(int z = 1; z<= ord; z++)
        H(y,z) = unifRandom();

return(H);
}
//---------------------------------------------------

void main()
{
int exponent, dimension;

cout<<"Insert exponent:"<<endl;
cin>>exponent;
cout<< "Insert dimension:"<<endl;   
cin>>dimension;


cout<<"The number of rows/columns in the square matrix is: "<<dimension<<endl;
cout<<"The exponent is: "<<exponent<<endl;

Matrix      A(dimension,dimension),B(dimension,dimension);
    Matrix C(dimension,dimension),D(dimension,dimension);

B= initialize_mat(A,dimension);

cout<<"Initial Matrix: "<<endl;

cout<<setw(5)<<setprecision(2)<<B<<endl;
//-----------------------------------------------------------------------------

cout<<"Repeated Squaring Result: "<<endl;

clock_t time_before1 = clock();

C = repeated_squaring (B, exponent , dimension);
cout<< setw(5) <<setprecision(2) <<C;

clock_t time_after1 = clock();
float diff1 = ((float) time_after1 - (float) time_before1);
cout << "It took " << diff1/CLOCKS_PER_SEC << " seconds to complete" << endl<<endl;

//---------------------------------------------------------------------------------

cout<<"Direct Squaring Result:"<<endl;

clock_t time_before2 = clock();

D = direct_squaring (B, exponent , dimension);
cout<<setw(5)<<setprecision(2)<<D;

clock_t time_after2 = clock();
float diff2 = ((float) time_after2 - (float) time_before2);
cout << "It took " << diff2/CLOCKS_PER_SEC << " seconds to complete" << endl<<endl;

}

私は次の問題に直面しています。

  1. 乱数ジェネレーターは、出力の各要素として「-5」のみを返します。
  2. 行列の乗算は、ブルートフォース乗算と繰り返し二乗アルゴリズムを使用した場合に異なる結果をもたらします。

コードの実行時間を計って、ブルートフォースの乗算と繰り返しの二乗にかかる時間を比較しています。

誰かが再帰とマトリックスの初期化の何が問題になっているのか調べてもらえますか？

注：このプログラムをコンパイルするときは、NEWMATライブラリをインポートしたことを確認してください。

前もって感謝します！

4

2 に答える 2

1

rand()intを返すので、rand()/RAND_MAXに切り捨てられinteger = 0ます。繰り返し二乗アルゴリズムを手作業で試してみる と、非常に非効率的であるwith n = 1, 2 and 3ことがわかります。surplus A *

于 2012-10-20T05:49:08.667 に答える
0

最終作業コードには、次の改善があります。

Matrix repeated_squaring(Matrix A, int exponent, int n) //Recursive function
{
    A(n,n);
    IdentityMatrix I(n);

    if (exponent == 0) //Matrix raised to zero returns an Identity Matrix
    return I;

    if (exponent == 1)
        return A;

    {

        if (exponent % 2 == 1) // if exponent is odd
        return (A*repeated_squaring (A*A, (exponent-1)/2, n));

        else //if exponent is even
        return (repeated_squaring(A*A, exponent/2, n));
    }
}

Matrix direct_squaring(Matrix B, int k, int no) //Brute Force Multiplication
{
B(no,no);
Matrix C(no,no);
C=B;
for (int i = 0; i < k-1; i++)
    C = B*C;
return C;
}

//----要素b/w（-5,5）で行列を作成する----

float unifRandom()
{
int a = -5;
int b = 5;

float temp = (float) ((b-a)*((float) rand()/RAND_MAX) + a);
return temp;
}
于 2012-10-21T22:39:06.260 に答える