当前位置 博文首页 > kbtx的博客：大数乘法 C语言实现 在Code::Blocks 17.12下通过编
题目：实现两个100位正整数相乘，输出运算结果
本代码在Code::Blocks 17.12下编译通过
分析：
很明显，C语言内置的任何整数类型都无法直接满足题目的需求，因此我们要通过构造数组按位存储运算结果。为了节省内存，我们可以选择构造char或者short数组，考虑到char需要频繁地强制转换，我们本次采用short数组实现。
我个人习惯将数字的低位放在下标较小的位置，因此设计这样一个输入函数：
//读取一个大数,输入的最后一个值应该保存在a[0]中，倒数第二个在a[1]中，...最先输入的应该保存在a[n-1]中
void ReadNUM(short *a){
int pos = MAX_NUM_LENGTH - 1;
char input = '\0';
//确保数组不越界
while(pos&&(input = getchar())!='\n'){
//安全检查
if('0'<=input&&input<='9'){
input-='0';
a[pos--] = (short)input;
}else {
printf("number format exception caused by letter: %c\n",input);
}
}
int mov = 0;
++pos;
//将用户的输入移到前面
while(mov+pos<MAX_NUM_LENGTH){
a[mov] = a[mov + pos];
++mov;
}
while(mov<MAX_NUM_LENGTH){
a[mov++] = 0;
}
}
我们在处理用户输入的时候，把先输入的放在数组末尾，后输入的放在较靠前的位置，最后将前面多余的0都换到后面去，就能让输入按照期望排列。
如何验证呢？很简单，只要调用PrintNUM_dbg，就能看到数组中的内容了，当然，也可以直接打开调试器查看。
//打印这个大数（调试模式）
void PrintNUM_dbg(short *a,int max_length = MAX_NUM_LENGTH){
int pos_ptr = max_length-1;
while(a[pos_ptr]==0) --pos_ptr;
while(pos_ptr>=0){
printf("a[%d] = %d\n",pos_ptr,a[pos_ptr]);
// printf("%d",a[pos_ptr]);
--pos_ptr;
}
// printf("%d",a[pos_ptr]);
}
同时，为了方便观察计算结果，我们再增加一个输出函数PrintNUM，让数字按照我们的阅读习惯打印在屏幕上：
//打印这个大数（观察效果）
void PrintNUM(short *a,int max_length = MAX_NUM_LENGTH){
int edge = max_length-1;
//去掉多余的0
while(a[edge]==0) --edge;
while(edge>=0) printf("%d",a[edge--]);
printf("\n");
}
这些函数准备好后，就能实现大数加法了——我们的乘法建立在加法的基础上——我们先看看核心代码：
//大数加法——核心
void superADD(const short *a,const short *b,short *result,int max_length = MAX_NUM_LENGTH){
int res_max_length = 2*MAX_NUM_LENGTH+1;
short tmp = 0;
int num_pos_ptr = 0;
//此时 num_pos_ptr == offset
while(num_pos_ptr<max_length){
tmp = a[num_pos_ptr] + b[num_pos_ptr];
result[num_pos_ptr] += (tmp%10);
result[num_pos_ptr+1] += (tmp/10 + result[num_pos_ptr]/10);
//每一位的运算结果都可能大于10，因此要取余数
result[num_pos_ptr]%=10;
++num_pos_ptr;
}
result[num_pos_ptr]%=10;
}
核心代码充分体现了两数相加，按位对齐，满十进一的原则
在计算乘法的时候，我们可以先把 a 的0~9倍单独保存在一个二维数组中，根据 b 中每一位的数值，从二维数组取出该数值对应的行叠加（如果为0可直接跳过），这样就实现了用加法计算乘法。当然，这个时候的大数加法还涉及到移位，因此我们要给SuperADD增加一个参数offset，表示计算时要将b[0]与a[offset]（而不是a[0]）对齐。同时注意到这样的加法做完后，b的数值并未用完，这些未用上的数我们直接按位放到结果数组result中即可。
拓展后的大数加法如下：
//大数加法
void superADD(const short *a,const short *b,short *result,int offset = 0,int max_length = MAX_NUM_LENGTH){
int res_max_length = 2*MAX_NUM_LENGTH+1;
short tmp = 0;
int num_pos_ptr;
//将上次计算的结果清零
for(num_pos_ptr = 0;num_pos_ptr<res_max_length;++num_pos_ptr){
result[num_pos_ptr] = 0;
}
num_pos_ptr = 0;
//如果偏移量不为0，则a、b之间的顺序不可随意交换，否则结果可能出错
while(num_pos_ptr<offset){
result[num_pos_ptr] = a[num_pos_ptr];
++num_pos_ptr;
}
//此时 num_pos_ptr == offset
while(num_pos_ptr<max_length){
tmp = a[num_pos_ptr] + b[num_pos_ptr - offset];
result[num_pos_ptr] += (tmp%10);
result[num_pos_ptr+1] += (tmp/10 + result[num_pos_ptr]/10);
//每一位的运算结果都可能大于10，因此要求余数
result[num_pos_ptr]%=10;
++num_pos_ptr;
}
result[num_pos_ptr]%=10;
//此时 num_pos_ptr == max_length，但b[]中还有一部分数据还要加到结果中
while ((num_pos_ptr-offset) < max_length){
result[num_pos_ptr] = b[num_pos_ptr-offset];
++num_pos_ptr;
}
}
有了这样强大的大数加法，我们就能在此基础上设计大数乘法了，首先，用大数加法把a的2~9倍计算出来，计算2倍的时候依赖1倍和1倍，计算3倍的时候依赖1倍和2倍…，计算n倍的时候依赖1倍和n-1倍（0、1倍无需计算，甚至不用为0倍分配内存空间，给个空指针即可）：
short* tmp_res[10];
int index;
//0倍的结果无需存储
tmp_res[0] = NULL;
//动态分配内存
for(index = 1;index<10;index++){
tmp_res[index] = (short*)malloc((max_length+1)*sizeof(short));
}
//a的1倍直接确定
for(index = 0;index<max_length;index++){
tmp_res[1][index] = a[index];
}
tmp_res[1][index] = 0;
//逐一计算2~9倍的结果
for(index = 2;index<10;index++){
superADD(tmp_res[index-1],tmp_res[1],result,0,max_length+1);
int i;
for(i=0;i<max_length+1;i++){
tmp_res[index][i] = result[i];
}
}
所有的计算结果都保存在了tmp_res[][]中，注意千万不要访问tmp_res[0]，以免崩溃。
相比而言准备工作而言，核心步骤就显得简单多了，由于大数加法运行时会把结果数组清空，我们要额外申请一个临时结果数组用于保存运算结果，并在运算结束后将临时结果复制到结果数组，同时用结果数组参与下一次运算：
//核心步骤
short temp_result[2*max_length+1]={};
for(index=0;index<2*max_length+1;++index) result[index]=0;
for(index=0;index<max_length;++index){
if(b[index]==0) continue;
//结果数组result用于参与下一次运算，计算结果保存在临时结果数组中，循环次数恰好就是偏移量
superADD(result,tmp_res[b[index]],temp_result,index);
int i;
for(i=0;i<2
