Residue Number System (RNS) has computational advantages for very large integer arithmetic because of its nature of parallel, carry free, and high-speed arithmetic. However, overflow detection, sign detection,relative-magnitude detection, and division in RNS are very difficult problems. In 1995, Hiasat and Zohdy proposed a high-speed division algorithm for RNS. Their algorithm computes the temporal quotient according to the highest powers in dividend and divisor. However, the temporal quotient is underestimated. In this paper, we improve Hiasat and Zohdy’s division algorithm in RNS by additionally dealing with the highest two bits of dividend and divisor. Our improvement reduces the number of execution rounds by 25%.
