Fast Power-of-Two RNS Scaling Algorithm for Large Dynamic Ranges

This paper presents a new efficient algorithm for scaling by power of two in the residue number system (RNS). It focuses on arbitrary moduli sets with large dynamic ranges. In this algorithm, in order to determine the remainder when dividing the number to be scaled by the scaling factor, an interval estimation of the RNS representation is used. The proposed algorithm requires only machine-precision integer and floating-point operations, and is well parallelized. The algorithm is implemented for CPU, as well as for GPU using CUDA C language.