关于Barrett Reduction的优化

· · 算法·理论

我今天忘记了这玩意的具体柿子，于是自己推了一下，莫名其妙似乎发现了一个优化。

要求的是 x \bmod m，可以转化为 \left\lfloor\frac{x}{m}\right\rfloor(0 \le x \le a,1 \le m \le b)。

正常的过程都是 \left\lfloor\frac{x \times \left\lfloor\frac{2^k}{m}\right\rfloor}{2^k}\right\rfloor，但是众所周知这个可能会差 1，需要一次额外的大小比较和减法。

现在考虑 t_x:=\left\lfloor\frac{x \times \left\lceil\frac{2^k}{m}\right\rceil}{2^k}\right\rfloor。

显然，t_x \ge \left\lfloor\frac{x \times \frac{2^k}{m}}{2^k}\right\rfloor=\left\lfloor\frac{x}{m}\right\rfloor，只需要考虑让 t_x \le \left\lfloor\frac{x}{m}\right\rfloor 即可。

令 g=\left\lfloor\frac{a}{m}\right\rfloor。设 x=wm+r(0 \le r \le m-1)，则 w \le g。

于是，t_x \le t_{wm+m-1}，只需要让 t_{wm+m-1} \le w 即可，将其变形为 t_{wm+m-1} \lt w+1。

展开取整，变为 (wm+m-1) \times \left\lceil\frac{2^k}{m}\right\rceil \lt (w+1) \times 2^k。

移项，\frac{wm+m-1}{w+1} \times \left\lceil\frac{2^k}{m}\right\rceil \lt 2^k。

考虑左边，\frac{wm+m-1}{w+1} \times \left\lceil\frac{2^k}{m}\right\rceil=(m-\frac{1}{w+1}) \times \left\lceil\frac{2^k}{m}\right\rceil \le (m-\frac{1}{g+1}) \times \left\lceil\frac{2^k}{m}\right\rceil \le (m-\frac{1}{g+1}) \times (\frac{2^k}{m}+\frac{m-1}{m})=2^k+m-1-\frac{2^k}{m(g+1)}-\frac{m-1}{m(g+1)}。

于是只需要 m-1 \lt \frac{2^k+m-1}{m(g+1)}，也就是 (m-1)(mg+m-1) \lt 2^k。

由 m-1 \le b-1,mg=m \times \left\lfloor\frac{a}{m}\right\rfloor \le a，只需要 2^k \gt (b-1) \times (a+b-1) 即可。