c++ - 我应该使用什么算法进行高性能大整数除法？

Question

我正在将大整数编码到一个 size_t 的数组中。我已经有其他操作在工作(加、减、乘)；以及除以一位数。但如果可能的话，我想匹配我的乘法算法的时间复杂度(目前是 Toom-Cook)。

我收集到有一些线性时间算法可用于计算我的红利的乘法逆的各种概念。这意味着我理论上可以实现与乘法相同的时间复杂度的除法，因为相比之下，线性时间运算无论如何都是“微不足道的”。

我的问题是，我实际上该怎么做？哪种类型的乘法逆元在实践中最好？模 64^digitcount？当我将乘法逆乘以我的除数时，我是否可以避免计算因整数截断而被丢弃的数据部分？任何人都可以提供 C 或 C++ 伪代码或准确解释应该如何完成吗？

或者是否有比基于逆的方法更好的专用除法算法？

编辑:我挖出了上面提到的“逆向”方法。在“计算机编程艺术，第 2 卷:半数值算法”的第 312 页，Knuth 提供了“算法 R”，这是一个高精度的倒数。他说它的时间复杂度低于乘法。然而，将它转换为 C 并对其进行测试是很重要的，并且不清楚在我编写代码之前会消耗多少开销内存等，这需要一段时间。如果没有人反对我，我会发布它。

Answer 1

GMP 库通常是优秀算法的良好引用。他们的documented algorithms for division主要取决于选择一个非常大的基数，这样您就可以将一个 4 位数除以一个 2 位数，然后进行长除法。

长除法需要计算 2 位除以 1 位的商；这可以递归地完成，也可以像使用 Barrett 约简那样预先计算逆并估计商。

划分一个2n时-位编号 n -位数，递归版本成本O(M(n) log(n)) , 其中M(n)是乘以 n 的成本-位数。

使用 Barrett 还原的版本将花费 O(M(n))如果您使用牛顿算法计算逆，但根据 GMP 的文档，隐藏常数要大得多，因此这种方法仅适用于非常大的除法。

---

更详细地说，大多数除法算法背后的核心算法是“估计商减法”计算，计算(q,r)这样

x = qy + r

但没有限制 0 <= r < y .典型的循环是

• 估计商q的 x/y
• 计算相应的减少量r = x - qy
• 可选地调整商数，以便减少 r处于某个期望的间隔内
• 如果r太大，然后用 r 重复代替 x .

x/y 的商将是所有 q 的总和s产生了，最终值为r将是真正的余数。

比如教科书长除法就是这种形式。例如第 3 步涵盖了您猜测的数字太大或太小的情况，您可以调整它以获得正确的值。

分而治之的方法估计 x/y 的商通过计算 x'/y'其中 x'和 y'是 x 的前导数字和 y .通过调整它们的大小有很大的优化空间，但是如果 x'，IIRC 你会得到最好的结果。是 y' 的两倍.

在我看来，如果您坚持使用整数运算，则乘以逆的方法是最简单的。基本方法是

• 估计 y 的倒数与 m = floor(2^k / y)
• 估价x/y与 q = 2^(i+j-k) floor(floor(x / 2^i) m / 2^j)

事实上，实际的实现可以容忍 m 中的额外错误如果这意味着您可以使用更快的互惠实现。

错误很难分析，但如果我记得它的方法，你想选择i和 j这样x ~ 2^(i+j)由于错误的累积方式，您想选择 x / 2^i ~ m^2尽量减少整体工作量。

随后的减少将有r ~ max(x/m, y) , 所以这给出了选择 k 的经验法则: 你想要 m 的大小大约是你每次迭代计算的商的位数——或者相当于你想从 x 中删除的位数每次迭代。