Improving Digital Computer Performance Using Residue Number Theory

Abstract

Residue arithmetic has the interesting characteristic that in multiplication, addition and subtraction any digit in the result is dependent only on its two corresponding operand digits. Consequently, for these operations, residue arithmetic is inherently faster than the conventional weighted arithmetics. A system design approach for exploiting the desirable characteristics of both residue and conventional number theory in digital computers is the principal topic of this paper. Criteria for selecting the moduli, and general techniques for implementing the residue arithmetic operations by simple modifications of conventional circuitry are described. A specific system with a conventional word length of 25 bits and a residue system with moduli 128, 127, 63 and 31 are treated in detail, showing that in comparison to the conventional mode of computation, residue arithmetic addition and subtraction are 3 times faster and multiplication is 12 times faster. As an example of the usefulness of the approach, the problem of solving systems of simultaneous linear equations is considered. It is shown that in obtaining solutions by residue arithmetic, the residue mode computation time approaches one sixth that required in the conventional mode as the equation systems become more complex.