Arithmetic and Logic in Computer Systems

9

Residue Number Operations

Since in Residue Number Systems (RNS) the moduli are independent of each other, there is no carry propagation among them. The operations based on each modulus can be performed in parallel, and the RNS computations can be completed more quickly – an attractive feature for people who need high-speed arithmetic operations.

9.1 RNS ADDITION, SUBTRACTION AND MULTIPLICATION

Suppose two numbers, X and Y, are represented as

and

in RNS. We use ⊗ to represent the operator of addition, subtraction and multiplication, and let

If

the arithmetic in RNS can be expressed as follows:

For example, if m₁ = 5, m₂ = 3, m₃ = 2, then

and

From the definition of the mod operation, all moduli are positive. x_i may be less than y_i which yields x_i − y_i < 0. In the mod operation, if x