C语言羁绊之高精度乘法计算

冷不防 2022-05-29 07:12 252阅读 0赞

很大一部分借鉴了（[C语言的高精度算法][C]）这一博客，你们可以去看看。欢迎指正！！！

## 1，定义 ##

对于计算机无法用普通数据类型（如：longint）表示的大整数进行乘法运算，称为高精度算法。这里的高精度乘法主要指按位模拟运算，实际上就是模拟乘法的过程，也就是笔算的过程。（你拿张纸就可以轻易的模拟出来，但是你原来可能没发现过其中的规律）。

## 2，原理 ##

既然是一个很大的数，我们便不能够在用简单的数据类型直接存储这些整数。我们自然可以得想到通过数组或字符串来存储数字。字符串的特点便于我们对高位整数的输入，而整型数组的简单遍历更利于每个位数的计算，因而我们结合两者的优点，不难得出高精度乘法的大致流程：

a,    通过两个字符串输入两个整数

b,    引入两个数组，将两个整数通过一定的运算，分别将每一位的数字存储进数组中；

c,    进行每一位的处理；

d,    处理进位；

e,    输出结果。

## 3，重要步骤分析    ##

#####     3.1    每一位的处理过程（好多在这小节不懂的疑问，在3.2便解决了） #####

这有点抽象，单是文字说明，我们或许不太清楚，为此，我们来举个小栗子。在coding 1中我们计算了123\*567的结果，到这里，好多人一头雾水，你告诉我这有啥用？小学乘法谁不会啊，你快告诉我该怎么写算法啊？别急别急，在这里，出现了一

//coding 1    求每一位的数值
              1   2   3
      *       5   6   7
      *--------------------------
              7   14  21
          6   12  18
     5   10   15   
    *--------------------------
     5   16   34  32  21

个我们需要注重理解的点，那就是结果中每一位值的求法，算法算法，肯定就是找规律列式子啊！那我们看上边的乘法有什么规律，好多人告诉我，没规律，那好，我们继续往下看coding2。

//coding 2    演示
                      a2       a1       a0
         *            b2       b1       b0
         *---------------------------------
                    a2b0     a1b0     a0b0
            a2b1    a1b1     a0b1
    a2b2    a1b2    a0b2         
         *---------------------------------
    c(4)    c(3)    c(2)     c(1)     c(0)

这时我们就应该可以看出规律了，原来结果数组c在的第i个元素的值为a和b数组下标和为i的值的和，即c\[i+j\] += a\[i\] +a\[j\]。

#####     3.2    处理进位 #####

在3.1中好多人对为什么要把乘起来的数加一块呢，其实这是我们没有进行处理进位操作，那怎么处理进位呢？那就是当前位数的值整除10所得的数加到更高位，对10取余，把剩下的数放在原来的位置，即可。看下图：我们把上边的运算结果拿下来![Image 1][]

，对各位21取整得2，取余得1，因此个位数为1，接下来十位数32加上个位的取整2为34，取整为3，取余为4，故十位是4..依此类推，最后得到的结果是69741，是不是很神奇呢。好了到此为止，高精度乘法的主要步骤已经讲完，下面我们进行代码的编写吧。

## 4，分部代码 ##

【注】分部代码大家可参考文章开头，结尾的整合代码我是通过不同的功能把它们做了一定的整合，有兴趣的小伙伴可以去看下。

#####     4.1    运算前的准备 #####

