バレットの還元アルゴリズム
合同算術において、バレットの還元アルゴリズムは P.D. バレットによって 1986 年に開発されたアルゴリズムである。以下の式を計算することを考える。
c = a mod n {\displaystyle c=a\,{\bmod {\,}}n\,}
愚直な方法は、高速な除算アルゴリズムを使用する方法である。バレットの還元アルゴリズムは、除算を乗算に置き換えることにより、 n {\displaystyle n} が定数で a < n 2 {\displaystyle a<n^{2}} であるときにこの計算を高速化する。
m {\displaystyle m} を整数にするために、 2 k / n {\displaystyle {2^{k}}/{n}} をどうにか整数に丸める必要がある。最も近い整数に丸めるのが最適だが、 m / 2 k {\displaystyle m/2^{k}} が 1 / n {\displaystyle 1/n} より大きくなるとアンダーフローを生じうるため、一般には m = ⌊ 2 k / n ⌋ {\displaystyle m=\lfloor {2^{k}}/{n}\rfloor } を用いる。
すると、前述の関数は以下のように書き換えられる。
ここで、 m / 2 k ≤ 1 / n {\displaystyle m/2^{k}\leq 1/n} なので、この関数における q は小さめに評価される。これによりaは [ 0 , n ) {\displaystyle [0,n)} に必ずしも収まらず、 [ 0 , 2 n ) {\displaystyle [0,2n)} の値を取りうる。そのため、値が n {\displaystyle n} を超えた場合は n {\displaystyle n} を引くことによってこれを補正する。