我应该使用什么算法进行高性能大整数除法？
我将大整数编码为size_t数组。 我已经有其他操作工作（加，减，乘）; 以及一位数的除法。 但是如果可能的话，我想匹配我的乘法算法的时间复杂度（目前是Toom-Cook）。
我收集有线性时间算法，用于采用我的红利的乘法逆的各种概念。 这意味着我理论上可以在与乘法相同的时间复杂度中实现除法，因为无论如何，线性时间操作通过比较是“无关紧要的”。
我的问题是，我该怎么做呢？ 什么类型的乘法逆在实践中最好？ Modulo 64^digitcount ？ 当我将乘法逆乘以我的除数时，我可以推卸计算由于整数截断而丢弃的数据部分吗？ 任何人都可以提供C或C ++伪代码或准确解释应该如何做到这一点？
或者是否存在比基于逆的方法更好的专用除法算法？
编辑：我挖出了上面提到的“反向”方法。 在“Art of Computer Programming，Volume 2：Seminumerical Algorithms”的第312页上，Knuth提供了“算法R”，它是一种高精度的倒数。 他说它的时间复杂度小于乘法的时间复杂度。 然而，将它转换为C并测试它并且不清楚将消耗多少开销内存等直到我对其进行编码是非常重要的，这将需要一段时间。 如果没有人打败我，我会发布它。
GMP库通常是良好算法的良好参考。 他们记录的划分算法主要取决于选择一个非常大的基数，因此你将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的限制。 典型的循环是
- 估计
x/y的商q - 计算相应的减少
r = x - qy - 可选地调整商，使得减小
r处于某个期望的间隔 - 如果
r太大，则用r代替x重复。
x/y的商是所有生成的q的总和， r的最终值将是真实的余数。
例如，教科书长划分就是这种forms。 例如，步骤3涵盖了您猜测的数字太大或太小的情况，并调整它以获得正确的值。
分而治之的方法通过计算x'/y'来估计x/y的商，其中x'和y'是x和y的前导数字。 通过resize可以有很大的优化空间，但如果x'是y'两倍，IIRC会得到最好的结果。
如果你坚持使用整数运算，那么乘以逆的方法是最简单的IMO。 基本方法是
- 估算
y的倒数，m = floor(2^k / y) - 估算
x/y，q = 2^(i+jk) 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删除的位数。
我不知道乘法逆算法，但它听起来像蒙哥马利减少或巴雷特减少的修改。
我做bigint分歧有点不同。
见bignum部门 。 特别是看一下近似分频器和那里的2个链路。 一个是我的定点分频器，其他是快速乘法算法（如NTT上的karatsuba，Schönhage-Strassen）和测量，以及我对32bit Base的快速NTT实现的链接。
我不确定逆乘法器是否正确。
它主要用于模数运算，其中除法器是常量。 我担心，对于任意划分，获得bigint逆转所需的时间和操作可能比标准划分本身更大，但由于我不熟悉它， 我可能是错的 。
我在实现中看到的最常用的分频器是Newton-Raphson分区，它与上面链接中的近似分频器非常相似。
近似/迭代分频器通常使用乘法来定义它们的速度。
对于足够小的数字，通常是长二进制除法和32/64位数字基本除法，如果不是最快的话，它的速度足够快：通常它们的开销很小，并且n是处理的最大值（不是数字位数！）
二进制除法示例：
是O(log32(n).log2(n)) = O(log^2(n)) 。
它循环遍历所有有效位。 在每次迭代中，您需要compare, sub, add, bitshift 。 这些操作中的每一个都可以在log32(n) ， log2(n)是位数。
这里是我的一个bigint模板（C ++）的二进制除法示例：
template void uint::div(uint &c,uint &d,uint a,uint b) { int i,j,sh; sh=0; c=DWORD(0); d=1; sh=a.bits()-b.bits(); if (sh<0) sh=0; else { b<<=sh; d<<=sh; } for (;;) { j=geq(a,b); if (j) { c+=d; sub(a,a,b); if (j==2) break; } if (!sh) break; b>>=1; d>>=1; sh--; } d=a; }
N是用于存储bigint数的32位DWORD的数量。
-
c = a / b -
d = a % b -
qeq(a,b)是一个比较：a >= b大于或等于（在log32(n)=N）
它返回0表示a < b，1表示a > b，2表示a == b -
sub(c,a,b)是c = a - b
从不使用乘法获得速度提升（如果不计算位移）
如果你使用像2 ^ 32（ALU块）这样的大基数的数字，那么你可以在ALU操作中使用32位构建以多项式样式重写整体。
这通常比二进制长除法更快，其想法是将每个DWORD处理为单个数字，或者递归地将使用的算术除以一半直到达到CPU能力。
请参见半位宽算术分区
最重要的是用bignums计算
如果你已经优化了基本操作，那么复杂性可以进一步降低，因为子结果随着迭代变小（改变基本操作的复杂性）。一个很好的例子是基于NTT的乘法。
开销可能会搞砸了。
由于这个原因，运行时有时不会复制大的O复杂度，因此您应该始终测量阈值并使用更快的方法来使用位数来获得最大性能并优化您的能力。