大整数乘法
1.算法原理
如果我们想要计算两个较大的数字相乘的时候，由于计算机硬件限制可能无法计算，因此我们可以将每个乘数用加法和乘法做分解，当分解到每个因子只是一位数的时候，乘法就很简单了，这也是一种分治法。
（1）分解：首先将2个大整数a（n位）、b（m位）分解为两部分：
| ah | al | bh | bl |
然后，
其中ah、al为n/2位，bh、bl为m/2位。两个大整数a、b相乘转换成了4个乘法运算，而乘数的位数变为了原来的一半。
（2）求解子问题。继续分解每个乘法运算，直到分解有一个乘数为1位数时停止分解，进行乘法运算并记录结果。
（3）合并。将计算出的结果相加并回溯，求出最终结果。
2.算法设计
（1）数据结构。将两个大数以字符串的形式输入，然后定义结构体Node，其中s[]数组用于存储大数，注意是倒序存储！（因为乘法加法运算中有可能出现进位，倒序存储时可以让进位存储在数组的末尾）。l表示长度，c表示幂次。两个大叔的初始次幂是0.如下所示：
char sa[1000];char sb[1000];typedef struct _Node{ int s[M];//数组，倒序存储大数 int l; int c;}Node, *pNode;
（2）划分函数。其中，cp()函数用于将一个n位的数分成两个n/2的数并存储，记录它的次幂和长度。
void cp(pNode src, pNode des, int st, int l){ //src表示待分解的数的结点，des表示分解后得到的数结点 //st表示从src结点数组中取数的开始位置，l表示取数长度 int i, j; for (i = st, j = 0; i<st + l; i++, j++) { des->s[j] = src->s[i];//从src节点数组中st位置开始取l个数 } des->l = l; des->c = st + src->c;//des次幂等于开始取数的位置加上src次幂。}
（3）乘法运算。定义的mul()函数用于将两个数进行相乘，不断进行分解，直到有一个乘数为1位时停止，让这两个数相乘，并记录结果回溯。
ma = pa->l/2;//表示a长度的一半mb = pb->l/2;//表示b长度的一半if(!ma || !mb)//如果!ma说明ma=0，即a的长度为1，该乘数为1位数，同理对mb也是{ if(!ma)//!ma说明a为1位数，a/b交换，保证a的长度大于b的长度 { temp=pa; pa=pb; pb=temp;//交换后b的长度为1 } ans->c = pa->c +pb->c; w=pb->s[0];//交换后b长度为1，用w记录即可 cc=0;//初始化进位为0 for(i=0;i<pa->;i++) {//把a中的数依次取出与w相乘，记录结果和进位 ans->s[i]=(w*pa->s[i]+cc)%10;//存储相乘结果的个位，十位做进位处理 cc=(w*pa->s[i]+cc)/10;//处理进位 }}if(cc) ans->s[i++]=cc;ans->l=i;
（4）合并函数
add()函数将分解得到的数进行相加合并。
void add(pNode pa, pNode pb, pNode ans){ //程序调用时把a、b的地址传递给pa、pb参数，表示待合并的两个数 //ans记录结果 int i,cc,k,alen,blen,len; int ta,tb; pNode temp; if(pa->c <pb->c)//交换保证a的次幂大 { temp=pa; pa=pb; pb=temp; } ans->c=pb->c;//结果的次幂为两个数中较小数的次幂 cc=0;//初始化进位为0 k=pa->c-pb->c;//k为a左侧需要补零的个数 alen = pa->l + pa->c;//a数加上次幂的总长度 blen = pb->l + pb->c;//b数加上次幂的总长度 if(alen>blen) len=alen; else len=blen; len=len-pb->c;//结果的长度为a/b之中的最大值减去最低次幂，最低次幂是不进行加法运算的位数 for(i=0;i<len;i++) { if(i<k) ta=0;//k为a左侧需要补零的个数，a左侧补零 else ta=pa->s[i-k];//i=k时，补零结束，从a数组中第0位开始去数字 if(i<pb->l) tb=pb->s[i];//从b数组中第0位开始取数字 else tb=0;//b数字先取完，b右侧补零 if(i>=pa->l+k)///a数字先取完，a右侧补零 ta=0; ans->s[i]=(ta+tb+cc)%10; cc=(ta+tb+cc)/10; } if(cc) ans->s[i++]=cc;//有进位，则存入数组末位 ans->l=i;}
3.完整代码
#include<stdlib.h>#include<cstring>#include<iostream>using namespace std;//定义结构体#define M 100char sa[1000];char sb[1000];typedef struct _Node{ int s[M];//数组，倒序存储大数 int l; int c;}Node, *pNode;//划分函数void cp(pNode src, pNode des, int st, int l){ //src表示待分解的数的结点，des表示分解后得到的数结点 //st表示从src结点数组中取数的开始位置，l表示取数长度 int i, j; for (i = st, j = 0; i<st + l; i++, j++) { des->s[j] = src->s[i];//从src节点数组中st位置开始取l个数 } des->l = l; des->c = st + src->c;//des次幂等于开始取数的位置加上src次幂。}//相加void add(pNode pa, pNode pb, pNode ans){ //程序调用时把a、b的地址传递给pa、pb参数，表示待合并的两个数 //ans记录结果 int i, cc, k, palen, pblen, len; int ta, tb; pNode temp; if ((pa->c)<(pb->c))//交换保证a的次幂大 { temp = pa; pa = pb; pb = temp; } ans->c = pb->c;//结果的次幂为两个数中较小数的次幂 cc = 0;//初始化进位为0 k = pa->c - pb->c;//k为a左侧需要补零的个数 palen = pa->l + pa->c;//a数加上次幂的总长度 pblen = pb->l + pb->c;//b数加上次幂的总长度 if (palen>pblen) len = palen; else len = pblen; for (i = 0; i<len - ans->c; i++) //结果的长度最长为pa，pb之中的最大长度减去最低次幂 { if (i<k) ta = 0; else ta = pa->s[i - k];//次幂高的补0，大于低的长度后与0进行计算 if (i<pb->l) tb = pb->s[i]; else tb = 0; if (i >= pa->l + k) ta = 0; ans->s[i] = (ta + tb + cc) % 10; cc = (ta + tb + cc) / 10; } if (cc) ans->s[i++] = cc; ans->l = i;}void mul(pNode pa, pNode pb, pNode ans){ int i, cc, w; int ma = pa->l >> 1, mb = pb->l >> 1; //长度除2 Node ah, al, bh, bl; Node t1, t2, t3, t4, z; pNode temp; if (!ma || !mb) //如果其中个数为1 { if (!ma) //如果a串的长度为1，pa,pb交换，pa的长度大于等于pb的长度 { temp = pa; pa = pb; pb = temp; } ans->c = pa->c + pb->c; w = pb->s[0]; cc = 0; //此时的进位为c for (i = 0; i < pa->l; i++) { ans->s[i] = (w*pa->s[i] + cc) % 10; cc = (w*pa->s[i] + cc) / 10; } if (cc) ans->s[i++] = cc; //如果到最后还有进位，则存入结果 ans->l = i; //记录结果的长度 return; } //分治的核心 cp(pa, &ah, ma, pa->l - ma); //先分成4部分al,ah,bl,bh cp(pa, &al, 0, ma); cp(pb, &bh, mb, pb->l - mb); cp(pb, &bl, 0, mb); mul(&ah, &bh, &t1); //分成4部分相乘 mul(&ah, &bl, &t2); mul(&al, &bh, &t3); mul(&al, &bl, &t4); add(&t3, &t4, ans); add(&t2, ans, &z); add(&t1, &z, ans);}int main(){ Node ans, a, b; cout << "输入大整数 a:" << endl; cin >> sa; cout << "输入大整数 b:" << endl; cin >> sb; a.l = strlen(sa);//sa,sb以字符串进行处理 b.l = strlen(sb); int z = 0, i; for (i = a.l - 1; i >= 0; i--) a.s[z++] = sa[i] - '0'; //倒向存储 a.c = 0; z = 0; for (i = b.l - 1; i >= 0; i--) b.s[z++] = sb[i] - '0'; b.c = 0; mul(&a, &b, &ans); cout << "最终结果为："; for (i = ans.l - 1; i >= 0; i--) cout << ans.s[i]; //ans用来存储结果，倒向存储 cout << endl; system("pause"); return 0;}
4.复杂度分析
递推可得，T(n)=4x(Tn/2x)+(2x-1)O(n)。地推最终规模为1，令n=2x，则x=logn，那么有：
T(n)=n2
