バレットの還元アルゴリズム
合同算術において、バレットの還元アルゴリズムは P.D. バレットによって 1986 年に開発されたアルゴリズムである。以下の式を計算することを考える。
愚直な方法は、高速な除算アルゴリズムを使用する方法である。バレットの還元アルゴリズムは、除算を乗算に置き換えることにより、formula_2 が定数で formula_3 であるときにこの計算を高速化する。