0x03 高精度运算#

The art of programming is the skill of controlling complexity.

—Marijn Haverbeke

备注

高精度运算（Arbitrary-precision arithmetic） 是指在计算机中进行数字运算时，使用一种算法或数据结构，可以支持更高位数的数字运算。通常情况下，计算机中使用的数据类型有其固定的长度，例如，32 位整数（int32）的长度为 32 个二进制位。而高精度运算则允许处理更大的数字，可能有数百位或数千位。需要实现高精度运算的原因有很多，其中最主要的原因是在某些应用程序中需要处理非常大的数字，例如大型科学计算、加密算法、货币计算、精度要求较高的统计分析等。在这些情况下，如果使用传统的数据类型和算法进行计算，可能会导致精度丢失或计算错误。因此，使用高精度运算可以确保计算的准确性，并提高计算效率和可靠性。

💡 在进行高精度计算时，通常将每个数字的各个位数按照从低位到高位的顺序进行存储，这是因为这种存储方式更符合我们进行手算的习惯，也更容易理解和计算。与此同时也能够让权值位始终保持对齐，方便模拟计算过程。

注意

这里更多讨论的是高精度整数的运算（大数 Big Number），而不是高精度浮点数的运算；
本文中的高精度整数指的是 非负整数，即大于等于 0 的整数；
本文中的高精度整数使用 vector<int> 来表示，其中每个元素表示一个位数，
- 例如 123 表示为 [3, 2, 1] ；
- 例如 123456789 表示为 [9, 8, 7, 6, 5, 4, 3, 2, 1] ；

读入与还原#

通常题目给出的大数都是以字符串的形式给出的，因此我们需要将其转换为 vector<int> 的形式。

vector<int> read(string &numString) { // E.g: 123456789
    vector<int> num;
    for (int i = numString.size() - 1; i >= 0; --i)
        num.push_back(numString[i] - '0');
    return num;  // [9, 8, 7, 6, 5, 4, 3, 2, 1]
}

最终要能够解析还原回字符串：

string parse(vector<int> &num) {
    string numString = "";
    for (int i = num.size() - 1; i >= 0; --i)
        numString += num[i] + '0';
    return numString;  // "123456789"
}

高精度加法#

基本思路：模拟手算过程，从低位到高位逐位相加，下面代码中的 tmp 变量既可以存放加法结果，也可以表示进位（carry）。如果最高位加法有产生进位，则将其也加入到结果中。

vector<int> add(vector<int> &a, vector<int> &b) {
    vector<int> c;
    int tmp = 0;  // store carray or sum
    for (int i = 0; i < a.size() || i < b.size(); ++i) {
        if (i < a.size()) tmp += a[i];
        if (i < b.size()) tmp += b[i];
        c.push_back(tmp % 10);
        tmp /= 10; // carry
    }
    if (tmp) c.push_back(1);
    return c;
}

LeeCode 415 AcWing 791

高精度减法#

基本思路：模拟手算过程，从低位到高位逐位相减，下面代码中的 tmp 变量既可以存放减法结果，也可以表示借位（borrow）。值得注意的是，相较于加法，减法由于不满足交换律，因此为了简化讨论情况，我们通过 geq 函数来比较两个数的大小，人为地保证后续计算的 a 大于等于 b，然后再进行减法运算。如果 a 小于 b，则交换 a 和 b 的位置（有标志变量 swap），最后再加上一个负号。另外注意减法 需要处理前导 0. 🔍︎ 例如 a = 123456789, b = 123456780，a - b == 9, vector<int> c == [9, 0, 0, 0, 0, 0, 0, 0, 0];

bool geq(vector<int> &a, vector<int> &b) {
    while (a.back() == 0 && a.size() > 1) a.pop_back();
    while (b.back() == 0 && b.size() > 1) b.pop_back();
    
    if (a.size() != b.size()) return a.size() > b.size();
    for (int i = a.size() - 1; i >= 0; --i)
        if (a[i] != b[i]) return a[i] > b[i];
    return true;
}

vector<int> sub(vector<int> &a, vector<int> &b, bool swap = false) {
    // make sure a is greater than or equal with b
    if (!geq(a, b)) return sub(b, a, true);

    vector<int> c;
    int tmp = 0;
    for (int i = 0; i < a.size() || i < b.size(); ++i) {
        if (i < a.size()) tmp += a[i];
        if (i < b.size()) tmp -= b[i];
        c.push_back((tmp + 10) % 10);
        tmp = tmp < 0 ? -1 : 0;  // borrow
    }

    // handle with leading zero and negative cases
    while (c.back() == 0 && c.size() > 1) c.pop_back();
    if (swap) c.back() *= -1;
    return c;
}

