压位高精度整数 3.0

Xudongning · 2025-04-20 12:08:59 · 科技·工程

代码

操作

记 n=\lfloor\lg\max(a,b)+1\rfloor,w=8。	表达式	含义	时间复杂度
`a.to_string()`	求 a 的`string`表示	O(\dfrac{n}{w})	O(n)
`a.to_long_long()`	求 a 的`long long`表示	O(\dfrac{n}{w})	O(n)
`a.to_binary()`	求 a 的二进制表示	O(\dfrac{n^2}{w})	O(n^2)
`a.to_int128()`	求 a 的`__int128`表示	O(\dfrac{n}{w})	O(n)
`a._digit_len()`	求 \lfloor \dfrac{n}{w} \rfloor	O(1)	O(1)
`-a`	求 -a	O(\dfrac{n}{w})	O(\dfrac{n}{w})
`~a`	求 -a-1	O(\dfrac{n}{w})	O(\dfrac{n}{w})
`a.abs()`	求 \mid a\mid	O(\dfrac{n}{w})	O(\dfrac{n}{w})
`a <=> b`	求大小关系	O(\dfrac{n}{w})	O(\dfrac{n}{w})
`a.div2()`	求 \lfloor \dfrac{a}{2} \rfloor	O(\dfrac{n}{w})	O(\dfrac{n}{w})
`a.divmod(b)`	除法 + 取余（普通）	O(\dfrac{n^2}{w})	O(\dfrac{n}{w})
`a.divmod(b)`	除法 + 取余（牛迭）	O(\dfrac{n\log n}{w})	O(\dfrac{n\log 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})
`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})
`a.pow(x)`	乘方（普通）	O(\dfrac{n^2\log n\log x}{w})	O(nx)
`a.pow(x,p)`	乘方（取余）	O(\dfrac{n^2\log n\log x}{w})	O(n)
`a.root(x)`	求 \lfloor \sqrt[x]{a} \rfloor	O(\dfrac{n \log n}{w})	O(\dfrac{n}{w})
`a.sqrt()`	求 \lfloor \sqrt{a} \rfloor	O(\dfrac{n \log n}{w})	O(\dfrac{n}{w})
`a.gcd(b)`	求 \gcd(a,b)	O(\dfrac{n^2}{w})	O(\dfrac{n}{w})
`a.lcm(b)`	求 \operatorname{lcm}(a,b)	O(\dfrac{n^2}{w})	O(\dfrac{n}{w})
`a & b`	按位与	O(n^2)	O(n)
`a \\| b`	按位或	O(n^2)	O(n)
`a ^ b`	按位异或	O(n^2)	O(n)
`a << x`	求 a\cdot 2^x	O(\dfrac{nx}{w})	O(n)
`a >> x`	求 \lfloor \dfrac{a}{2^x} \rfloor	O(\dfrac{nx}{w})	O(n)
`a._move_l(x)`	求 a\cdot 10^{wx}	O(\dfrac{n}{w}+x)	O(\dfrac{n}{w}+x)
`a._move_r(x)`	求 \lfloor \dfrac{a}{10^{wx}} \rfloor	O(\dfrac{n}{w}-x)	O(\dfrac{n}{w}-x)
`random_big(x)`	生成位数为 x 的随机正数	O(n)	O(n)

优点

高度封装，支持许多操作；
速度较快，大部分操作已优化到较优秀的复杂度；
代码较短（约 30KB）。
缺点
位运算速度慢；
整数位数较大时，FFT 会出现误差；

其他偶然错误。

性能测试

测试信息

CPU：12th Gen Intel(R) Core(TM) i3-12100   3.30 GHz
RAM：24.0 GB
系统类型：64 位操作系统，基于 x64 的处理器
版本：Windows 11 专业版
编译器：TDM-GCC 14.2.0 64-bit Release
编译语言：C++ 23
软件：Dev-C++ 6.7.5
备注：采用文件读写的方式，运用 Windows 系统函数测速，多次测速取算数平均数，最坏情况
单位：毫秒

测试结果

	10^4	5\times 10^4	10^5	5\times 10^5	10^6	5\times 10^6	10^7
加法	0.0087	0.0546	0.1075	0.5358	1.4062	5.3154	9.4003
减法	0.0054	0.0353	0.0851	0.4604	1.3605	4.0691	8.4379
乘法	0.1183	0.8681	1.9343	9.1752	18.8203	207.892	413.864
除法	0.4551	1.5709	4.6036	10.1658	23.3427	226.032	515.148
取余	0.6864	1.0169	2.1562	12.088	31.8304	265.982	491.209
开平方	3.3651	18.7371	38.378	189.588	352.961
GCD	152.062	4930.9
LCM	157.421	4962.43
位运算	191.679	5605.27

优化内容

1. 基础架构差异

异常处理：
- BigInteger 3.0 使用 std::runtime_error 作为基类
- BigInteger 2.7 使用 std::exception 作为基类
内存管理：
- BigInteger 3.0 实现了内存池机制，使用 allocate_digits 和 deallocate_digits 方法
- BigInteger 2.7 使用传统的 new 和 delete 直接管理内存
  2. 功能实现差异
构造函数和赋值操作：
- BigInteger 3.0 提供了 operator=(const __int128&) 和 to_int128() 方法
- BigInteger 2.7 将这些方法放在 #ifdef __SIZEOF_INT128__ 条件编译块中
数学运算：
- BigInteger 3.0 提供了 random() 方法生成随机大整数
- BigInteger 2.7 提供了 factorial() 静态方法计算阶乘
模板支持：
- BigInteger 3.0 的 pow 方法使用模板参数
- BigInteger 2.7 有明确的 pow(const long long&, const BigInteger&) 重载
  3. 实现细节差异
实现：
- BigInteger 3.0 使用 FastFourierTransformation 命名空间
- BigInteger 2.7 使用 __FFT 命名空间
- 具体实现细节和常量定义略有不同
比较运算符：
- BigInteger 2.7 只使用 operator<=>
- BigInteger 2.7 同时支持 operator<=> 和传统的比较运算符重载
位移操作：
- BigInteger 3.0 的位移操作直接使用 pow 方法
- BigInteger 2.7 的位移操作实现相同但代码风格略有不同
  4. 代码风格差异
方法实现位置：
- BigInteger 3.0 将更多方法实现放在类定义内部
- BigInteger 2.7 倾向于将方法实现在类定义外部
命名风格：
- BigInteger 3.0 使用更一致的命名风格
- BigInteger 2.7 在某些地方使用了下划线前缀
  5. 性能优化
BigInteger 3.0 的内存池实现可能提供更好的内存分配性能
BigInteger 2.7 的 factorial 方法提供了额外的数学运算功能，但速度慢

压位高精度整数 2.7

压位高精度整数 3.0

代码

操作

优点

缺点

性能测试

测试信息

测试结果

优化内容

1. 基础架构差异

2. 功能实现差异

3. 实现细节差异

4. 代码风格差异

5. 性能优化

BigInteger 2.7 的 factorial 方法提供了额外的数学运算功能，但速度慢

BigInteger 2.7 的 `factorial` 方法提供了额外的数学运算功能，但速度慢