vlambda博客
学习文章列表

大数乘法 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*max_length+1;++i){
        //将结果从临时数组中复制出来
            result[i] = temp_result[i];
        }
    }

至此，大数乘法已经成功实现，最后，不要忘记释放内存：

     //回收动态分配的内存(动态分配内存非常危险)
    for(index = 1;index<10;index++){
        //PrintNUM(tmp_res[index]);
        free(tmp_res[index]);
    }

给出一张运行截图，大家可以寻找工具检查计算是否正确：

为了方便大家验证，我们把算式列在下面：

1234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890
*
9876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210
= 12193263113702179522618503273386678859451150739156363359236761164455788599298790108215200135650052123609205801112635258986434993786160646167367779295611949397448712086533622923332237463801111263526900

以下是完整的C实现：

#include<cstdio>
#include<cstdlib>
#define MAX_NUM_LENGTH 300
short *a,*b,*result;

//读取一个大数,输入的最后一个值应该保存在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;
    }
}
//打印这个大数（调试模式）
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]);
}
//打印这个大数（观察效果）
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 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;
    }
}

//大数乘法 可以基于大数加法实现
void superMUL(const short *a,const short *b,short *result,int max_length = MAX_NUM_LENGTH){
    //存储a从0乘到9的结果，其中乘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];
        }
    }
    //----------------以上是准备工作--------------


    //核心步骤
    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;
        superADD(result,tmp_res[b[index]],temp_result,index);
        int i;
        for(i=0;i<2*max_length+1;++i){
            result[i] = temp_result[i];
        }
    }

     //回收动态分配的内存(动态分配内存非常危险)
    for(index = 1;index<10;index++){
        //PrintNUM(tmp_res[index]);
        free(tmp_res[index]);
    }
}



int main(){
    //为运算分配空间
    a = (short*)malloc(MAX_NUM_LENGTH*sizeof(short));
    b = (short*)malloc(MAX_NUM_LENGTH*sizeof(short));
    result = (short*)malloc((2*MAX_NUM_LENGTH+1)*sizeof(short));
    ReadNUM(a);
    ReadNUM(b);
    //PrintNUM(a);
    //superADD(a,a,result,3);
    //PrintNUM(result,2*MAX_NUM_LENGTH+1);
    //superMUL(a,a,result);
    //释放分配的空间
    superMUL(a,b,result);
    PrintNUM(result);
    free(a);
    free(b);
    free(result);
}


推荐阅读

[5.05] 暗喻幻想港中35周年限定版1.03+DLC+金手指+王中王存档 [5.05] 暗喻幻想港中35周年限定版1.03+DLC+金手指+王中王存档
C语言再学习 -- 负数 C语言再学习 -- 负数

相关文章