Barrett reduction

In modular arithmetic, Barrett reduction is a reduction algorithm introduced in 1986 by P.D. Barrett. A naive way of computing In modular arithmetic, Barrett reduction is a reduction algorithm introduced in 1986 by P.D. Barrett. A naive way of computing would be to use a fast division algorithm. Barrett reduction is an algorithm designed to optimize this operation assuming n {displaystyle n} is constant, and a < n 2 {displaystyle a<n^{2}} , replacing divisions by multiplications. Let s = 1 / n {displaystyle s=1/n} be the inverse of n {displaystyle n} as a floating point number. Then where ⌊ x ⌋ {displaystyle lfloor x floor } denotes the floor function. The result is exact, as long as s {displaystyle s} is computed with sufficient accuracy.