把自己的 个人C++17代码模板库 放在 github 后，发现没有 BigInt，于是有了这篇博客，随便搜了一下，发现都不够全面，或者说不够高效，于是就自己尝试一下。那么就有几个问题

• 用什么存数据
• 内部逻辑几进制
• 乘法和除法怎么实现
• 最终哪些功能要实现
• 与 Boost、Python，Haskell 的大数比较性能如何

代码仓库，这里就当作放文档的地方吧

存储

首先肯定会用类似多项式方式存大数，自然会想到用 vector<T>，现在问题是 \(T\) 是什么

• 不能是 bool，因为 vector<bool> 不是容器，水很深，我把握不住。
• char, short, int, long long 选什么呢？因为我要用 NTT，因此只能在 int 和 long long 中选择，但是如果用 long long 基础乘法时不可避免出现 __int128 十分影响效率，最终选择 int
• 有符号还是无符号：有符号，因为在出现 NTT 会出现减法，此时很可能就会模 \(2^{32}\) 直接爆炸

再用一个 flag 存储符号。

其实我是想用不定长的 bitset 即 boost::dynamic_bitset 来存的，但是，都用了 boost 为什么不用 boost 的里面的高精度呢？所以还是下次一定吧

用什么进制呢？起初我是想用 二进制，此时选择的最佳模数为 \(469762049 = 7 \cdot 2^{26} + 1\) 又由于 \(2^{2^{25}} \simeq 10^{10^7}\) ，所以数的十进制表示长度不能超过 \(10^7\)（其实如果超过了一次除法，甚至乘法估计也是跑不动的）。但是很快哈，十进制和二进制的转化就成为了瓶颈。所以即使要用二进制存也要先实现十进制。

进制转换

假设用十进制 vector<int> 保存大数，比如来了一个长度为 n 的 0-1 字符串，那么我强行补 0，让它变成 2 的幂次的长度，根据长度预处理 \(2^{2^{i}}\)(当作静态成员，所以一直往后添加即可），然后就然后递归求两个部分的值，前一部分乘以 某个 \(2^{2^i}\) 就可以，所以总复杂度 \(O(n \log^2 n)\)

这里其实也可以不限制，因为在求的时候给出即可，二进制转十进制用十进制存，十进制转二进制用二进制存

所以如果要互换，我们需要考虑两个版本，即写两个 B，但是 2进制可以特殊对待一下，因为可以用位运算，会快很多。所以要写两个版本：2 进制存的版本，B 进制存的版本（必须满足 \((B - 1)^2 N < M\)），但是没必要其实 取 \(B = 10\) 吧。

2 进制内最佳模数：\(469762049 = 7 \cdot 2^{26} + 1\)，原根为 3，最大长度为 \(2^{25}\)，值大约为 \(10^{10^7}\)

10 进制内最佳模数：\(754974721 = 45 \cdot 2^{24} + 1\)，原根为 11，最大长度为 \(2^{23}\) 值大约会 \(10^{8 \cdot 10^6}\)

逻辑

先继承 vector<int> 然后用 ngt 存储符号（ngt = true 表示为负数）

• 取负号，自己改变符号（为了高效），+ 也太鸡肋了就不搞了，判断是否相等
• 实现大小比较
• 实现加法减法
• 实现逻辑比较
• 用 NTT 实现乘法
• 用 牛顿法实现除法

由于 NTT 的使用中，能选取的最佳模数为 \(469762049 = 7 \cdot 2^{26} + 1\) 又由于 \(2^{2^{25}} \simeq 10^{10^7}\) ，所以数的十进制表示长度不能超过 \(10^7\)（其实如果超过了一次除法，甚至乘法估计也是跑不动的）

基础功能

• +=,-=,*=,/=
• ++,--(前缀)，后缀版本太蠢了
• 位运算
• 与基础数据交互，类型转化int, LL, string
• IO
• 支持 lg（2 为底数）

大数除法

参考洛谷的题解：https://www.luogu.com.cn/problem/solution/P5432

首先应用牛顿法：\(f(x) = \frac{1}{x} - b\)，即可知道迭代公式为：

当然也可以根据 \(|b x_n - 1| < \epsilon\) 则

即，我们可以始终保持 \(1 - \epsilon < b x_n < 1\) 并且给出了误差范围。关键问题是如果 \(b > 1\)，我们应该怎么存储 \(x_n\) 呢？

用小数

假设 \(b = b_0 + b_1 \cdot 10 + \cdots + b_{n - 1} 10^{n - 1}, 0 \leq b_i < 10, b_{n - 1} > 0\) ，我们处理 \(b' = \frac{b}{10^n}\)，即

那么此时 \(x_n\) 也可以写成此形式

但是我们要迭代时候截断 b’，否则复杂度就不行了。

注意到 \(b' < 1\) 因此 \(x_n > 1\)，若 \(-10^{-m} < b x_n - 1 < 0\)，则 \(-10^{-m}\frac{a}{b} < \frac{a}{b} - a x_n < 0\)，因此若 \(10^{-m} a < 1\) 即可停止。

然而如果按照这种方式存储 大小比较和减法 要重新写，挺麻烦的。因此我们转而

求 \(\frac{10^{2n}}{b}\)

最后各种办法无果，最终还是在洛谷题解 中 WC2012论文《理性愉悦：高精度数值计算》里的公式求出 \(\lfloor \frac{10^n}{b}\rfloor\)，然后用这个一直取消去 \(a\)，直到无法消去，就开始递减，然后就得到正确答案了

拓展功能

• gcd，lcm， pow，sqrt，cbrt，任意次开方
• 静态：big_random: 利用 mt19937?

注意 gcd 是 \(O(n^2 \log n)\)，其中 \(n\) 为 位数

与 Boost 比较

#include <boost/multiprecision/cpp_int.hpp>
using BINT = boost::multiprecision::cpp_int;