压位高精度整数 3.0

# 代码
**[代码](https://www.luogu.me/paste/yidm1pfu#)**
# 操作
记 $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 会出现误差；
- 其他偶然错误。
# 性能测试
## 测试信息
```html
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](https://www.luogu.me/article/p6un33cl)