压位高精度整数2.7

· · 科技·工程

板子

更新

BigInteger 2.7

时间：2025/04/06。

经过对开根的优化，BigInteger 2.7 在 U473176 速度优化 10 倍，超过 pypy 200ms。在 P2293 跑进最优解第一页。

BigInteger 2.6.2

时间：2025/03/29。

修复了 @Xudongning 指出的关于取模的 bug，在此感谢。

BigInteger 2.6

时间：2025/01/23。

为 BigDecimal 项目需要，修复若干 bug。

BigInteger 2.5

时间：2024/08/28。

BigInteger 2.4.2

时间：2024/07/24。

BugFixed

时间：2024/07/03。

感谢 konyakest 神仙指错，原 push 中的扩容存在严重问题，导致计算 2729 及以上的阶乘会 RE：

现将所有 BigInteger2 版本修复。

BigInteger 2.4

时间：2024/06/21。

经过对 FFT 的大量优化，BigInteger 2.4 在 P1919 的平均用时仅 49ms，跑到最优解第 6 页。在 3 \times 10^6 数据下用时仅 170ms。

BigInteger 2.3

时间：2024/06/15。

BigInteger 2.2

时间：2024/06/07。

BigInteger 2.1

时间：2024/05/31。

BigInteger 2.0

时间：2024/04/04。

重构全是锅的 BigInteger 1.0。

BigInteger 1.0

时间：2023/12/01。

见 这篇博客。

在大量的锅中发现了少量板子。

FFT 模板能跑到 948ms，高精除高精 727ms，全套模板 481ms，常数极大。

Todo

支持操作

以下，记 n 为 a,b 中较大数的位数。w = 8。

表达式 含义 时间复杂度 空间复杂度 备注
a <=> b 高精度比较 O(\dfrac{n}{w}) O(\dfrac{n}{w})
a + b 高精度加法 O(\dfrac{n}{w}) O(\dfrac{n}{w})
a - b 高精度减法 O(\dfrac{n}{w}) O(\dfrac{n}{w})
a * b 高精度乘法（普通） O(\dfrac{n^2}{w^2}) O(\dfrac{n}{w})
a * b 高精度乘法（FFT） O(\dfrac{n\log n}{w}) O(n)
a / b 高精度除法（普通） O(\dfrac{n^2}{w}) O(\dfrac{n}{w})
a / b 高精度除法（牛迭） O(\dfrac{n \log n}{w}) O(\dfrac{n \log n}{w}) 2.3 新增
a % b 高精度取余（普通） O(\dfrac{n^2}{w}) O(\dfrac{n}{w})
a % b 高精度取余（牛迭） O(\dfrac{n \log n}{w}) O(\dfrac{n\log n}{w}) 2.3 新增
a.root(x) 计算 \lfloor \sqrt[x]{a} \rfloor O(\dfrac{n \log n}{w}) O(\dfrac{n}{w}) 2.0 新增，2.4 前名为 sqrt，2.7 前复杂度为 O(\dfrac{n \log^2 n}{w})
a.sqrt(x) 计算 \lfloor \sqrt{a} \rfloor O(\dfrac{n \log n}{w}) O(\dfrac{n}{w}) 2.5 新增，速度快于 root(2)，2.7 前复杂度为 O(\dfrac{n \log^2 n}{w})
a.abs() 求绝对值 O(\dfrac{n}{w}) O(\dfrac{n}{w})
-a 求相反数 O(\dfrac{n}{w}) O(\dfrac{n}{w})
~a 计算 -a-1 O(\dfrac{n}{w}) O(\dfrac{n}{w})
a.divmod(b) 除法 + 取余（普通） O(\dfrac{n^2}{w}) O(\dfrac{n}{w}) 2.1 新增
a.divmod(b) 除法 + 取余（牛迭） O(\dfrac{n\log n}{w}) O(\dfrac{n\log n}{w}) 2.3 新增
a.div2() 计算 \lfloor \dfrac{a}{2} \rfloor O(\dfrac{n}{w}) O(\dfrac{n}{w}) 2.1 新增
a.gcd(b) 计算 \gcd(a,b) O(\dfrac{n^2}{w}) O(\dfrac{n}{w}) 2.1 新增
a.lcm(b) 计算 \operatorname{lcm}(a,b) O(\dfrac{n^2}{w}) O(\dfrac{n}{w}) 2.1 新增
a.to_binary() 返回 a 的二进制表示 O(n) O(n) 2.4 新增
a & b 高精度按位与 O(n^2) O(n) 2.4 新增
a \| b 高精度按位或 O(n^2) O(n) 2.4 新增
a ^ b 高精度按位异或 O(n^2) O(n) 2.4 新增
a >> x 计算 \lfloor \dfrac{a}{2^x} \rfloor O(\dfrac{nx}{w}) O(n) 2.4 新增
a._move_l(x) 计算 a\times 10^{wx} O(\dfrac{n}{w}+x) O(\dfrac{n}{w}+x) 2.5 新增
a._move_r(x) 计算 \lfloor \dfrac{a}{10^{wx}} \rfloor O(\dfrac{n}{w}-x) O(\dfrac{n}{w}-x) 2.5 新增
a._digit_len() 计算 \lfloor \dfrac{n}{w} \rfloor O(1) O(1) 2.5 新增

