TABLE OF CONTENTS The residue number system is an integer number system whose most important property is that additions, subtractions, and multiplications are inherently carry-free. As a result we may add, subtract, or multiply numbers in one step regardless of the length of the numbers involved. Unfortunately, other arithmetic operations, like division, comparison, and sign detection, are very complex and slow. Another problem with the residue number system is that it is an integer number system and, as a result, it is very inconvenient to represent fractions. Consequently, the residue system has not been seriously considered for use in general-purpose computers. However, for some special-purpose applications such as many types of digital filters [6], in which the number of additions and multiplications is substantially greater than the number of invocations of magnitude comparison, overflow detection, division, and alike, the residue system can be very attractive.
A residue number system is characterized by a base that is not a single radix but an N-tuple of integers ( m N , m N ? 1, , m 1). Each of these m i ( i=1, 2, , N) is called a modulus. An integer X is represented in the residue number system by an N-tuple ( x N , x N ?1, , x 1) where x i is a nonnegative integer satisfying
where q i is the largest integer such that 0 ? x i ?( m
