Low-cost residue number systems for computer arithmetic
Behrooz Parhami · 1976
The representation of integers by their residues with respect to a set of pairwise-prime moduli is known as the residue number representation system and has been shown to have several advantages over conventional number systems for digital computers. In this paper, residue systems are considered for which each modulus is of the form 2b-1. Such systems result in relatively high storage efficiency as well as simple algorithms for addition, subtraction multiplication, conversion, and reconversion; hence the name "low-cost." The question of existence for low-cost residue number systems is examined. It is shown that the additional storage requirement with respect to binary representation is at most one bit per word. Guidelines are given for optimal selection of the set of moduli to represent a desired range of integers. Algorithms for various operations in a low-cost residue system are described.