Integer Division in Residue Number Systems Markus A. Hitz Erich Kaltofen This contribution to the ongoing discussion of division algorithms for residue number systems (RNS) is based on Newton iteration for computing the reciprocal. An extended RNS withtwice thenumberof moduli provides the range required for multiplication and scaling. Separation of the algorithm description from its RNS implementation achievesa high level of modularity, and makes the complex ity analysis more transparent. The number of iterations needed is logarithmic in the size of the quotient for a fixed startvalue. With preconditioning it becomes the logarithm of the input bit size. An implementation of the conversion to mixed radix representation is outlined in the appendix. Department of Computer Science, Rensselaer Polytechnic Institute, Troy, NY cs-93-9
Integer Division in Residue Number Systems
Markus A. Hitz
Erich Kaltofen
This contribution to the ongoing discussion of division algorithms for residue number systems (RNS) is based on Newton iteration for computing the reciprocal. An extended RNS withtwice thenumberof moduli provides the range required for multiplication and scaling. Separation of the algorithm description from its RNS implementation achievesa high level of modularity, and makes the complex ity analysis more transparent. The number of iterations needed is logarithmic in the size of the quotient for a fixed startvalue. With preconditioning it becomes the logarithm of the input bit size. An implementation of the conversion to mixed radix representation is outlined in the appendix.
Department of Computer Science, Rensselaer Polytechnic Institute, Troy, NY
cs-93-9