本模板能以优秀的时间通过 这个题单 中的所有题目。

优缺点

为什么要使用这个板子？

这个板子有哪些缺点？

性能测试

本机信息

CPU：Intel(R) Core(TM) i7-10750H CPU @ 2.60GHz 2.59 GHz。
内存：32 GB。
系统：Windows 10，64 位。

本机 GCC 编译器，GNU C++14，开 O2。

大概比洛谷机子慢一倍左右。

BigInteger 2.4 及以上

数据规模 10^4 5\times 10^4 10^5 5\times 10^5 10^6 5\times 10^6 10^7 5\times 10^7
加法 0.002 0.010 0.022 0.100 0.201 1.020 2.065 10.183
减法 0.002 0.010 0.020 0.102 0.194 0.990 1.987 9.989
乘法 0.003 0.011 0.024 0.139 0.283 1.423 2.875
除法 0.003 0.046 0.033 0.200 0.429 3.239 7.007
取余 0.001 0.008 0.017 0.125 0.283 3.061 5.314
GCD 0.309 7.168
LCM 0.316 7.342
位运算 0.333 8.206

BigInteger 2.3

只对除法、取余有优化，故只测试除法和取余。

数据规模 10^4 5\times 10^4 10^5 5\times 10^5 10^6 5\times 10^6 10^7 5\times 10^7
除法 0.005 0.031 0.062 0.387 0.820 4.106 8.433 43.097
取余 0.003 0.024 0.051 0.316 0.661 3.290 6.851 37.779

BigInteger 2.2

数据规模 10^4 5\times 10^4 10^5 5\times 10^5 10^6 5\times 10^6 10^7 5\times 10^7
加法 0.002 0.009 0.017 0.088 0.174 0.883 1.893 8.976
减法 0.002 0.009 0.017 0.088 0.175 0.883 1.775 9.411
乘法 0.004 0.027 0.057 0.281 0.575 2.748 5.762 26.792
除法 0.004 0.056 0.209 4.562 20.290
取余 0.003 0.048 0.196 4.616 20.058
GCD 0.239 5.401
LCM 0.646 5.387

BigInteger 2.1

数据规模 10^4 5\times 10^4 10^5 5\times 10^5 10^6 5\times 10^6 10^7 5\times 10^7
加法 0.002 0.009 0.017 0.096 0.176 0.887 1.762 8.792
减法 0.002 0.009 0.017 0.090 0.181 0.887 1.772 9.036
乘法 0.005 0.028 0.055 0.280 0.573 2.668 5.491 26.744
除法 0.398 9.650
取余 0.401 9.655
GCD 0.239 5.404
LCM 0.647 15.691

