大整数乘法
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 100
char 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
文章评论