AcWing 792

高精度乘法#

基本原理：模拟竖式乘法 (AxB=C) ——

（子功能实现）将 B 按十进制位拆成多项，分别与 A 相乘得到候选 candidate;
（问题转化）计算 C 的过程即计算多项 candidate 错位求和，模拟手算加法；

注意

不同项错位求和时，对应下标变化规律性极强，建议使用具体实例模拟一下计算过程辅助理解。以及实际的求和次数由 candidates.front().size() 决定（而非 a.size() 值）；

vector<int> mul_per_digit(vector<int> &a, int b) {
    vector<int> candidate;  
    int tmp = 0;
    for (int i = 0; i < a.size(); ++i) {
        tmp += a[i] * b;
        candidate.push_back(tmp % 10);
        tmp /= 10;
    }
    if (tmp) candidate.push_back(tmp);
    return candidate;
}

vector<int> mul(vector<int> &a, vector<int> &b) {
    vector<int> c;
    vector<vector<int>> candidates;
    for (int i = 0; i < b.size(); ++i) {
        candidates.push_back(mul_per_digit(a, b[i]));
    }
    int tmp = 0;
    for (int i = 0; i < candidates.front().size() + b.size(); ++i) {
        for (int digit = i, idx = 0; idx < b.size(); ++idx, --digit) {
            if (digit >= 0 && digit <= a.size())
                tmp += candidates[idx][digit];
        }
        c.push_back(tmp % 10);
        tmp /= 10;
    }
    if (tmp) c.push_back(tmp);
    while (c.back() == 0 && c.size() > 1) c.pop_back();
    return c;
}

Wikipedia LeeCode 43 AcWing 793

高精度除法#

基本原理：模拟竖式除法（A/B=C…R），辗转相减，将除法转换为多次减法运算——

🔍︎ 例如计算 230000027 / 23 时, 中间过程会出现许多 remain 为 0 或包含前导 0 的情况，需要在 geq 和 sub 中进行处理，同时起到剪枝的效果。

复用了高精度减法中的 geq 和 sub 函数（由于借位的存在，一定要处理前导 0）； 🔍︎ 例如计算 230000027 / 23 时, 中间过程会出现许多 remain 为 0 或包含前导 0 的情况，需要在 geq 和 sub 中进行处理，同时起到剪枝的效果。
竖式除法的每一小步，都是用当前余数 reamain 尝试与除数 b 相除，得到当前最高位商和新余数；
用减法运算代替除法，当前的 reamin 减去除数 b，直到 remain 的长度小于 b, 减的次数即当前位的商；
如果 remain 的长度小于 b，则将 a 的下一位补充到 remain 的最后，商位补 0, 直到能继续减法运算；
除法过程中，如果在最后一项产生了借位，则计算完当前余数后，就不用再继续计算了。

vector<int> div(vector<int> &a, vector<int> &b, vector<int> &remainder) {
    if (a.size() < b.size()) {
        remainder = a;
        return vector<int> (1, 0);
    }
    
    vector<int> c;
    int tmp = 0;
    
    vector<int> remain(a.end() - b.size(), a.end());
    
    int cur = a.size() - b.size(); // current digit in dividend to be handled
    while (cur >= 0) {

        while (cur >= 1 && !geq(remain, b)) {
            c.push_back(0);  // borrow
            remain.insert(remain.begin(), a[--cur]);  // shift remain item
        }
        
        while (geq(remain, b)) {  // sub multi-times
            remain = sub(remain, b);
            tmp += 1;
        }
        c.push_back(tmp);
        tmp = 0;
        
        if (cur == 0) break; // when borrowed the last digit, jump next step
        remain.insert(remain.begin(), a[--cur]); // supplement the remainder
    }

    remainder = remain;
    
    reverse(c.begin(), c.end());
    while (c.back() == 0 && c.size() > 1) c.pop_back();
    
    return c;
}

Wikipedia AcWing 794

警告

另一种辗转相减的做法是，先将除数乘以 10 的幂，使得除数和被除数的位数相同，然后再仿照上面的思路不断进行减法与“去”位（对除数），直到不能再去位。虽然总是能取得一样的结果，但是这种做法的复杂度取决于被除数的位数，而原方法复杂度取决于除数的位数，显然原方法更优。

0x03 高精度运算

目录

0x03 高精度运算#

读入与还原#

高精度加法#

高精度减法#

高精度乘法#

高精度除法#