A Computer for Solving Linear Simultaneous Equations Using the Residue Number System

Abstract

The design of a special-purpose digital computer for solving simultaneous equations which operates with numbers coded in the residue number system is described. Since addition, subtraction or multiplication can be done in one-bit time using this coding, Gauss-Seidel iteration can be done in a very fast and efficient manner. The computer has been arbitrarily designed to solve dense systems of equations with as many as 128 unknowns and sparse systems with as many as 512 unknowns. Operating at a 500-kc clock rate, the computer would be able to perform one complete iteration on a system with 128 unknowns 30 times faster than an IBM 704. Using a 7 digit residue code requiring a 42-bit word, the computer would provide solutions of up to 4 significant figures. By using the best presently obtainable components, computing speed can be increased by a factor of 5. The size of the system which can be handled and the number of significant digits which can be obtained in the solutions can also be extended if desired. The speed of computation obtained with this computer is made possible by the combination of the one-bit-time arithmetic operations obtainable with residue numbers, the high data rate possible with a magnetic drum, and the sequential nature of the Gauss-Seidel iteration procedure. The digital techniques which have been developed to realize a computer of this type include methods of encoding decimal numbers into residue representation, rescaling residue numbers, and decoding residue numbers into binary coded decimal form.