Error-free computation using multiple-modulus residue arithmetic

Multiple-modulus residue arithmetic (MMRA) is a method of performing certain arithmetic computations (+, -, *, /) on the set of order-N Farey fractions (F_N) in an environment totally free of machine roundoff error. MMRA provides a method of representing elements in the set Fff on unique ordered n-tuples of integers, called standard residue representations with respect to the base vector. Arithmetic operations on elements in F_N are replaced by corresponding operations on the standard residue representations. These computations are performed upon the ordered n-tuples in componentwise fashion with respect to the base vector using residue arithmetic. If the resultant standard residue representation corresponds to an element in F_N, the answer is recovered totally free of machine roundoff error.

The theory and implementation of multiple-modulus residue arithmetic is discussed. Then specific aspects of multiple-modulus residue arithmetic are compared and contrasted to single-modulus residue arithmetic, concluding with recommendations for further research.