大整數(shù)乘法(分治法)

1、#include#include#include#include#define DATASIZE 1000/ 該函數(shù)用以接收用戶輸入的大整數(shù)，返回值為該大整數(shù)的數(shù)字位數(shù)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;/ 該函數(shù)通過在較短的大整數(shù)之前填充 0 的方式，將兩個大整數(shù)的位數(shù)對 齊，返回值為較長的那個大整數(shù)的位置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;/ 該函數(shù)通過刪去大整數(shù)前面無意義的 0 來得到其真實的數(shù)字位數(shù) 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 的大整數(shù)做減法，得到的結果放到數(shù)組 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;/ 分治法求兩個大整數(shù)的乘積，它只需要更少次數(shù)的乘法，但是它必須遞歸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);/將原來的兩個大整數(shù)，分治為一半，分別放入到a1,aO和bl, b0四個數(shù)組當中去 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);/ 輸入大整數(shù) a/ 輸入大整數(shù) blen