#include<stdio.h>
    #include<string.h>
    
    int main() {
        char number1[1500], number2[1500];
        scanf("%s%s", number1, number2);
        int n = strlen(number1), m = strlen(number2);
        int a[n], b[m];

上述代码使我们输入了两个整数，并且通过strlen函数确定了乘数的位数，并且将整形数组的长度同时定位好了。

我们接着写：

int i, j; 
        for (i = 0, j = n - 1; i < n; i++, j--) {
            a[i] = numberN[j] - '0';
        }
        for (i = 0, j = m - 1; i < m; i++, j--) {
            b[i] = numberM[j] - '0';
        }

此处循环的目的是将两个乘数的各位数拆开来存储进两个数组了，并且a\[0\]为个位，a\[1\]为十位，以此类推。此时高精度乘法运算前的准备已经做好了。之所以在这减去‘0’，是因为0的Ascll值为48，通过其他字符的Ascll减去0的就剩下多余的数字，由于0-9在字符表中连续，也即得到了整数0-9；

#####     4.2    一位一位的算 #####

看过3.1应该对此问不陌生，直接贴出代码如下

int c[3000];
    for (i = 0; i < 3000; i++) {
        c[i] = 0;
    }
    for (i = 0; i < n; i++) {
        for (j = 0; j < m; j++) {
            c[i + j] += a[i] * b[j];
        }
    }

#####     4.3    处理进位 #####

for (i = 0; i < n + m; i++) {
        if (c[i] >= 10) {
            c[i + 1] += c[i] / 10;
            c[i] %= 10;
        }
    }

#####     4.4    输出结果 #####

好了，现在我们要输出结果了。我们知道，现在c数组里储存着结果的各位数字，我们只需要按照正确的顺序把数字一个个print出来就可以了！

for (j = 2999; j > 0; j--) {
        if (c[j] != 0)
        break;
    }
    for (i = j; i >= 0; i--) {
    printf("%d", c[i]);
    }
    printf("\n");
    return 0;
    }

在这里我需要指出的是，因为c数组的长度是固定的，但我们并不知道最终的结果有多少位，而我们又可以看出结果应该从后往前print。所以在输出前需要用一个for循环确定一下结果的位数

## 5.整体代码 ##

/*************************
    *file name:高精度乘法计算 
    **************************/
    
    #include "stdio.h"
    #include "string.h"
    
    /*************************
    *函数名： init()
    *作用： 先将字符串的数组转至数字数组
    *参数：	*a - 存放整数的数组   *numberN -存放字符串的数组 	n-数组的长度 
    *返回值：无 
    *************************/
    
    init(int *a,char *c,int n){
    	int i,j;
    	for(i = 0,j=n-1;i<n;i++,j--){
    		a[i] = c[j] - '0';
    	}
    } 
    
    /*************************
    *函数名： init_c()
    *作用： 初始化数组c，将其所有元素设置为0 
    *参数：	*c - 存放乘法结果的数组   	n-数组的长度 
    *返回值：无 
    *************************/
    
    init_c(int *c,int n){
    	int i;
    	for(i=0;i<3000;i++){
    		c[i] = 0;
    	}
    } 
    
    /*************************
    *函数名： operation_c()-----重要 
    *作用： 算出c数组的每一位
    *参数：	*a - 存放整数的数组a  *b - 存放整数的数组b  *c - 存放结果的数组b 
    *  n-数组a的长度	m-数组b的长度 
    *返回值：无 
    *************************/
    
    operation_c(int *a,int *b,int *c,int n,int m){
    	int i,j;
    	for(i=0;i<n;i++){
    		for(j=0;j<m;j++){
    			c[i+j] += a[i]*b[j];
    		}
    	}
    } 
    
    /*************************
    *函数名： processing_carry()
    *作用： 处理c数组中的进位问题 
    *参数：	*c - 存放结果的数组c   n - 存放结果的数组长度 
    *返回值：无 
    *************************/
    
    processing_carry(int *c,int n){
    	int i;
    	for(i=0;i<n;i++){
    		if(c[i] >= 10){
    			c[i+1] += c[i]/10;
    			c[i] = c[i]%10;
    		}
    	}
    } 
    
    
    //主函数 
     int main(){
     	char numberN[1500],numberM[1500];
    	scanf("%s%s",numberN,numberM);
    	int n = strlen(numberN),m = strlen(numberM);
    	int a[n],b[m];
    	int i,j;
    
    	//init 初始化，先将字符串的数组转至数字数组 
    	init(a,numberN,n);
    	init(b,numberM,m);
    
    	int c[3000];
    	//初始化c数组 
    	init_c(c,m+n);
    	//计算出c每一位的值（没有考虑进位） 
    	operation_c(a,b,c,n,m); 
    	//处理进位 
    	processing_carry(c,n+m);
    	//由于大部分的运算不可能到3000位，因此我们为了减少遍历，加入了一个判空的操作
    	for(j=2999;j>0;j--){
    		if(c[j] != 0)
    		break;
    	}
    	//倒序输出我们的数组，别忘了，我们规定的是a[0]是个位 
    	for(i=j;i>=0;i--){
    		printf("%d",c[i]);
    	}
    	printf("\n");
     	return 0;
     }

\---------------------- **END**\-----------------------

[C]: http://blog.csdn.net/luojj26/article/details/49671121#t3
[Image 1]: