Error-free computation using multiple-modulus residue arithmetic

Author

Deborah Susan Crowell

Date of Award

6-1986

Degree Type

Thesis

Degree Name

Master of Science

Major

Computer Science

Major Professor

D. W. Straight

Committee Members

Michael Thomason, Eugene Wachspress

Abstract

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.

Recommended Citation

Crowell, Deborah Susan, "Error-free computation using multiple-modulus residue arithmetic. " Master's Thesis, University of Tennessee, 1986.
https://trace.tennessee.edu/utk_gradthes/13676