A high-speed division algorithm in residue number system using parity-checking technique
- 1 June 2004
- journal article
- other
- Published by Taylor & Francis in International Journal of Computer Mathematics
- Vol. 81 (6) , 775-780
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%.Keywords
This publication has 8 references indexed in Scilit:
- New approach to integer division in residue number systems2002
- Design and implementation of an RNS division algorithm2002
- A high-speed division algorithm for residue number system2002
- A novel division algorithm for the residue number systemIEEE Transactions on Computers, 1992
- A new residue number system division algorithmComputers & Mathematics with Applications, 1990
- Division and sign detection algorithms for residue number systemsComputers & Mathematics with Applications, 1984
- General Division in the Symmetric Residue Number SystemIEEE Transactions on Computers, 1973
- Division and Overflow Detection in Residue Number SystemsIEEE Transactions on Electronic Computers, 1962