大整数乘法.cpp

此代码为两个大整数的乘法运算

#include<iostream.h>
#include<math.h>/*用到pow()函数*/
#include<stdio.h>
#include<string.h>
#include<time.h>/*用到时间函数clock()*/
#define MAX 10000/*定义相乘的两个数的最大位数*/

int adc(int x[],int xb,int xe,int y[],int yb,int ye,int z[],int zb,int ze,int flag)/*带进位的加法*/ 
{int F=0;int dist;
 dist=xe-xb;
 z[ze]=x[xe]+y[ye]+flag;
 if(z[ze]>9)
 {z[ze]=z[ze]-10;
  F=1;}
 else F=0;
 for(int i=1;i<=dist;i++)
 {z[ze-i]=x[xe-i]+y[ye-i]+F;
  if(z[ze-i]>9)
  {z[ze-i]=z[ze-i]-10;
   F=1;}
  else F=0;}
  return F;
}

int sub(int x[],int n,int y[])/*减函数,y[]为x[]的前半部分,减后放入y[]中*/
{int flag=0,i;
 for( i=1;i<=n/2;i++)/*判断前半部分和后半部分那个大*/
 {if(x[i]<x[i+n/2])
	{y[0]=-1;break;}
  else 
	if(x[i]>x[i+n/2])
	{y[0]=1;break;}
    else 
	if(x[i]==x[i+n/2])
    continue;}
    if(i==n/2+1)/*如果前半部分和后半部分相等*/
	{for(i=1;i<=n/2;i++)
     y[i]=0;}
    else if(y[0]==1)/*前半部分比后半部分大*/
    for( i=n/2;i>=1;i--)
	{y[i]=x[i]-x[n/2+i]-flag;
     if(y[i]<0)/*不够减，则向高位借位*/
	 {y[i]=y[i]+10;
      flag=1;}
     else flag=0;
	}else
	for(i=n/2;i>=1;i--)/*此处这样处理是为了得到其绝对值*/
	{y[i]=x[n/2+i]-x[i]-flag;
     if(y[i]<0)
	 {y[i]=y[i]+10;
      flag=1;}
	 else flag=0;
	}return y[0];
}

void add(int x[],int y[],int n) /*此加法是求(x0*y1+x1*y0)*/
{int flag=0,i;
 if(x[0]==1)/*当x[]为正数时*/
 for( i=n;i>=0;i--)
 {x[i+1]=x[i+1]+y[i]+flag;/*两个数直接带进为相加*/
  if(x[i+1]>9)/*如果大于九，则调整，进位*/
  {x[i+1]=x[i+1]-10;
   flag=1;}
   else flag=0;
 }else if(x[0]==-1)/*当x[]为负数时*/
 {for( i=1;i<=n;i++)
  {if(y[i]<x[i+1])
	{y[0]=-1;break;}
   else if(y[i]>x[i+1])
	{y[0]=1;break;}
    else if(y[i]==x[i+1])
    continue;}
   if(i==n+1)/*如果这两个数绝对值相等*/
	for(i=2;i<=n+1;i++)
	x[i]=0;
	else if(y[0]==1)/*当y[]绝对值大于x[]时*/
	{x[0]=1;
     for( i=n;i>=1;i--)
	 {x[i+1]=y[i]-x[1+i]-flag;
      if(x[i+1]<0)
		{x[i+1]=x[i+1]+10;
         flag=1;}
      else flag=0;
	 }
	}else   /*当y[]绝对值小于x[]时*/
	{x[0]=-1; 
     for( i=n;i>=1;i--)
	 {x[i+1]=x[1+i]-y[i]-flag;
      if(x[i+1]<0)
	  {x[i+1]=x[i+1]+10;
       flag=1;}
      else flag=0;
}}}}

