Design and implementation of an RNS division algorithm

In 1995 the authors introduced the main outlines of a new algorithm for division in residue number system, which can be applied to any moduli set. Simulation results proved that the algorithm was many times faster than most competitive published work. Determining the position of the most significant nonzero bit of any residue number in that algorithm is the major speed limiting factor. They customize the same algorithm to serve two specific moduli sets: (2/sup k/, 2/sup k/-1, 2/sup k-1/-1) and (2/sup k/+1, 2/sup k/, 2/sup k/-1), and thus, eliminate that speed limiting factor. Based on this work, hardware needed to determine most significant bit position has been reduced to a single adder. Therefore, computation time and hardware requirements are substantially improved. This would enable RNS to be a stronger force in building general purpose computers.