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 回答