我不知道乘法逆算法,但这听起来像是Montgomery Reduction或巴雷特补偿的修改。
我使用了不同的大整数除法方法。
请参见bignum division。特别是查看近似除法器和其中的2个链接。其中一个是我的定点除法器,另一个是快速乘法算法(如Karatsuba、NTT上的Schönhage-Strassen)和我的非常快速的32位基数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 <DWORD N> void uint<N>::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
是用于存储大整数的32位DWORD
数的数量。
c = a / b
d = a % b
qeq(a,b)
是一个比较:如果a>=b
,则为大于或等于(在log32(n)=N
中完成)
它返回a<b
时的0
,返回a>b
时的1
,返回a == b
时的2
sub(c,a,b)
是 c = a - b
加速的提升源于不使用乘法(如果不计算位移的话)
如果您使用像2^32(ALU块)这样的大基底数字,则可以使用32位内置ALU操作将整个重写为类似于多项式的样式。这通常甚至比二进制长除法更快,其思想是将每个DWORD处理为单个数字,或者将已使用的算术逐渐减半直到达到CPU能力。
请参阅通过半位宽算术进行除法运算
当与大整数计算时
如果您优化了基本操作,则复杂度甚至可以进一步降低,因为随着迭代,子结果会变得更小(从而改变基本操作的复杂度)。 NTT基础乘法的一个很好的例子。
开销可能会搞砸事情。
由于这个原因,运行时间有时不会复制大O复杂度,因此您应该始终测量阈值并针对所使用的位数使用更快的方法来获得最大性能并进行优化。