大整数 cpp 版
最后更新于：2022年6月25日 下午
把自己的 个人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 为底数）
大数除法
参考洛谷的题解
首先应用牛顿法：\(f(x) = \frac{1}{x} - b\)，即可知道迭代公式为： \[ x_{n + 1} = x_n(2 - b x_n) \] 当然也可以根据 \(|b x_n - 1| < \epsilon\) 则 \[ -\epsilon^2 < bx_n(2 - b x_n) - 1 < 0 \] 即，我们可以始终保持 \(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}\)，即 \[
b' = b_{n - 1} \frac{1}{10} + b_{n - 2} \frac{1}{10^2} + \cdots + b_0 \frac{1}{10^n}
\] 那么此时 \(x_n\) 也可以写成此形式 \[
x_n = a_0 + a_1 \frac{1}{10} + \cdots + a_n \frac{1}{10^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 比较
1 | |