二进制高精度，ACMer 必知必会（不是）的算法

先说几句废话。

众所周知，遇到高精度题，（有的人赛后对线出题人），有的人使用 Java / Python，有的人直接高精度板子开冲。Java 的缺点是学习成本高、代码写起来繁琐，而 Python 的缺点是其运行速度（其实 Pypy 挺快的）。由于种种原因，我们仍然不能抛弃 C++ 高精度板子。

在网上的高精度板子大致分为几个流派：存储结构有不压位的、压 3 位的、压 9 位的，乘法的时候有暴力、FFT、NTT。曾经的我以为乘法暴力就完事，（事实上正经比赛暴力真的完事），有一天练习时我被卡 TLE 了，最后用了 Java 才解决问题。痛定思痛，我决定打造一个 ACM 界最牛逼（并不）的高精度板子。

我偶然发现，Java 的大数类 (BigInteger) 是 Java 实现的。既然如此，我把这部分代码翻译到 C++ 不就变成高精度板子了吗？

Java 大数类的实现有几个很不一样的地方。

第一个是二进制存放数据，每个比特都没有浪费。具体实现是用 int 数组（Java 没有无符号数）存放。好处很明显，十进制高精度运算的时候，必然伴随着大量整除运算和取模运算，这会成为性能瓶颈，二进制就没这问题。但是缺点是输入输出时需要二进制和十进制之间进行转换。我读了一下 Java 源码，十进制转二进制的复杂度是 $O(n^2)$ ，二进制转十进制没读懂，估计也是这个复杂度。实测十万位的转换已经需要几秒时间了。

第二是乘法用了朴素算法 $O(n^2)$ 、Karatsuba $O(n^{\log_2 3})\approx O(n^{1.58})$ 、Toom Cook-3 $O(n^{\log_3 5})\approx O(n^{1.46})$ 三种算法，看情况选择使用哪个。相比于 FFT / NTT，这几个算法的实现更加贴近二进制。复杂度虽然高，但是实际测试的时候常数极小，优势非常明显。

因此二进制高精度适用的场景是，有大量乘法，但是输入输出的位数不能太大（二进制输入输出除外）。当然前提是允许贴板子，如果是真的比赛，一般情况下十进制高精就能过，二进制板子太长反而浪费时间。

然后说一下实现细节。

类似 Java，用 int 来保存符号（三个可能的值，-1, 1, 0 分别对应正数、负数、零），用 vector<unsigned> 来保存这个数的绝对值，类似原码的存储。（用 vector 是因为懒得写 delete，而且能加长；Java 源码是定长的）

struct big {
    using uint = unsigned;
    using ull = uint64_t;
    using vtr = vector<uint>;

    int sign; // 1 表示正数，-1 表示负数，0 表示等于 0
    vtr mag; // 存放绝对值
};

首先是十进制字符串转换到二进制的问题。Java 的实现中，先估计存下这个数需要的 int 的个数，进行 mag 的一个空间申请。然后每 9 个十进制位一组（比如 s[9k .. 9k+8]），每次让 mag 乘以 $10^9$ 再加上 s[9k .. 9k+8]。

Java 实现有更强的兼容性，我翻译时简化了很多，如下：（这个 Inplace 是原地操作的意思）

static uint parseInt(const string &s); // string 转换为 uint，略
static void mulInplace(vtr &x, uint y); { // 高精度乘单精度，略
static void addInplace(vtr &x, uint y); // 高精度加单精度，略
explicit big(string val) { // 用 string 构造
    const uint len = val.size();
    sign = (val[0] == '-' ? -1 : 1);
    uint cursor = (val[0] == '-');
    uint groupLen = (len - cursor - 1) % 9 + 1;
    while (cursor < len) {
        string group = val.substr(cursor, groupLen);
        cursor += groupLen;
        mulInplace(mag, 1000000000);
        addInplace(mag, parseInt(group));
        groupLen = 9;
    }
    if (mag.size() == 0) sign = 0;
}

二进制转换到十进制，源码有点复杂，我没绕清楚。但是可以把十进制转二进制反着来做，即先实现高精度对单精度的乘除和取模，然后每次除以 $10^9$ ，9 位 9 位地拿到十进制。

static uint divModInplace(vtr &x, uint m); // 高精度整除单精度，返回余数，略
string toString() const { // 转换为 string
    if (sign == 0) return "0";
    string result;
    vtr t = mag;
    while (t.size()) {
        string k = to_string(divModInplace(t, 1000000000));
        if (t.size()) k = string(9 - k.size(), '0') + k;
        reverse(k.begin(), k.end());
        result += k;
    }
    if (sign == -1) result += '-';
    reverse(result.begin(), result.end());
    return result;
}

高精度加、减法，这很简单，直接略。

最后是二进制高精度的精髓，即乘法。如果规模比较小，朴素乘法 (Grade-School Algorithm) 显然是首选，如下：

static vtr mul(const vtr &x, const vtr &y) { // 高精度乘法 Grade-School Algorithm
    vtr z(x.size() + y.size());
    for (uint i = 0; i < x.size(); i++){
        ull carry = 0;
        for (uint j = 0; j < y.size(); j++) {
            carry += (ull)x[i] * y[j] + z[i + j];
            z[i + j] = carry;
            carry >>= 32;
        }
        z[i + y.size()] = carry;
    }
    adjust(z); // 删除前导 0
    return z;
}

卡拉苏巴算法 (Karatsuba Algorithm) 是一个分治算法，它每次将两个乘数 x, y 分成两个部分，高位和低位，然后进行一些计算。这个相关资料挺多，我不详细讲了。

Java 的乘法还实现了 Toom Cook-3，但是卡拉苏巴已经够用，我就不翻译了。

卡拉苏巴实现的时候，我设置为如果朴素算法规模不超过 512 就用朴素算法实现，否则分治。

static void addInplace(vtr &x, vtr y, int sign = 1); // 高精度加、减高精度，sign 为 -1 表示减法，且必须满足 x > y，略
static void shiftLeft32Inplace(vtr &mag, uint nInts); // 左移 32 * nInts 位，略
static vtr Karatsuba(const vtr &x, const vtr &y) { // 高精度乘法 Karatsuba Algorithm
    if (x.size() * y.size() <= 512) { return mul(x, y); }
    ull half = (max(x.size(), y.size()) + 1) / 2;
    vtr xl(x.begin(), x.begin() + min(half, x.size()));
    vtr xh(x.begin() + min(half, x.size()), x.end());
    vtr yl(y.begin(), y.begin() + min(half, y.size()));
    vtr yh(y.begin() + min(half, y.size()), y.end());
    vtr p1 = Karatsuba(xh, yh);
    vtr p2 = Karatsuba(xl, yl);
    addInplace(xh, xl); addInplace(yh, yl);
    vtr p3 = Karatsuba(xh, yh); // 接下来计算答案 p1 = p1 * 2^(64h) + (p3 - p1 - p2) * 2^(32h) + p2
    addInplace(p3, p1, -1); addInplace(p3, p2, -1);
    shiftLeft32Inplace(p1, half);
    addInplace(p1, p3);
    shiftLeft32Inplace(p1, half);
    addInplace(p1, p2);
    return p1;
}

什么，你还想要除法？（出门左转 Python）现在还没搞，如果实现起来比较简单的话我还会回来更新的。

然后说一下效果，就那题（不说哪题了，丢人），十进制板子的朴素乘法和 FFT 都 TLE，Java 1913ms，二进制板子 356ms。（虽然我自带常数，别人直接莽都能过，但不影响二进制板子牛逼鸭）

以上。

← ACM 板子卡常：关于对常量取模的优化→