multiply.c

用动态规划算法实现的多段图程序

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<assert.h>

//矩阵大小
#define N 1000
#define M 4539

int A1[N][N],B1[N][N],A2[M][M],B2[M][M],C1[N][N],C2[M][M];

//用一般的方法求n-1阶多项式在x的值
double PolynomialMultiply(double *A,int n,double x)
{
	//assert(A != NULL);
	double dValue = A[0];
	double dTemp = 1.0;
	int i =  1;
	

	for(i = 1; i < n; i++)
	{
		dTemp = dTemp*x;
		dValue = dValue + A[i]*dTemp;
	}

	return dValue;
}



//用Horner方法求n-1阶多项式在x的值
double PolynomialMultiply_Horner(double *A,int n,double x)
{
	//assert(A != NULL);
	double dValue = A[n-1];
	int i = n-2;

	for(i = n-2; i >= 0; i--)
	{
		dValue = dValue*x + A[i];
	}

	return dValue;

}


//用一般的方法求两个矩阵乘法值
void MatrixMultiply(int (*A)[N],int m,int (*B)[N],int n,int (*C)[N])
{
	int i,j,k;

	for(i = 0; i < m; i++)
	{
		for(j = 0; j < N; j++)
		{
			C[i][j] = 0;
			for(k = 0; k < N; k++)
			{
				C[i][j] = C[i][j] + A[i][k]*B[k][j];
			}
		}
	}
}

//扩充矩阵阶数
int LeastPowVal(int n)
{
	int Temp = 1;

	while(1)
	{
		if(Temp > n)
			return Temp;
		else
			Temp = Temp*2;
	}
}

//用Strassen矩阵乘法
void Strassen(int Left,int Top,int Row,int Column)
{
	

}







//俄氏乘法
int Multiply(int m,int n)
{
	if(m == 1)
		return n;
	else 
	{
		if(m%2 == 0)
		{
			return (Multiply(m>>1,n<<1));
		}
		else
			return (Multiply((m-1)>>1,n<<1) + n);
	}
}

int main()
{
	double adPolyCoef[] = {200.341,0,39,0,57,23,79,86,109,98,0,-66,0,45};//size:14
	double x,PolyVal_1,PolyVal_2;

	//int A[N][N],B[N][N],C1[N][N],C2[N][N];
	clock_t start1,finish1,start2,finish2,start3,finish3,start4,finish4;
	double D1,D2,D3,D4;
	time_t t;
	int i,j;

	srand((unsigned) time(&t));


	//多项式乘法
	for(i = 0; i < 10; i++)
	{
		x = rand()%1000;
		
		start1 = clock();
		for(j = 0; j < 1000000; j++)
		{
			PolyVal_1 = PolynomialMultiply(adPolyCoef,14,x);
		}
		finish1 = clock();
		D1 = (double)(finish1- start1)/CLOCKS_PER_SEC;

		start2 = clock();
		for(j = 0; j < 1000000; j++)
		{
			PolyVal_2 = PolynomialMultiply_Horner(adPolyCoef,14,x);
		}
		finish2 = clock(); 
		D2 = (double)(finish2- start2)/CLOCKS_PER_SEC;

		printf("x = %f\n",x);
		printf("PolyVal_1 = %g,time = %f\n",PolyVal_1,D1);
		printf("PolyVal_2 = %g,time = %f\n\n",PolyVal_2,D2);
	}

	
	for(i = 0; i < M; i++)
	{
		for(j = 0; j < M; j++)
		{
			A2[i][j] = 0;
			B2[i][j] = 0;
		}
	}


	for(i = 0; i < N; i++)
	{
		for(j = 0; j < N; j++)
		{
			A1[i][j] = rand()%100 + 1;
			A2[i][j] = A1[i][j];
			B1[i][j] = rand()%100 + 1;
			B2[i][j] = B1[i][j];
		}
	}
	
	
	start3 = clock();
	MatrixMultiply(A1,N,B1,N,C1);
	finish3 = clock(); 
	D3 = (double)(finish3- start3)/CLOCKS_PER_SEC;

	start4 = clock();
	Strassen(0,0,LeastPowVal(N),LeastPowVal(N));
    finish4 = clock(); 
	D4 = (double)(finish4- start4)/CLOCKS_PER_SEC;
	

	printf("Normal matrix multiplied method cost time = %f\n",D3);
	printf("39 *79 = %d\n\n",Multiply(39,79));

	return 0;
}