Barrett Reduction 算法学习笔记

在模数变化频率较小情况下的高效取模优化器。

取模运算，即计算 $a \bmod p$，在各类数论、计数题中经常出现。但是计算机对取模运算的处理较慢，如果取模的次数很多，则会显著拖慢程序的速度。

考虑怎么加速这个运算，通常我们人工计算取模，使用的是下面这个式子：

$a \bmod p = a - \left \lfloor \frac{a}{p} \right \rfloor \times a$

还剩下一个 $q = \left \lfloor \dfrac{a}{p} \right \rfloor$ 没有逃掉除法，或许可以使用浮点数预先存下 $p$ 的倒数，但是浮点数的运算还是比较慢，不尽如人意。

考虑用位移运算去逼近 $\dfrac{1}{p}$，弄出两个整数 $m,k$，使得 $\dfrac{m}{2^k} \approx \dfrac{1}{p}$。那么 $q$ 就约等于 $\left \lfloor \dfrac{a \times m}{2^k} \right \rfloor$，只要预先处理出 $m \approx \dfrac{2^k}{p}$，之后的取模便拆成了速度快得多的乘法与位移，一劳永逸。

考虑如何定下 $m$，即 $k$ 要怎么取。直观上看，$m$ 的取值范围不能太小，至少要达到最大值要可以达到 $p$，于是可以解得 $k \ge 2 \lceil \log_2{p} \rceil$。下面我们证明，当 $k \ge 2 \lceil \log_2{p} \rceil$，我们取 $m = \left \lfloor \dfrac{2^k}{p} \right \rfloor$，则得到的答案便是几乎正确的：

证明：

$a - pq = a - \dfrac{apm}{2^k} = \dfrac{a}{2^k} (2^k - pm)$

因为 $m = \left \lfloor \dfrac{2^k}{p} \right \rfloor$，故 $\dfrac{2^k}{p} - 1 < m \le \dfrac{2^k}{p}$，可推出：

$0 \le 2^k - pm < p$

而通常而言 $a$ 是小于 $p$ 的两个数的和或积，不超过 $p^2$。而 $k \ge 2 \lceil \log_2{p} \rceil$，则有 $2^k \ge p^2$。综合一下便有 $0 \le \dfrac{a}{2^k} < 1$。

那就得出了：

$0 \le a - pq = \dfrac{a}{2^k} (2^k - pm) <p$

即：

$a \bmod p = a - pq$

$\Box$

有的人可能对「几乎正确」这个词很迷惑，不是都得出了 $0\le a - pq < p$ 了吗，为什么不能把「几乎」去掉呢？

这是因为其实上面的 $q$ 都没有带上下取整号，所以实际上 $a - pq$ 可能会更大。但是只要 $k$ 取得不要太离谱，具体的，$k$ 的误差在 $20$ 以内，基本上 $a - pq = a \bmod p$ 取值只有 $0,p$ 两种情况，极少数有 $2p$ 的情况，没有 $3p$ 的情况，即只需要再多进行至多两次减法即可。

以上算法便是著名的 Barrett Reduction 算法，其实如果模数是静态常量并且开 O2 优化，编译器就已经加上了这个优化。

这个算法需要对每个模数预先执行一次除法操作来预处理 $m$。那考虑十分极端的情况，每次取模的模数都不一样，那该算法的效率便比直接取模还要慢。但正常来讲模数个数与取模次数之间差了至少一个数量级，所以大多数情况下还是很好用的。

经测试，在 $2^{63}$ 即 long long 范围内大概效率是不加优化的 $70\%$；而在 $2^{1024}$ 范围内，由于高精度除法的效率实在是低，加了这个优化后效率更是飞起，达到不加优化的 $6\%$ 左右。