大整数乘法(分治法)

1、#include#include#include#include#define DATASIZE 1000/ 该函数用以接收用户输入的大整数，返回值为该大整数的数字位数int InputBigInt(int arr)char ch;int i=0;printf(Input a Big Interger:);while(1)scanf(%c,&ch);if(ch=n)break;elsearri+=ch-0;return i;/ 该函数通过在较短的大整数之前填充 0 的方式，将两个大整数的位数对 齐，返回值为较长的那个大整数的位置int AlignArray(int *a,int len_a,i

2、nt *b,int len_b)int len_align=len_a;if(len_alen_b)for(int i=len_b-1;i=0;i-) bi+(len_a-len_b)=bi;for(int i=0;ilen_a-len_b;i+)bi=0;len_align=len_a;else if(len_a=0;i-) ai+(len_b-len_a)=ai;for(int i=0;ilen_b-len_a;i+)ai=0;len_align=len_b;return len_align;/ 该函数通过删去大整数前面无意义的 0 来得到其真实的数字位数 int Adjust(int a

3、,int len)while(a0=0)int j=1;doaj-1=aj;j+;while(j=0;i-)int t=ai+bi+carry;ci+1=t%10;carry=t/10;c0=carry;return length+1;/ 两个长度为 length 的大整数做减法，得到的结果放到数组 C 中，长度为 lengthint Sub(int a,int b,int c,int length)int borrow=0;for(int i=length-1;i=0;i-)ai=ai-borrow;if(ai=bi)ci=ai-bi;borrow=0;elseint t=ai+10-bi;

4、borrow=1;return length;/ 分治法求两个大整数的乘积，它只需要更少次数的乘法，但是它必须递归int DividBigIntMultiply(int a,int b,int c,int len)int l=len/2;if(len=1)int t=a0*b0;c0=t/10;c1=t%10;return 2;elseif(len=2)int t1=a1*b1;c3=t1%10;int t2=a0*b1+a1*b0+t1/10;c2=t2%10;int t3=a0*b0+t2/10;c1=t3%10;c0=t3/10;return 4;5 / 10elseint *a1,*a

5、0,*b1,*b0;a1=(int *)malloc(l*sizeof(int);a0=(int *)malloc(len-l)*sizeof(int);b1=(int *)malloc(l*sizeof(int);b0=(int *)malloc(len-l)*sizeof(int);if(a1=NULL | a0=NULL | b1=NULL | b0=NULL)printf( 内存分配失败，递归失败，程序退出！ n);exit(0);/将原来的两个大整数，分治为一半，分别放入到a1,aO和bl, b0四个数组当中去 for(int i=0;il;i+)a1i=ai;b1i=bi;for(

6、int i=l;ilen;i+)a0i-l=ai;b0i-l=bi;int l1=AlignArray(a1,l,a0,len-l);int l2=AlignArray(b1,l,b0,len-l);l=l1;/先求得c2和cO,直接做乘法就可以了int *c2,*c0;c2=(int *)malloc(2*l*sizeof(int);c0=(int *)malloc(2*l*sizeof(int);if(c2=NULL | c0=NULL)printf( 内存分配失败，递归失败，程序退出！ n);exit(0);DividBigIntMultiply(a1,b1,c2,l);/c2=a1*b

7、1, 长度为 2*l DividBigIntMultiply(a0,b0,c0,l);/c0=a0*b0, 长度为 2*l/再来求得C1,这里有乘法也有加法，还有减法/c1=(a1+a0)*(b1+b0)-(c2+c0)int *t1,*t2,*t3,*t4,*C1;t1=(int *)malloC(1+l)*sizeof(int); /t1=a1+a0t2=(int *)malloC(1+l)*sizeof(int); /t2=b1+b0t3=(int *)malloC(1+2*l)*sizeof(int);/t3=t1*t2t4=(int *)malloC(2*(l+1)*sizeof(i

8、nt);/t4=C2+C0C1=(int *)malloC(2*(l+1)*sizeof(int);/C1=t3-t4 if(t1=NULL | t2=NULL | t3=NULL)printf( 内存分配失败，递归失败，程序退出！ n); exit(0);int len 仁Add(a1,aO,t1,l); lit 仁 a1+aO,长度为 1+1int len2=Add(b1,b0,t2,l);/t2=b1+b0, 长度为 l+1int len4=Add(c2,c0,t4,2*l);llt4=c2+c0, 长度为 2*l+1int len3=AlignArray(t1,len1,t2,len2

9、);DividBigIntMultiply(t1,t2,t3,len3);llt3=t1*t2, 长度为 2*(l+1)int k=AlignArray(t4,len4,t3,len3);ll 将 c1 与 t3 对齐，长度为 2*(l+1)int len5=Sub(t4,t3,c1,k); llc1=t4-t3, 长度为 2*(l+1)ll 打印输出 c2,c1 和 c0int i=0;printf(c2=);while(c2i=0) i+;for(;i2*l;i+)printf(%d,c2i);printf(n);int j=0;printf(c0=);while(c0j=0) j+;for(;j2*l;j+)printf(%d,c0j);printf(n);int n=0;printf(c1=);while(c1n=0) n+;for(;nlen5;n+)printf(%d,c1n);printf(n);return 2*len;void main()int aDATASIZE,bDATASIZE,c2*DATASIZE;int len_a,len_b,len_align;len_a=InputBigInt(a);len_b=InputBigInt(b);/ 输入大整数 a/ 输入大整数 blen