dividemultiply.cpp

这是一个分治法应用的又一个例子,利用分治技术,做大整数乘法,尤其是几百位数以上的乘法,比一般的方法快很多,仅次于快速傅立叶变换.

#include<iostream.h>
#include<math.h>
#include<string.h>
char a[100],b[100],c[200];
int n,m,k;

void mul(int lefta,int righta,int leftb,int rightb,int times)
{
	if(lefta==righta && leftb==rightb)
	{
		int temp=c[times]-48+(a[lefta]-48)*(b[leftb]-48);
		if(temp>=10)
		{
			int s=temp/10;
			c[times]=temp%10+48;
			int start=times+1;
			while(s>0)
			{
				temp=c[start]-48+s;
				c[start]=temp%10+48;
				s=temp/10;
			}
		}
		else
			c[times]=temp+48;
		return;
	}
	int mida=(lefta+righta)/2;
	int midb=(leftb+rightb)/2;
	int length=righta-lefta+1;
	mul(mida+1,righta,midb+1,rightb,times);
	if(midb>=k-m)	
		mul(mida+1,righta,leftb,midb,length/2+times);
	if(mida>=k-n)
		mul(lefta,mida,midb+1,rightb,length/2+times);
	if(mida>=k-n && midb>=k-m)
		mul(lefta,mida,leftb,midb,length+times);
}

void main()
{
	char ta[50],tb[50];
	cout<<"输入被乘数"<<endl;
	cin>>ta;
	cout<<"输入乘数 ( 乘数的位数不能多于被乘数的位数 )"<<endl;
	cin>>tb;
	n=strlen(ta);
	m=strlen(tb);
	int temp=log(n)/log(2);
	k=(int)pow(2,temp);
	if(k<n)
		k*=2;
	for(int i=0;i<k-n;i++)
		a[i]='0';
	for(i=0;i<k-m;i++)
		b[i]='0';
	strcat(a,ta);
	strcat(b,tb);
	for(i=0;i<n+m;i++)
		c[i]='0';
	mul(0,k-1,0,k-1,0);
	cout<<"它们的乘积是:"<<endl;
	if(c[n+m-1]!='0')
		cout<<c[n+m-1];
	for(i=n+m-2;i>=0;i--)
		cout<<c[i];
	cout<<endl;
}