#include "stdafx.h"
#include<iostream.h>
#include<math.h>/*用到pow()函數(shù)*/
#include<stdio.h>
#include<string.h>
#include<time.h>/*用到時間函數(shù)clock()*/
#define MAX 10000/*定義相乘的兩個數(shù)的最大位數(shù)*/

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[])/*減函數(shù),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[]為正數(shù)時*/
 for( i=n;i>=0;i--)
 {x[i+1]=x[i+1]+y[i]+flag;/*兩個數(shù)直接帶進為相加*/
  if(x[i+1]>9)/*如果大于九，則調(diào)整，進位*/
  {x[i+1]=x[i+1]-10;
   flag=1;}
   else flag=0;
 }else if(x[0]==-1)/*當x[]為負數(shù)時*/
 {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)/*如果這兩個數(shù)絕對值相等*/
	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)  /*乘法函數(shù)*/
{ if(n==2)/*n==2的情況,避免無限遞歸調(diào)用*/
	{int *z;
     z=new int[5];
     int sum;
     sum=(x[1]*10+x[2])*(y[1]*10+y[2]);
     z[4]=sum%10;/*算出相應位的數(shù)值*/
     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++)/*將數(shù)的后半部分賦給寄存數(shù)組*/
	{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);/*將數(shù)的后半部分遞歸調(diào)用(x1*y1)*/
     for( i=1;i<=n;i++)
     m2[i]=*(p+i);/*將后半部分算好的數(shù)賦給m2*/
     x=xt;y=yt;
     for( i=1;i<=n/2;i++)/*將數(shù)的前半部分賦給寄存數(shù)組*/
	{xtemp[i]=x[i];
     ytemp[i]=y[i];}
     x=xtemp;y=ytemp;/*x,y為前半部分*/
     p=mul(x,y,n/2);/*將數(shù)的前半部分遞歸調(diào)用(x0*y0)*/
     for( i=1;i<=n;i++)/*相乘之后位數(shù)加一倍*/
     m0[i]=*(p+i);/*將前半部分算好的數(shù)賦給m0*/
     x=xt;y=yt;
     flag1=sub(y,n,ytemp);/*ytemp為前面部分的數(shù),返回相減的數(shù)的符號*/
     flag2=sub(x,n,xtemp);/*xtemp為前面部分的數(shù)，返回相減的數(shù)的符號*/
     if(flag1*flag2==1) m1[0]=-1;/*判斷兩個相乘的數(shù)符號是否相等*/
     else  m1[0]=1;
	 x=xtemp;y=ytemp;/*此時兩數(shù)的前半部分 (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存放三個加數(shù)相加結果*/
     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<<"輸入被乘數(shù):"<<endl;
    gets(a);
    lengtha=strlen(a);
    cout<<"\n你輸入被乘數(shù)的位數(shù)是 "<<lengtha<<" 位"<<endl;
    cout<<"\n輸入乘數(shù):"<<endl;
    gets(b);
    lengthb=strlen(b);
    cout<<"\n你輸入乘數(shù)的位數(shù)是 "<<lengthb<<" 位"<<endl;
    start=clock();/*記錄程序運行的起始時間*/
    if(lengtha>=lengthb)/*判斷是否位數(shù)滿足2的i次冪位數(shù)，得到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;/*記錄被乘數(shù)要補零的個數(shù)*/
    d2=(int)pow(2,i)-lengthb;/*記錄乘數(shù)要補零的個數(shù)*/
    n=(int)pow(2,i);/*得到相應2的i次冪位數(shù)*/
    x=new int[n+1];y=new int[n+1];
    for( i=1;i<=d1;i++)/*在輸入數(shù)前補零*/
    x[i]=0;
    for( i=1;i<=d2;i++)
    y[i]=0;
    for( i=d1+1;i<=n;i++)/*補零完后，在后面繼續(xù)輸入數(shù)*/
    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運算結果的位數(shù)為 "<<n*2-j<<" 位"<<endl;
    end=clock();/*記錄程序運行的結束時間*/
    cout<<"\n程序運行時間為 "<<end-start<<" 毫秒"<<endl;
	puts("\n按回車鍵退出程序!");
	getchar();
}