两个矩阵相乘的执行时间怎么定义呢???
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<math.h>
int randseed=0; //随机序列种子
randomize(); //初始化随机序列
float random() //随机数生成器
{
srand(randseed);
randseed=rand();
return (float)1+randseed%10;
}
void createMatrix(int n,float ***newM) //建立动态n阶矩阵
{
int i;
(*newM)=(float **)malloc(n*sizeof(float *));
if((*newM)==NULL)
{
printf("错误!空间已满!\n");
exit(0);
}
for(i=0;i<n;i++)
{
(*newM)[i]=(float *)malloc(n*sizeof(float));
if((*newM)[i]==NULL)
{
printf("错误!空间已满!\n");
exit(0);
}
}
}
void scanfMatrix(int n,int k,float **p) //随机输入矩阵数据
{
int i,j;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
p[i][j]=random();
if(n!=k) //当n不是2的幂的时候填充0 再进行矩阵分割
{
for(i=0;i<n;i++)
for(j=n;j<k;j++)
p[i][j]=0;
for(i=n;i<k;i++)
for(j=0;j<k;j++)
p[i][j]=0;
}
}
void printfMatrix(int n,float **C) //输出矩阵
{
int i,j;
for(i=0;i<n;i++){
for(j=0;j<n;j++)
printf("%4.f ",C[i][j]);
printf("\n");
}
printf("\n");
}
void matrixAdd(int n,float **a,float **b,float **c) //矩阵加法
{
int i,j;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
c[i][j]=a[i][j]+b[i][j];
}
}
void matrixSub(int n,float **a,float **b,float **c) //矩阵减法
{
int i,j;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
c[i][j]=a[i][j]-b[i][j];
}
}
void matrixMul(int n,float **A,float **B,float **C) //矩阵乘法 传统做法
{
int i,j,k;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
C[i][j]=0;
for(k=0;k<n;k++)
C[i][j]+=A[i][k]*B[k][j];
}
}
void Strassen(int n,float **A,float **B,float **C) //strassen算法函数
{
int i,j;
if (n==2) //当阶为2时进行传统矩阵乘法运算
matrixMul(2,A,B,C);
else
{
float **a11,**a12,**a21,**a22;
float **b11,**b12,**b21,**b22;
float **c11,**c12,**c21,**c22;
float **M1,**M2,**M3,**M4,**M5,**M6,**M7;
float **AA,**BB,**MM1,**MM2;
int m=n/2;
createMatrix(m,&a11); //A11-A22 动态创建子矩阵
createMatrix(m,&a12);
createMatrix(m,&a21);
createMatrix(m,&a22);
createMatrix(m,&b11); //B11-B22
createMatrix(m,&b12);
createMatrix(m,&b21);
createMatrix(m,&b22);
createMatrix(m,&c11); //c11-c22
createMatrix(m,&c12);
createMatrix(m,&c21);
createMatrix(m,&c22);
createMatrix(m,&M1); //M1-M7
createMatrix(m,&M2);
createMatrix(m,&M3);
createMatrix(m,&M4);
createMatrix(m,&M5);
createMatrix(m,&M6);
createMatrix(m,&M7);
createMatrix(m,&AA);
createMatrix(m,&BB);
createMatrix(m,&MM1);
createMatrix(m,&MM2);
for(i=0;i<m;i++) //分割矩阵
for(j=0;j<m;j++)
{
a11[i][j]=A[i][j];
a12[i][j]=A[i][j+m];
a21[i][j]=A[i+m][j];
a22[i][j]=A[i+m][j+m];
b11[i][j]=B[i][j];
b12[i][j]=B[i][j+m];
b21[i][j]=B[i+m][j];
b22[i][j]=B[i+m][j+m];
}
matrixSub(m,b12,b22,BB); //计算M1到M7
Strassen(m,a11,BB,M1); //M1=a11(b12-b22)
matrixAdd(m,a11,a12,AA);
Strassen(m,AA,b22,M2); //M2=(a11+a12)b22
matrixAdd(m,a21,a22,AA);
Strassen(m,AA,b11,M3); //M3=(a21+a22)b11
matrixSub(m,b21,b11,BB);
Strassen(m,a22,BB,M4); //M4=a22(b21-b11)
matrixAdd(m,a11,a22,AA);
matrixAdd(m,b11,b22,BB);
Strassen(m,AA,BB,M5); //M5=(a11+a22)(b11+b22)
matrixSub(m,a12,a22,AA);
matrixAdd(m,b21,b22,BB);
Strassen(m,AA,BB,M6); //M6=(a12-a22)(b21+b22)
matrixSub(m,a11,a21,AA);
matrixAdd(m,b11,b12,BB);
Strassen(m,AA,BB,M7); //M7=(a11-a21)(b11+b12)
matrixAdd(m,M5,M4,MM1);
matrixSub(m,M2,M6,MM2);
matrixSub(m,MM1,MM2,c11); //c11=M5+M4-M2+M6
matrixAdd(m,M1,M2,c12); //c12=M1+M2
matrixAdd(m,M3,M4,c21); //c21=M3+M4
matrixAdd(m,M5,M1,MM1);
matrixAdd(m,M3,M7,MM2);
matrixSub(m,MM1,MM2,c22); //c22=M5+M1-M3-M7
for(i=0;i<m;i++) //将值存入C矩阵中
for(j=0;j<m;j++)
{
C[i][j]=c11[i][j];
C[i][j+m]=c12[i][j];
C[i+m][j]=c21[i][j];
C[i+m][j+m]=c22[i][j];
}
free(a11);free(a12);free(a21);free(a22); //释放内存
free(b11);free(b12);free(b21);free(b22);
free(c11);free(c12);free(c21);free(c22);
free(M1);free(M2);free(M3);free(M4);
free(M5);free(M6);free(M7);
free(AA);free(BB);free(MM1);free(MM2);
}
}
void checkMatrix(int k,float **c,float **d) //检查Strassen与传统算法结果是否一致
{
int i,j;
for(i=0;i<k;i++)
for(j=0;j<k;j++)
if(fabs(c[i][j]-d[i][j])>0.000001)
{
printf("Wrong!!!\n");
printf("C[%d][%d]=%f\nD[%d][%d]=%f\n",i,j,c[i][j],i,j,d[i][j]);
}
printf("Yes!!!\n");
}
int littlePow(int n) //自定义计算2的n次方
{
int lp=1;
int i;
for(i=0;i<n;i++)
lp*=2;
return lp;
}
int determinePower(int n) //计算出大于等于n的最小的2的幂的次数
{
int pow=0;
int i=0;
while(n!=0)
{
pow++;
i+=n%2;
n/=2;
}
return i>1?pow:pow-1;
}
void main()
{
float **A,**B,**C,**D;
int n,k;
printf("请输入矩阵的阶数\n");
while(scanf("%d",&n)&&n<2)
printf("请重新输入一个大于2的数\n");
k=littlePow(determinePower(n));
createMatrix(k,&A); createMatrix(k,&B); createMatrix(k,&C); createMatrix(k,&D);
printf("\n"); printf("\n"); printf("矩阵A:\n"); printf("\n"); printf("\n");
scanfMatrix(n,k,A);
printfMatrix(n,A); //输出随机矩阵A
printf("\n"); printf("\n");
printf("矩阵B:\n");
printf("\n"); printf("\n");
scanfMatrix(n,k,B);
printfMatrix(n,B); //输出随机矩阵B
Strassen(k,A,B,C); //用Strassen算法计算矩阵A,B并将值存入矩阵C中
printf("\n"); printf("\n");
printf("strassen算法:\n");
printf("\n"); printf("\n");
printfMatrix(n,C); //输出strassen算法结果
matrixMul(k,A,B,D);
printf("\n"); printf("\n");
printf("传统算法:\n");
printf("\n"); printf("\n");
printfMatrix(n,C); //输出传统算法计算结果
printf("是否匹配:\n");
printf("\n"); printf("\n");
checkMatrix(n,C,D); //检查Strassen与传统算法结果是否一致
free(A); free(B); free(C); free(D); //释放动态分配的内存
printf("\n"); printf("\n"); printf("\n"); printf("\n");
main(); //递归进入主函数
}
