高精度乘法

背景

高精度乘法是指两个非常大的整数相乘的计算方法，传统的乘法算法不适合处理太大的整数。举个例子，计算两个200位数的乘积，不论是int类型还是long long类型都会溢出。因此需要用高精度乘法来完成大数乘法的计算

代码介绍

本文介绍的是一种使用C++实现大整数相乘的方法。采用的方法是将两个大整数的每一位分别存入两个数组中，然后逐位相乘，结果再存入结果数组中，最后将结果数组逆序输出即可

优点

  1. 可以计算较大的整数相乘，不会受到int类型变量的限制
  2. 避免了精度损失的问题

缺点

  1. 时间复杂度较高，当两个数长度相等时，时间复杂度为O(n^2)，而当两个数长度不相等时，时间复杂度为O(m*n)，其中m和n分别为两个数的长度。所以比较适合计算中小规模的数字
  2. 代码实现中使用了大量的数组操作，可能会浪费大量的空间
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<iostream>
#include<cstring>

using namespace std;

void rev(int fir[], int sec[], string a, string b)  // 反转存储函数
{
    for(int i=0; i<a.length(); i++)  // 将字符串 a 存储到 fir 数组中
    {
        fir[a.length()-i-1] = a[i] - '0';  // 将字符转化为数字，存储到对应位置上（如 "123" 存储为 {3, 2, 1}）
    }
    for(int i=0; i<b.length(); i++)  // 将字符串 b 存储到 sec 数组中
    {
        sec[b.length()-i-1] = b[i] - '0';
    }
}

int main()
{
    string a, b;
    int fir[2002], sec[2002], ans[4005], MaxLen, x, AnsLen;

    while (cin>>a>>b)
    {
        MaxLen = max(a.length(), b.length());  // 计算两个数的最大长度，用于数组的初始化
        AnsLen = a.length() + b.length();  // 两个数乘积的最大位数是这两个数的位数之和

        for(int i=0; i<MaxLen; i++)  // 初始化，每一位的初始值为 0
        {
            fir[i] = 0;  
            sec[i] = 0;
        }
        for(int i=0; i<=AnsLen; i++)
        {
            ans[i] = 0;
        }
        
        rev(fir, sec, a, b);  // 反转存储到数组中

        x = 0;  // 进位初始化为 0
        for(int i=0; i<a.length(); i++)  // 从低位到高位依次计算乘积
        {      
            x = 0;  // 每开始循环一次，进位都初始化为 0，保证没有上一位的进位
            for(int j=0; j<b.length(); j++)                              
            {
                ans[i+j] = fir[i] * sec[j] + ans[i+j] + x;  // 计算当前这一位上，所有可能的进位（包括上一位和当前位）和该位已经有的值的和
                x = ans[i+j] / 10;  // 取得进位
                ans[i+j] %= 10;  // 取得该位的值
            }   
            ans[i+b.length()] = x;  // 如果有最高位要进位，将进位加到数组的下一位
        }

        while (ans[AnsLen]==0 && AnsLen!=0)  // 去除结果前导0
        {
            AnsLen--;
        }

        for(int i=AnsLen; i>=0; i--)  // 从高位到低位输出结果
        {
            cout << ans[i];
        }

        cout << endl;
    }
    return 0;
}

rev函数作用

代码原理

分析第41行到51行代码的循环过程：

1
2
3
4
5
6
7
8
9
10
11
for(int i = 0 ; i < a.length() ; i ++ )
       {
           x=0 ;
           for(int j = 0 ; j < b.length() ; j ++)
           {
               ans[i+j] = fir[i] * sec[j] + ans [i+j] + x ;
               x = ans[i+j] / 10 ;
               ans[i+j] % = 10 ;
           }
           ans[i+b.length()] = x ;
       }

首先，这里搭配了一个变量 x 用来存储进位，最开始为 0。先计算fir[i] * sec[j]的值
在相乘时，把进位 x 加上原本在这一位的值（第一次ans [ i+j ] 和 x 都等于 0），即：

1
ans[i+j] = fir[i] * sec[j] + ans [i+j] + x ;

然后，把余数存入 ans 数组中，再利用除法计算出下一次进位的值x
注：结束内循环后，还要将进位 x 存储至数组的下一位（不然错的离谱 计算2*5得出来的是0），即：

1
ans[i+b.length()] = x ;

需要注意的点：

  • 在这个代码段中，ans 一开始应该被初始化为 0。否则，如果有之前的结果则会影响到当前的计算
  • 在计算结束后，可能存在最高位进位，也就是 ans 的最高位有值，所以 ans[ i+b.length() ] = x ; 必不可少
  • 实际上，我们最开始并不知道最高位是否有值。所以，最后的数组 ans 的长度需要提前预留，才能够保证能够存储下所有的位数

优化与改进

  • 快速傅里叶变换算法（FFT）
  • Karatsuba 乘法
  • Strassen 算法
  • Toom-Cook 算法
    （在写博客查找资料的时候看到的，我看不懂 但我大受震撼😨😨）