大整数乘法.cpp

大整数乘法 本程序中大整数由用户决定 并且算法复杂度相对叫小 有很好的可读性

#include <iostream.h>
#include <math.h>

long mult(long x,long y,int n);
int num(long x);

void main() //主函数
{
	int n=0,m=0;
	int *a=new int[n];
	int *b=new int[m];
	cout<<"请输入这两个大整数的位数"<<endl;
	cout<<"n=";cin>>n;cout<<endl;
	cout<<"m=";cin>>m;cout<<endl;
	cout<<"请输入这两个大整数a[n]和b[n](one by one)"<<endl;
	for(int i=0;i<n;i++)
		cin>>a[i];
	for(i=0;i<m;i++)
		cin>>b[i];
 long x,y;
 cout<<"input x and y:"<<endl;
 cin>>x;
 cout<<endl;
 cin>>y;
 cout<<mult(x,y,num(x))<<endl;
}

long mult(long x,long y,int n)
{
 long a,b,c,d,s;
 if (n=1)
  return x*y;
 else
 {
  a=long(x/pow(10,(n/2))); //取x的左半部分
  b=long(x%long(pow(10,(n/2)))); //取x的右半部分
  c=long(y/pow(10,(n/2))); //取y的左半部分
  d=long(y%long(pow(10,(n/2)))); //取y的右半部分
  s=mult(a,c,n)*pow(2,n)+(mult((a-b),(d-c),n)+mult(a,c,n)+mult(b,d,n))*pow(2,n/2)+mult(b,d,n); //书上的公式
  return (s);
 }
}

int num(long x) //判断输入的数字的位数
{
 int i=0;
 if(x-9<=0)
  return 1;
 else
 {
  while (x!=0)
  {
   i++;
   x=x/10;
  }
  return i;
 }
}