int* mul(int x[],int y[],int n)  /*乘法函数*/
{ if(n==2)/*n==2的情况,避免无限递归调用*/
	{int *z;
     z=new int[5];
     int sum;
     sum=(x[1]*10+x[2])*(y[1]*10+y[2]);
     z[4]=sum%10;/*算出相应位的数值*/
     z[3]=sum%100/10;
     z[2]=sum%1000/100;
     z[1]=sum/1000;
     return z;}
    else
	{int *m0,*m1,*m2,*z,*p,*xtemp,*ytemp,*temp,*xt,*yt;
     int flag1,flag2,fg1,fg2,fg3,i;
     m0=new int[n+1];/*每个都预留符号位*/
     m1=new int[n+2];
     m2=new int[n+1];
     z=new int[2*n+1];
     xtemp=new int[n/2+1];
     ytemp=new int[n/2+1];
     temp=new int[n/2+1];
     m0[0]=m1[0]=m2[0]=m1[1]=0;
     for( i=1;i<=n/2;i++)/*将数的后半部分赋给寄存数组*/
	{xtemp[i]=x[i+n/2];
     ytemp[i]=y[i+n/2];}
     xt=x;yt=y;
     x=xtemp;y=ytemp;/*x,y为后半部分*/
     p=mul(x,y,n/2);/*将数的后半部分递归调用(x1*y1)*/
     for( i=1;i<=n;i++)
     m2[i]=*(p+i);/*将后半部分算好的数赋给m2*/
     x=xt;y=yt;
     for( i=1;i<=n/2;i++)/*将数的前半部分赋给寄存数组*/
	{xtemp[i]=x[i];
     ytemp[i]=y[i];}
     x=xtemp;y=ytemp;/*x,y为前半部分*/
     p=mul(x,y,n/2);/*将数的前半部分递归调用(x0*y0)*/
     for( i=1;i<=n;i++)/*相乘之后位数加一倍*/
     m0[i]=*(p+i);/*将前半部分算好的数赋给m0*/
     x=xt;y=yt;
     flag1=sub(y,n,ytemp);/*ytemp为前面部分的数,返回相减的数的符号*/
     flag2=sub(x,n,xtemp);/*xtemp为前面部分的数，返回相减的数的符号*/
     if(flag1*flag2==1) m1[0]=-1;/*判断两个相乘的数符号是否相等*/
     else  m1[0]=1;
	 x=xtemp;y=ytemp;/*此时两数的前半部分 (x0-x1)*(y1-y0) */
     p=mul(x,y,n/2);
     for( i=1;i<=n;i++)
     m1[i+1]=*(p+i);        
     add(m1,m0,n);           
     add(m1,m2,n);
     for( i=1;i<=n/2;i++)
     z[n/2+n+i]=m2[n/2+i];/*z存放三个加数相加结果*/
     fg1=0;
     fg2=adc(m2,1,n/2,m1,n/2+2,n+1,z,n+1,n/2+n,fg1);
     fg3=adc(m1,2,n/2+1,m0,n/2+1,n,z,n/2+1,n,fg2);
     temp[n/2]=m1[1];/*将(x0-x1)*(y1-y0)的进位位赋给temp*/
     for( i=1;i<=n/2-1;i++)
     temp[i]=0;
     adc(temp,1,n/2,m0,1,n/2,z,1,n/2,fg3);
     delete m0,m1,m2,xtemp,ytemp,temp;
     return z;}
}

void main()
{ 
	char a[MAX],b[MAX];
	int lengtha,lengthb,d1,d2,n;
	int *x,*y,*p;
	int i,j;
    clock_t start,end;
    cout<<"输入被乘数:"<<endl;
    gets(a);
    lengtha=strlen(a);
    cout<<"\n你输入被乘数的位数是 "<<lengtha<<" 位"<<endl;
    cout<<"\n输入乘数:"<<endl;
    gets(b);
    lengthb=strlen(b);
    cout<<"\n你输入乘数的位数是 "<<lengthb<<" 位"<<endl;
    start=clock();/*记录程序运行的起始时间*/
    if(lengtha>=lengthb)/*判断是否位数满足2的i次幂位数，得到i的值*/
	{for( i=1;i<=15;i++)
     if(lengtha-(int)pow(2,i)<=0)/*2的i次幂*/
	 break;}
    else 
    {for( i=1;i<=15;i++)
     if(lengthb-(int)pow(2,i)<=0)
     break;}
    d1=(int)pow(2,i)-lengtha;/*记录被乘数要补零的个数*/
    d2=(int)pow(2,i)-lengthb;/*记录乘数要补零的个数*/
    n=(int)pow(2,i);/*得到相应2的i次幂位数*/
    x=new int[n+1];y=new int[n+1];
    for( i=1;i<=d1;i++)/*在输入数前补零*/
    x[i]=0;
    for( i=1;i<=d2;i++)
    y[i]=0;
    for( i=d1+1;i<=n;i++)/*补零完后，在后面继续输入数*/
    x[i]=(int)a[i-d1-1]-48;/*把字符型转换成整型*/
    for( i=d2+1;i<=n;i++)
    y[i]=(int)b[i-d2-1]-48;    
    p=mul(x,y,n);
    cout<<"\n运算结果为："<<endl;
    for(i=1;i<=2*n;i++)
    if(!(*(p+i)==0))/*找到结果的开始位不为零的位置*/
    break;
    j=i-1;/*j为记录非零位的起始地址*/
    for(i;i<=2*n;i++)/*从非零位开始输出*/
    cout<<*(p+i);
    cout<<endl;
    cout<<"\n运算结果的位数为 "<<n*2-j<<" 位"<<endl;
    end=clock();/*记录程序运行的结束时间*/
    cout<<"\n程序运行时间为 "<<end-start<<" 毫秒"<<endl;
	puts("\n按回车键退出程序!");
	getchar();
}