实现原理

基础四则运算就是压个位，普及组内容。这里说一下如何优化速度。

乘法

乘法用 FFT，参考这篇文章和这篇文章添加了压 4 位 + DIF/DIT + 分裂基，同时按 zhangbo1000 巨佬的做法 添加了分段单位根优化，这样避免使用速度较慢的 long double。代价是 5 \times 10^7 数据下出现严重精度损失，而 OI 范围内一直到 3 \times 10^6 都没有问题。

除法

写过一篇 题解，复述一下：

对于 \lfloor \dfrac{a}{b} \rfloor，考虑使用牛顿迭代计算 \dfrac{1}{b} 的近似值，然后使用 a \times \dfrac{1}{b} 计算并调整得到精确值。

牛顿迭代的式子：

x=x_0-\dfrac{f(x_0)}{f'(x_0)}

求解 \dfrac{1}{b} 就是解方程 x-\dfrac{1}{b}=0，将 f(x)=x-\dfrac{1}{b} 代入得

\begin{aligned} x&=x_0-\dfrac{f(x_0)}{f'(x_0)}\\ &=x_0-\dfrac{x_0-\dfrac{1}{b}}{1}\\ &=\dfrac{1}{b} \end{aligned}

换个方程 \dfrac{1}{x}-b=0 代入

\begin{aligned} x&=x_0-\dfrac{f(x_0)}{f'(x_0)}\\ &=x_0-\dfrac{\dfrac{1}{x_0}-b}{-\dfrac{1}{{x_0}^2}}\\ &=2x_0-b{x_0}^2 \end{aligned}

如果直接求解 \dfrac{1}{b}，需要高精度实数。下面的做法来自著名论文《理性愉悦：高精度数值计算》。

考虑把小数的那些位保存到整数上，也就是求得 x=\lfloor \dfrac{10^{2n}}{b} \rfloor，那么设 x_0=\lfloor \dfrac{10^{2n_0}}{b_0} \rfloor，代入 x=2x_0-b{x_0}^2 得：

\dfrac{10^{2n}}{b}=2\dfrac{ \dfrac{10^{2n_0}}{b_0}}{10^{n-n_0}}-b(\dfrac{ \dfrac{10^{2n_0}}{b_0}}{10^{n-n_0}})^2

整理得：

x =2\times 10^{n-n_0} x_0-\dfrac{b{b_0}^2}{10^{2n_0}}

为了保证调整次数，这里需要使 b 的位数不过少，可以令 b 左移到 n_b \le 2n_a。

取 n_0=\lfloor \dfrac{n+2}{2} \rfloor 可得到复杂度为 O(n \log n)。

开平方

《理性愉悦：高精度数值计算》中提出如下方法：

也是牛顿迭代求解 \sqrt{a}。求解方程 x^2-a=0，将 f(x)=x^2-a 代入得

\begin{aligned} x&=x_0-\dfrac{f(x_0)}{f'(x_0)}\\ &=x_0-\dfrac{{x_0}^2-a}{2x_0}\\ &=\dfrac{x_0}{2}+\dfrac{a}{2x_0} \end{aligned}

除法不好解决，换用方程 \dfrac{1}{x^2}-\dfrac{1}{a}=0，则

\begin{aligned} x&=x_0-\dfrac{f(x_0)}{f'(x_0)}\\ &=x_0-\dfrac{\dfrac{1}{{x_0}^2}-\dfrac{1}{a}}{-\dfrac{2}{{x_0}^3}}\\ &=\dfrac{3x_0}{2}+\dfrac{{x_0}^3}{2a} \end{aligned}

这样我们只要求解 \sqrt{\dfrac{1}{a}} 就能去掉除法。和除法一样，设 x_0=\lfloor \dfrac{10^{2n_0}}{a} \rfloor 代入计算即可。参考了 @TBB_Nozomi 的实现。

参考资料

说明

如果有 bug，欢迎指出，感激不尽！