An overview of high-performance computing using the residue number system

A residue number system (RNS) is a non-positional number system, an alternative to a binary representation of numbers. In RNS, a large integer is represented as a set of smaller numbers, which are the remainders (“residues”) of dividing its original value by some moduli. An exciting feature of the RNS is that addition, subtraction, and multiplication with each residue are performed independently, which provides parallel, carry-free, and high-speed computer arithmetic. On the other hand, non-modular operations that require estimating the magnitude of a number by its residues are challenging to implement in RNS since there is no parallel form for them.
This paper provides an overview of research on the implementation and practical application of high-performance computational techniques for RNS. More specifically, the paper addresses the following two aspects:

• Existing techniques for performing the most critical non-modular operations: reverse conversion, magnitude comparison, sign identification, and division;
• How RNS arithmetic finds practical application in cloud environments, blockchain technologies, multiple-precision computation, and deep neural networks.

The research was aimed at the wider use of non-positional number systems in resource-intensive applications.