A high-speed division algorithm in residue number system using parity-checking technique

Abstract

The residue number system (RNS) has computational advantages for large integer arithmetic because of its parallel, carry free, and high-speed arithmetic nature. However, overflow detection, sign detection, relative-magnitude detection, and division are highly time-consuming operations in RNS. Among them, the most interesting one is division because it can apply to modular arithmetic. To speed up the operation, Hiasat and Abdel-Aty-Zohdy proposed a high-speed division algorithm for RNS in 1997. Hiasat and Abdel-Aty-Zohdy's algorithm computes a temporal quotient according to the highest power of 2 in the dividend and the divisor. Nevertheless, the temporal quotient is underestimated such that the algorithm has redundant execution rounds. In this article, we improve Hiasat and Abdel-Aty-Zohdy's division algorithm by using parity checking. Our improvement can reduce the number of execution rounds by 50%.

[email protected]

E-mail: [email protected]

Keywords:

• Residue number system
• Division
• Sign detection

Notes

[email protected]

E-mail: [email protected]

E-mail: [email protected]