Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper refines the Szabo and Tanaka type-II division algorithm for Residue Number Systems (RNS) to improve hardware implementation efficiency. It introduces a power-based RNS with moduli selected as powers of natural primes, enhancing dynamic range and bit efficiency. The work formalizes multi-factor scaling, mixed-radix conversion, and a novel divisor decomposition method, optimizing hardware structure and scalability for direct RNS division.
Power-of-prime moduli in Residue Number Systems unlock more efficient and scalable direct integer division hardware.
Residue Number Systems (RNS) offer efficient modular arithmetic and natural parallelism, but direct integer division in RNS remains a difficult and comparatively underdeveloped operation. This paper builds on the type-II division algorithm of Szabo and Tanaka and reformulates it for more efficient hardware implementation. A principal contribution is the introduction of a power-based RNS, in which moduli are selected as powers of natural primes, increasing dynamic range, improving bit efficiency, and providing greater flexibility for scaling during division. The paper further formalizes three decomposition methods required by the division process: multi-factor scaling for modulus-based division, mixed-radix conversion for base extension and comparison, and a new divisor decomposition method introduced in this work. Each method is supported by mathematical development, including analysis of modulus invalidation during computation. These results simplify the hardware structure of the algorithm and improve its scalability. Supported by hardware diagrams and performance tables, the work advances both the theory and practical implementation of direct RNS division.