strassen.cpp

在应用中常用矩阵相乘的定义算法对其进行计算。这个算法用到了大量的循环和相乘运算

#include<iostream.h>
#include<stdlib.h>
#include<iomanip>
typedef int piece[2][2];
void mul(piece a1,piece a2,piece d){
	int m1=a1[0][0]*(a2[0][1]-a2[1][1]);
	int m2=(a1[0][0]+a1[0][1])*a2[1][1];
	int m3=(a1[1][0]+a1[1][1])*a2[0][0];
	int m4=a1[1][1]*(a2[1][0]-a2[0][0]);
	int m5=(a1[0][0]+a1[1][1])*(a2[0][0]+a2[1][1]);
	int m6=(a1[0][1]-a1[1][1])*(a2[1][0]+a2[1][1]);
	int m7=(a1[0][0]-a1[1][0])*(a2[0][0]+a2[0][1]);
	d[0][0]=m5+m4-m2+m6;
	d[0][1]=m1+m2;
	d[1][0]=m3+m4;
	d[1][1]=m5+m1-m3-m7;
};
void add(piece a1,piece a2,piece d){
	d[0][0]=a1[0][0]+a2[0][0];
	d[0][1]=a1[0][1]+a2[0][1];
	d[1][0]=a1[1][0]+a2[1][0];
	d[1][1]=a1[1][1]+a2[1][1];
};
void sub(piece a1,piece a2,piece d){
	d[0][0]=a1[0][0]-a2[0][0];
	d[0][1]=a1[0][1]-a2[0][1];
	d[1][0]=a1[1][0]-a2[1][0];
	d[1][1]=a1[1][1]-a2[1][1];
};
void calculate(int a[4][4],int b[4][4],int d[4][4]){
	int a00[2][2],a01[2][2],a10[2][2],a11[2][2];
	int b00[2][2],b01[2][2],b10[2][2],b11[2][2];
	int c00[2][2],c01[2][2],c10[2][2],c11[2][2];
	int temp[2][2],temp2[2][2];
	int m1[2][2],m2[2][2],m3[2][2],m4[2][2],m5[2][2],m6[2][2],m7[2][2];
	for(int i=0;i<2;i++){
		for(int j=0;j<2;j++){
			a00[i][j]=a[i][j];
			b00[i][j]=b[i][j];
		};
		for(int k=0;j<4;j++,k++){
			a01[i][k]=a[i][j];
			b01[i][k]=b[i][j];
		}
	};
	for(int l=0;i<4;i++,l++){
		for(int j=0;j<2;j++){
			a10[l][j]=a[i][j];
			b10[l][j]=b[i][j];
		};
		for(int k=0;j<4;j++,k++){
			a11[l][k]=a[i][j];
			b11[l][k]=b[i][j];
		}
	};
	sub(b01,b11,temp);mul(a00,temp,m1);	
	add(a00,a01,temp);mul(temp,b11,m2);	
	add(a10,a11,temp);mul(temp,b00,m3);	
	sub(b10,b00,temp);mul(a11,temp,m4);	
	add(a00,a11,temp);add(b00,b11,temp2);mul(temp,temp2,m5);	
	sub(a10,a11,temp);add(b10,b11,temp2);mul(temp,temp2,m6);	
	sub(a00,a10,temp);add(b00,b10,temp2);mul(temp,temp2,m7);	
	add(m5,m4,temp);sub(temp,m2,temp);add(temp,m6,c00);
	add(m1,m2,c01);
	add(m3,m4,c10);
	add(m5,m1,temp);sub(temp,m3,temp);sub(temp,m7,c11);
	for( i=0;i<2;i++){
		for(int j=0;j<2;j++){
			d[i][j]=c00[i][j];
		};
		for(;j<4;j++){
			d[i][j]=c01[i][j];
		}
	};
	for(;i<4;i++){
		for(int j=0;j<2;j++){
			d[i][j]=c10[i][j];
		};
		for(;j<4;j++){
			d[i][j]=c11[i][j];
		}
	};
};
void main(){
	int a[4][4]={2,2,2,2,
		         3,3,3,3,
		         4,4,4,4,
				 5,5,5,5};  
	int b[4][4]={0,1,1,1,
		         1,0,1,1,
		         1,1,0,1,
		          1,1,1,0};	        		         		       
/*int a[4][4]={2,2,2,2,                   	
		         3,3,3,3,                             
		         4,4,4,4,                             
				 5,5,5,5}   ;                        
int b[4][4]={0,1,1,1,		         		         		       
1,0,1,1,
1,0,1,1,
1,1,0,1,
1,1,1,0};   */

	int c[4][4];
	calculate(a,b,c);
	for(int i=0;i<4;i++){
		for(int j=0;j<4;j++){
			cout<<c[i][j]<<" ";
		}
		cout<<endl;
	};
}