Residual Numbering System


A Residue Number System (RNS) represents a large integer using a set of smaller integers, so that computation may be performed more efficiently. It relies on the Chinese remainder theorem of modular arithmetic for its operation, a mathematical idea from Sun Tsu Suan-Ching (Master Sun’s Arithmetic Manual) in the 4th century AD.

Things we have, of which we know not the number.
If we count them by 3, the remainder is 2.
If we count them by 5, the remainder is 3.
If we count them by 7, the remainder is 2.
How many thing have we?
The answer is, 23.


My work in RNS consisted in the development of efficient implementations in hardware, through the development of improved arithmetic units, namely multipliers, and the description of a more balanced moduli set (2^{n+1};2^{2n};2^{n-1}). I've also studied the usage of RNS in Digital Signal Processors (DPS).

For more details about this subject and the developed work, please take a look to my publications page.

Pros and Cons of RNS

  • The RNS consists in dividing the binary representation into several residual numbers and operating individually and in parallel on each one.
  • Each residue is the remainder obtained by the division of the binary representation by each of the elements of the moduli set.

    Disadvantages of RNS

  • Dynamic range is not a power of 2;
  • A difficult overflow detection;
  • Requires conversion form and to the binary system;
  • Only addition and multiplication operations can be performed.

    Advantages of RNS

  • Smaller and independent residues are obtained;
  • Faster calculation speed;
  • Smaller area.

Small example of RNS

Using the moduli set (2^{n+1};2^n) for n = 3

Figure of RNS example