バレットの還元アルゴリズム
n {\displaystyle n} の浮動小数点数としての逆数を s = 1 / n {\displaystyle s=1/n} とおくと、 ⌊ x ⌋ {\displaystyle \lfloor x\rfloor } を床関数として
a mod n = a − ⌊ a s ⌋ n {\displaystyle a\,{\bmod {\,}}n=a-\lfloor as\rfloor n}
となる。 s {\displaystyle s} が十分な精度で計算される限り、これは誤差なく成り立つ。
m / 2 k {\displaystyle m/2^{k}} は近似にすぎないので、近似が正当となる a {\displaystyle a} の範囲を考える必要がある。 1 / n {\displaystyle 1/n} の近似誤差は
e = 1 n − m 2 k {\displaystyle e={\frac {1}{n}}-{\frac {m}{2^{k}}}}
なので、qの誤差は a e {\displaystyle ae} である。 a e < 1 {\displaystyle ae<1} 、すなわち a < 1 / e {\displaystyle a<1/e} である限り、この還元は正当である。 a ≥ 1 / e {\displaystyle a\geq 1/e} である場合も必ずしもこの関数が誤った値を返すわけではないが、 a {\displaystyle a} を先述の範囲内に収めることで一般の場合においての正当性を保証できる。
k {\displaystyle k} を大きく取ると、還元が正当となる a {\displaystyle a} の範囲は広がる一方、他の計算においてオーバーフローを生じる可能性がある。