Barrett Reduction とは

えびちゃんさんの記事がわかりやすかったです．アイデアは固定された除数 $m$ に対して適当な $2$ 冪である定数 $B$ を使って $\left \lceil \frac{B}{m} \right \rceil$ を前計算しておくことで， $\left \lfloor \frac{N}{m} \right \rfloor$ を $\left \lfloor \frac{\left \lceil \frac{B}{m} \right \rceil \times N}{B} \right \rfloor$ で近似すれば除算を乗算とビット演算で置き換えられるという感じです．また， $N \lt m ^ 2$ の時近似の誤差が高々 $1$ であることが知られています．(ACLの実装も (実質) $\lt m ^ 2$ を要求しています)

考えたことその1 ： $N \lt m ^ 2$ とは限らない場合

$B = qm - r \ (0 \leq r \lt m)$ とします．この時 $\left \lceil \frac{B}{m} \right \rceil = \frac{B + r}{m}$ です． $\left \lfloor \frac{\left \lceil \frac{B}{m} \right \rceil \times N}{B} \right \rfloor = \left \lfloor\left \lceil \frac{B}{m} \right \rceil \times \frac{N}{B} \right \rfloor = \left \lfloor \frac{B + r}{m} \times \frac{N}{B} \right \rfloor = \left \lfloor \frac{N}{m} + \frac{rN}{mB} \right \rfloor$ で，求めたい値が $\left \lfloor \frac{N}{m} \right \rfloor$ であることに留意すると，誤差が高々 $1$ になる十分条件は $\frac{rN}{mB} \lt \frac{mN}{mB} \leq 1$ より $N \leq B$ であればよさそうということがわかります． $N \lt m ^ 2$ よりも扱いやすい制約になった気がします．

考えたことその2 ：誤差を $0$ にする方法

前の章と同じようなことをすると， $\left \lfloor \frac{N}{m} + \frac{rN}{mB} \right \rfloor \leq \left \lfloor \frac{N + 1}{m} \right \rfloor$ であればよさそうなので，こうなる条件を考えることにします．これの十分条件として $\frac{rN}{mB} \lt \frac{1}{m} \Leftrightarrow rN \lt B$ があるので， $N$ の最大値を $N _ { \max }$ として $mN _ {\max} \leq B \lt 2mN _ {\max}$ となるように $B$ をとることとします．この時オーバーフローが若干心配になりますが， $\left \lceil \frac{B}{m} \right \rceil \times N \lt (\frac{2mN _ {\max}}{m} +1) \times N = 2N _ {\max}^2 + N _ {\max}$ なので途中で出てくる数はそこまで大きくないことも確認できました．

実際この方法のほうが ACL の実装より幾分か高速な様です．( $N _ {\max} = 2 ^ {64}$ としたとき $\left \lceil \frac{B}{m} \right \rceil$ を $2 ^ {64}$ で切り下げ除算した結果が常に $1$ なことを利用した高速化もしています．)