高精度算法处理四则运算

前言

我们都知道，在计算机程序中让两个数相加，一般直接输入 sum = a + b 即可。当然，前提是加数与和没有超过限定的数据类型范围。在现代 32 位或 64 位系统中，C/C++ 的 int 通常取值范围为±21亿，而 long long 更是能达到±2的63次方。

如果数字超过了这个范围，我们应该怎样进行计算呢？

高精度加法

所谓“高精度算法”，实际上是使计算机模拟我们小学就学过的竖式计算，来进行加、减、乘、除的算法。

为此，我们需要简单复习一下小学知识。

这里有两个数 114514 和 666 ，我们想计算两数相加，应该怎么做？很简单，列一个竖式，将两数从个位开始相加，逢十进一，最后便能得到结果。

  1 1 4 5 1 4
+       6 6 6
-------------
  1 1 5 1 8 0
      ^   ^   --进位

但是要让计算机理解这一过程，就不是那么简单了。

1.数据存储

想要实现竖式计算，我们不能简单地存放数字，我们希望数字可以一位一位地取出、计算、存入，此时数组是最适合的容器。

    int a[510]={0},b[510]={0},sum[510]={0};
    //数字位数越大，数组需要开的位数越大

这带来了一个新的问题：如何将超长的输入数字按位存入数组中？

我们可以使用字符串接收数字，并用循环将其存入数组。

	char s1[510],s2[510];
    scanf("%s %s",s1,s2);
    //计算字符串的有效长度，需要引入string.h
    int len1=strlen(s1);
    int len2=strlen(s2);
    //分别倒序存入数组
    for(int i=0;i<len1;i++){
        a[i] = s1[len1-i-1] - '0';
    }
    for(int i=0;i<len2;i++){
        b[i] = s2[len2-i-1] - '0';
    }

当然，如果使用C++也能用vector，这样更方便。

2.数字计算

在上面的代码中，为什么我们要将数字倒序存入？

这是因为竖式计算时，我们是从个位开始运算的，每次运算需要注意进位。

倒序存储之后，我们先计算 a[1] + b[1] ，再计算 a[2] + b[2] ······这样就能完成整个竖式。

我们还需要计算循环的次数，这是由两位中更长的那个数字的位数决定的。

	//取循环边界
    int lenth = (len1 > len2) ? len1 : len2;
    //运算并进位
    for(int i=0;i<lenth;i++){
        sum[i] += (a[i] + b[i]);
        if(sum[i] >= 10){ //进位处理
            sum[i+1]++;
            sum[i] %= 10;
        }
    }

你可能会担心“如果数字与数组未被写入的地方进行了计算怎么办？”。其实在数组初始化时，我们便使数组所有位为0了。

3.输出

先等等，我们还不能直接输出。

假如两数相加，最高位发生了进位，则输出循环的边界必须加一，否则最高位将被截去。

这也是为何数组开的位数最好大于数字的位数。我们只需要用循环计算的位数检测最高位，若不为0，则说明发生了进位。

	//最高位有进位则加一
    if(sum[lenth] != 0) 
        lenth++;
    //倒序输出
    for(int i=lenth-1;i >= 0;i--){
        printf("%d",sum[i]);
    }

完整代码

#include<stdio.h>
#include<string.h>
int main(){
    int a[510]={0},b[510]={0},sum[510]={0};
    char s1[510],s2[510];
    scanf("%s %s",s1,s2);
    int len1=strlen(s1);
    int len2=strlen(s2);
    for(int i=0;i<len1;i++){
        a[i] = s1[len1-i-1] - '0';
    }
    for(int i=0;i<len2;i++){
        b[i] = s2[len2-i-1] - '0';
    }
    int lenth = (len1 > len2) ? len1 : len2;
    for(int i=0;i<lenth;i++){
        sum[i] += (a[i] + b[i]);
        if(sum[i] >= 10){
            sum[i+1]++;
            sum[i] %= 10;
        }
    }
    if(sum[lenth] != 0) 
        lenth++;
    for(int i=lenth-1;i >= 0;i--){
        printf("%d",sum[i]);
    }
    return 0;
}

相关题目：洛谷P1601

高精度减法

高精度减法与加法一样，使用模拟竖式的方式进行运算。将两数从个位开始相减，若当前位不够减，则向前一位借1。

不过减法比加法多一重考虑：如果结果为负数应该怎么办？

例如 114514 和 666 相减得 113848 ，若将两数交换，我们很容易得结果为 -113848 。到这里答案已经很明显了，我们只需要保证总是大数减去小数，如果数字反转，则在结果前加上 - 即可。

所以在接收数字后，需要对两数比较大小，若被减数小于减数，则交换。

    //我这里使用指针进行交换，也可以用数组逐个交换
    int *tmp;
    int *pa = a;
    int *pb = b;
    char flag = '+';
    if(compare(a,b,len1,len2) == -1){
        flag = '-';
        tmp = pa;
        pa = pb;
        pb = tmp;
        len1 = len2;//注意循环计算次数也需要取更大的位数
    }

比较功能单独写成函数：

    int compare(int a[], int b[], int len1, int len2) {
        if (len1 != len2) return len1 > len2 ? 1 : -1;
        // 从最高位（数组末尾）开始往前比
        for (int i = len1 - 1; i >= 0; i--) {
            if (a[i] != b[i]) {
                return a[i] > b[i] ? 1 : -1;
            }
        }
        return 0;
    }
    //实际上可能有更简便的方法XD

需要注意，减法是可能会减小位数的！两数相等时甚至结果为0，我们当然不可能输出 000000 这样奇怪的数字。所以我们需要去除前导零，并重新取循环边界。

    int index = 0;
    for(int i=len1-1;i>=0;i--){
        if(min[i] != 0){
            index =i;
            break;
        }
    }

完整代码

#include<stdio.h>
#include<string.h>
int compare(int a[], int b[], int len1, int len2) {
    if (len1 != len2) return len1 > len2 ? 1 : -1;
    for (int i = len1 - 1; i >= 0; i--) {
        if (a[i] != b[i]) {
            return a[i] > b[i] ? 1 : -1;
        }
    }
    return 0;
}

int main(){
    int a[10100]={0},b[10100]={0},min[10100]={0};
    char s1[10100],s2[10100];
    scanf("%s %s",s1,s2);
    int len1 = strlen(s1),len2 = strlen(s2);
    for(int i=0;i<len1;i++){
        a[i] = s1[len1-i-1] - '0';
    }
    for(int i=0;i<len2;i++){
        b[i] = s2[len2-i-1] - '0';
    }
    int *tmp;
    int *pa = a;
    int *pb = b;
    char flag = '+';
    if(compare(a,b,len1,len2) == -1){
        flag = '-';
        tmp = pa;
        pa = pb;
        pb = tmp;
        len1 = len2;
    }
    //运算并进行借位
    for(int i=0;i<len1;i++){
        min[i] += pa[i] - pb[i];
        if(min[i] < 0){
            min[i] += 10;
            min[i+1]--;
        }
    }
    //输出符号
    if(flag == '-')
        printf("-");
    int index = 0;
    for(int i=len1-1;i>=0;i--){
        if(min[i] != 0){
            index =i;
            break;
        }
    }
    for(int i=index;i>=0;i--){
        printf("%d",min[i]);
    }
    return 0;
}

相关题目：洛谷P2142

高精度乘法

（待续）