0%


Disclaimer: 我对汇编几乎不了解，理解基本上是靠猜。我也不了解每个指令的时间、CPU 的流水线作业、分支预测等因素对齐性能的影响。这里贴出汇编代码只是为了确认没有奇怪的操作。

# Algorithm 2

Algorithm 2 有一个问题使得我们无法直接计算 $$\floor{\frac{(n+1)a}{2^b N}}$$$$n+1$$ 可能会溢出 u64。这也就是我们即将解决的问题。注意到 $$a < N$$，所以 $$(n+1)a \leq N(N-1)$$ 不会溢出 u128。

# Related Work

baihacker 的 PE 库中有一个 NTT 的 benchmark，里面比较了 FLINT/NTL/LibBF 以及 Min_25 的代码，发现 Min_25 的是最快。我去看了一下 Min_25 的代码UnsafeMod 里面的 reduce 函数和 Wikipedia 里面的 REDC 算法很像（但是不是），不过我也没仔细去看这个函数到底是干啥的了 = = 这个类好奇怪啊，减法里面为啥要加 3 * mod……NTL 的源代码中提到了这篇 paper，我也没看这是在说啥……Division algorithm 的 Wikipedia 中有一小节提到了：

However, unless D itself is a power of two, there is no X and Y that satisfies the conditions above. Fortunately, (N·X)/Y gives exactly the same result as N/D in integer arithmetic even when (X/Y) is not exactly equal to 1/D, but "close enough" that the error introduced by the approximation is in the bits that are discarded by the shift operation.

# Acknowledgement

As is well known (and seen in a previous post), compilers optimize unsigned division by constants into multiplication by a "magic number." But not all constants are created equal, and approximately 30% of divisors require magic numbers that are one bit too large, which necessitates special handling.