高精度计算
太长不看版：结尾自取模板……
定义
高精度计算（Arbitrary-Precision Arithmetic），也被称作大整数（bignum）计算，运用了一些算法结构来支持更大整数间的运算（数字大小超过语言内建整型）．
引入
高精度问题包含很多小的细节，实现上也有很多讲究．
所以今天就来一起实现一个简单的计算器吧．
任务
输入：一个形如 a <op> b 的表达式．
a、b分别是长度不超过 10001000
的十进制非负整数；<op>是一个字符（+、-、*或/），表示运算．- 整数与运算符之间由一个空格分隔．
输出：运算结果．
- 对于
+、-、*运算，输出一行表示结果； - 对于
/运算，输出两行分别表示商和余数． - 保证结果均为非负整数．
存储
在平常的实现中，高精度数字利用字符串表示，每一个字符表示数字的一个十进制位．因此可以说，高精度数值计算实际上是一种特别的字符串处理．
读入字符串时，数字最高位在字符串首（下标小的位置）．但是习惯上，下标最小的位置存放的是数字的 最低位 ，即存储反转的字符串．这么做的原因在于，数字的长度可能发生变化，但我们希望同样权值位始终保持对齐（例如，希望所有的个位都在下标 [0]，所有的十位都在下标 [1]……）；同时，加、减、乘的运算一般都从个位开始进行（回想小学的竖式运算），这都给了「反转存储」以充分的理由．
此后我们将一直沿用这一约定．定义一个常数 LEN = 1004 表示程序所容纳的最大长度．
由此不难写出读入高精度数字的代码：
---|---
输出也按照存储的逆序输出．由于不希望输出前导零，故这里从最高位开始向下寻找第一个非零位，从此处开始输出；终止条件 `i >= 1` 而不是 `i >= 0` 是因为当整个数字等于 00 时仍希望输出一个字符 `0`．
---|---
拼起来就是一个完整的复读机程序咯．
copycat.cpp
---|---
## 四则运算
四则运算中难度也各不相同．最简单的是高精度加减法，其次是高精度—单精度（普通的 `int`）乘法和高精度—高精度乘法，最后是高精度—高精度除法．
我们将按这个顺序分别实现所有要求的功能．
### 加法
高精度加法，其实就是竖式加法啦．
也就是从最低位开始，将两个加数对应位置上的数码相加，并判断是否达到或超过 1010．如果达到，那么处理进位：将更高一位的结果上增加 11，当前位的结果减少 1010．
---|---
试着和上一部分结合，可以得到一个加法计算器．
adder.cpp
---|---
### 减法
高精度减法，也就是竖式减法啦．
从个位起逐位相减，遇到负的情况则向上一位借 11．整体思路与加法完全一致．
---|---
将上一个程序中的 add() 替换成 sub()，就有了一个减法计算器．
subtractor.cpp
---|---
试一试，输入 `1 2`——输出 `/9999999`，诶这个 **OI Wiki** 怎么给了我一份假的代码啊……
事实上，上面的代码只能处理减数 𝑎a 大于等于被减数 𝑏b 的情况．处理被减数比减数小，即 𝑎 <𝑏a<b 时的情况很简单．
𝑎 −𝑏 = −(𝑏 −𝑎)a−b=−(b−a)
要计算 𝑏 −𝑎b−a 的值，因为有 𝑏 >𝑎b>a，可以调用以上代码中的 `sub` 函数，写法为 `sub(b,a,c)`．要得到 𝑎 −𝑏a−b 的值，在得数前加上负号即可．
### 乘法
#### 高精度—单精度
高精度乘法，也就是竖……等会儿等会儿！
先考虑一个简单的情况：乘数中的一个是普通的 `int` 类型．有没有简单的处理方法呢？
一个直观的思路是直接将 𝑎a 每一位上的数字乘以 𝑏b．从数值上来说，这个方法是正确的，但它并不符合十进制表示法，因此需要将它重新整理成正常的样子．
重整的方式，也是从个位开始逐位向上处理进位．但是这里的进位可能非常大，甚至远大于 99，因为每一位被乘上之后都可能达到 9𝑏9b 的数量级．所以这里的进位不能再简单地进行 −10−10 运算，而是要通过除以 1010 的商以及余数计算．详见代码注释，也可以参考下图展示的一个计算高精度数 13371337 乘以单精度数 4242 的过程．
当然，也是出于这个原因，这个方法需要特别关注乘数 𝑏b 的范围．若它和 109109（或相应整型的取值上界）属于同一数量级，那么需要慎用高精度—单精度乘法．
---|---
高精度—高精度
如果两个乘数都是高精度，那么竖式乘法又可以大显身手了．
回想竖式乘法的每一步，实际上是计算了若干 𝑎 ×𝑏𝑖 ×10𝑖a×bi×10i 的和．例如计算 1337 ×421337×42，计算的就是 1337 ×2 ×100 +1337 ×4 ×1011337×2×100+1337×4×101．
于是可以将 𝑏b 分解为它的所有数码，其中每个数码都是单精度数，将它们分别与 𝑎a 相乘，再向左移动到各自的位置上相加即得答案．当然，最后也需要用与上例相同的方式处理进位．
注意这个过程与竖式乘法不尽相同，我们的算法在每一步乘的过程中并不进位，而是将所有的结果保留在对应的位置上，到最后再统一处理进位，但这不会影响结果．
---|---
### 除法
高精度除法的一种实现方式就是竖式长除法．
竖式长除法实际上可以看作一个逐次减法的过程．例如上图中商数十位的计算可以这样理解：将 4545 减去三次 1212 后变得小于 1212，不能再减，故此位为 33．
为了减少冗余运算，我们提前得到被除数的长度 𝑙𝑎la 与除数的长度 𝑙𝑏lb，从下标 𝑙𝑎 −𝑙𝑏la−lb 开始，从高位到低位来计算商．这和手工计算时将第一次乘法的最高位与被除数最高位对齐的做法是一样的．
参考程序实现了一个函数 `greater_eq()` 用于判断被除数以下标 `last_dg` 为最低位，是否可以再减去除数而保持非负．此后对于商的每一位，不断调用 `greater_eq()`，并在成立的时候用高精度减法从余数中减去除数，也即模拟了竖式除法的过程．
---|---
入门篇完成！
将上面介绍的四则运算的实现结合，即可完成开头提到的计算器程序．
calculator.cpp
---|---
## 压位高精度
### 引入
在一般的高精度加法，减法，乘法运算中，我们都是将参与运算的数拆分成一个个单独的数码进行运算．
例如计算 8192 ×428192×42 时，如果按照高精度乘高精度的计算方式，我们实际上算的是 (8000 +100 +90 +2) ×(40 +2)(8000+100+90+2)×(40+2)．
在位数较多的时候，拆分出的数也很多，高精度运算的效率就会下降．
有没有办法作出一些优化呢？
注意到拆分数字的方式并不影响最终的结果，因此我们可以将若干个数码进行合并．
### 过程
还是以上面这个例子为例，如果我们每两位拆分一个数，我们可以拆分成 (8100 +92) ×42(8100+92)×42．
这样的拆分不影响最终结果，但是因为拆分出的数字变少了，计算效率也就提升了．
从 [进位制](../numeral-sys/base/) 的角度理解这一过程，我们通过在较大的进位制（上面每两位拆分一个数，可以认为是在 100100 进制下进行运算）下进行运算，从而达到减少参与运算的数字的位数，提升运算效率的目的．
这就是 **压位高精度** 的思想．
下面我们给出压位高精度的加法代码，用于进一步阐述其实现方法：
压位高精度加法参考实现
---|---
压位高精下的高效竖式除法
在使用压位高精时，如果试商时仍然使用上文介绍的方法，由于试商次数会很多，计算常数会非常大．例如在万进制下，平均每个位需要试商 5000 次，这个巨大的常数是不可接受的．因此我们需要一个更高效的试商办法．
我们可以把 double 作为媒介．假设被除数有 4 位，是 𝑎4,𝑎3,𝑎2,𝑎1a4,a3,a2,a1，除数有 3 位，是 𝑏3,𝑏2,𝑏1b3,b2,b1，那么我们只要试一位的商：使用 𝑏𝑎𝑠𝑒base 进制，用式子 𝑎4𝑏𝑎𝑠𝑒+𝑎3𝑏3+𝑏2𝑏𝑎𝑠𝑒−1+(𝑏1+1)𝑏𝑎𝑠𝑒−2a4base+a3b3+b2base−1+(b1+1)base−2 来估商．而对于多个位的情况，就是一位的写法加个循环．由于除数使用 3 位的精度来参与估商，能保证估的商 q' 与实际商 q 的关系满足 𝑞 −1 ≤𝑞′ ≤𝑞q−1≤q′≤q，这样每个位在最坏的情况下也只需要两次试商．但与此同时要求 𝑏𝑎𝑠𝑒3base3 在 double 的有效精度内，即 𝑏𝑎𝑠𝑒3 <253base3<253，所以在运用这个方法时建议不要超过 32768 进制，否则很容易因精度不足产生误差从而导致错误．
另外，由于估的商总是小于等于实际商，所以还有再进一步优化的空间．绝大多数情况下每个位只估商一次，这样在下一个位估商时，虽然得到的商有可能因为前一位的误差造成试商结果大于等于 base，但这没有关系，只要在最后做统一进位便可．举个例子，假设 base 是 10，求 395081/9876395081/9876，试商计算步骤如下：
- 首先试商计算得到 3950/988 =33950/988=3，于是 395081 −(9876 ×3 ×101) =98801395081−(9876×3×101)=98801，这一步出现了误差，但不用管，继续下一步计算．
- 对余数 98801 继续试商计算得到 9880/988 =109880/988=10，于是 98801 −(9876 ×10 ×100) =4198801−(9876×10×100)=41，这就是最终余数．
- 把试商过程的结果加起来并处理进位，即 3 ×101 +10 ×100 =403×101+10×100=40 便是准确的商．
方法虽然看着简单，但具体实现上很容易进坑，所以以下提供一个经过多番验证确认没有问题的实现供大家参考，要注意的细节也写在注释当中．
压位高精度高效竖式除法参考实现
---|---
## Karatsuba 乘法
记高精度数字的位数为 𝑛n，那么高精度—高精度竖式乘法需要花费 𝑂(𝑛2)O(n2) 的时间．本节介绍一个时间复杂度更为优秀的算法，由前苏联（俄罗斯）数学家 Anatoly Karatsuba 提出，是一种分治算法．
考虑两个十进制大整数 𝑥x 和 𝑦y，均包含 𝑛n 个数码（可以有前导零）．任取 0 <𝑚 <𝑛0<m<n，记
𝑥=𝑥1⋅10𝑚+𝑥0,𝑦=𝑦1⋅10𝑚+𝑦0,𝑥⋅𝑦=𝑧2⋅102𝑚+𝑧1⋅10𝑚+𝑧0,x=x1⋅10m+x0,y=y1⋅10m+y0,x⋅y=z2⋅102m+z1⋅10m+z0,
其中 𝑥0,𝑦0,𝑧0,𝑧1 <10𝑚x0,y0,z0,z1<10m．可得
𝑧2=𝑥1⋅𝑦1,𝑧1=𝑥1⋅𝑦0+𝑥0⋅𝑦1,𝑧0=𝑥0⋅𝑦0.z2=x1⋅y1,z1=x1⋅y0+x0⋅y1,z0=x0⋅y0.
观察知
𝑧1=(𝑥1+𝑥0)⋅(𝑦1+𝑦0)−𝑧2−𝑧0,z1=(x1+x0)⋅(y1+y0)−z2−z0,
于是要计算 𝑧1z1，只需计算 (𝑥1 +𝑥0) ⋅(𝑦1 +𝑦0)(x1+x0)⋅(y1+y0)，再与 𝑧0z0、𝑧2z2 相减即可．
上式实际上是 Karatsuba 算法的核心，它将长度为 𝑛n 的乘法问题转化为了 33 个长度更小的子问题．若令 𝑚 =⌈𝑛2⌉m=⌈n2⌉，记 Karatsuba 算法计算两个 𝑛n 位整数乘法的耗时为 𝑇(𝑛)T(n)，则有 𝑇(𝑛) =3 ⋅𝑇(⌈𝑛2⌉) +𝑂(𝑛)T(n)=3⋅T(⌈n2⌉)+O(n)，由主定理可得 𝑇(𝑛) =Θ(𝑛log23) ≈Θ(𝑛1.585)T(n)=Θ(nlog23)≈Θ(n1.585)．
整个过程可以递归实现．为清晰起见，下面的代码通过 Karatsuba 算法实现了多项式乘法，最后再处理所有的进位问题．
karatsuba_mulc.cpp
---|---
关于 new 和 delete
见 内存池．
但是这样的实现存在一个问题：在 𝑏b 进制下，多项式的每一个系数都有可能达到 𝑛 ⋅𝑏2n⋅b2 量级，在压位高精度实现中可能造成整数溢出；而若在多项式乘法的过程中处理进位问题，则 𝑥1 +𝑥0x1+x0 与 𝑦1 +𝑦0y1+y0 的结果可能达到 2 ⋅𝑏𝑚2⋅bm，增加一个位（如果采用 𝑥1 −𝑥0x1−x0 的计算方式，则不得不特殊处理负数的情况）．因此，需要依照实际的应用场景来决定采用何种实现方式．
基于多项式的高效大整数乘法
如果数据规模达到了 1010510105 或更大，普通的高精度乘法可能会超时．本节将介绍用多项式优化此类乘法的方法．
对于一个 𝑛n 位的十进制整数 𝑎a，可以将它看作一个每位系数均为整数且不超过 1010 的多项式 𝐴 =𝑎0100 +𝑎1101 +⋯ +𝑎𝑛−110𝑛−1A=a0100+a1101+⋯+an−110n−1．这样，我们就将两个整数乘法转化为了两个多项式乘法．
普通的多项式乘法时间复杂度仍是 𝑂(𝑛2)O(n2)，但可以用多项式一节中的 快速傅里叶变换、快速数论变换 等算法优化，优化后的时间复杂度是 𝑂(𝑛log𝑛)O(nlogn)．
封装类
这里 有一个封装好的高精度整数类，以及 这里 支持动态长度及四则运算的超迷你实现类．
这里是另一个模板
---|---
## 习题
* [NOIP 2012 国王游戏](https://loj.ac/problem/2603)
* [SPOJ - Fast Multiplication](http://www.spoj.com/problems/MUL/en/)
* [SPOJ - GCD2](http://www.spoj.com/problems/GCD2/)
* [UVa - Division](https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1024)
* [UVa - Fibonacci Freeze](https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=436)
* [Codeforces - Notepad](http://codeforces.com/contest/17/problem/D)
## 参考资料与链接
1. [Karatsuba algorithm - Wikipedia](https://en.wikipedia.org/wiki/Karatsuba_algorithm)
* * *
> __本页面最近更新： 2026/1/30 14:50:40，[更新历史](https://github.com/OI-wiki/OI-wiki/commits/master/docs/math/bignum.md)
> __发现错误？想一起完善？[在 GitHub 上编辑此页！](https://oi-wiki.org/edit-landing/?ref=/math/bignum.md "edit.link.title")
> __本页面贡献者：[StudyingFather](https://github.com/StudyingFather), [cbw2007](https://github.com/cbw2007), [H-J-Granger](https://github.com/H-J-Granger), [Ir1d](https://github.com/Ir1d), [Marcythm](https://github.com/Marcythm), [Tiphereth-A](https://github.com/Tiphereth-A), [Enter-tainer](https://github.com/Enter-tainer), [NachtgeistW](https://github.com/NachtgeistW), [countercurrent-time](https://github.com/countercurrent-time), [sshwy](https://github.com/sshwy), [ayuusweetfish](https://github.com/ayuusweetfish), [CCXXXI](https://github.com/CCXXXI), [diauweb](https://github.com/diauweb), [Early0v0](https://github.com/Early0v0), [ouuan](https://github.com/ouuan), [AngelKitty](https://github.com/AngelKitty), [cjsoft](https://github.com/cjsoft), [ezoixx130](https://github.com/ezoixx130), [GekkaSaori](https://github.com/GekkaSaori), [Konano](https://github.com/Konano), [LovelyBuggies](https://github.com/LovelyBuggies), [Makkiy](https://github.com/Makkiy), [mgt](mailto:i@margatroid.xyz), [minghu6](https://github.com/minghu6), [P-Y-Y](https://github.com/P-Y-Y), [PotassiumWings](https://github.com/PotassiumWings), [SamZhangQingChuan](https://github.com/SamZhangQingChuan), [Suyun514](mailto:suyun514@qq.com), [weiyong1024](https://github.com/weiyong1024), [Xeonacid](https://github.com/Xeonacid), [383494](https://github.com/383494), [alphagocc](https://github.com/alphagocc), [AndrewWayne](https://github.com/AndrewWayne), [Baobaobear](https://github.com/Baobaobear), [c-forrest](https://github.com/c-forrest), [Chihaya-Yuka](https://github.com/Chihaya-Yuka), [Chrogeek](https://github.com/Chrogeek), [ChungZH](https://github.com/ChungZH), [GavinZhengOI](https://github.com/GavinZhengOI), [Gesrua](https://github.com/Gesrua), [gi-b716](https://github.com/gi-b716), [Glenn-Su](https://github.com/Glenn-Su), [hsfzLZH1](https://github.com/hsfzLZH1), [iamtwz](https://github.com/iamtwz), [justarandomstring](https://github.com/justarandomstring), [ksyx](https://github.com/ksyx), [kxccc](https://github.com/kxccc), [lss233](https://github.com/lss233), [lychees](https://github.com/lychees), [Peanut-Tang](https://github.com/Peanut-Tang), [r-value](https://github.com/r-value), [shuzhouliu](https://github.com/shuzhouliu), [SukkaW](https://github.com/SukkaW), [TrisolarisHD](mailto:orzcyand1317@gmail.com), [yusancky](https://github.com/yusancky)
> __本页面的全部内容在**[CC BY-SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/deed.zh) 和 [SATA](https://github.com/zTrix/sata-license)** 协议之条款下提供，附加条款亦可能应用