Associative table lookup processing for multioperand residue arithmetic

Publisher Website
Google Scholar
Abstract
This paper investigates the complexity of multioperand residue addition and multiplication implemented by associative table lookup processing. The complexity measure used is the size of the associative memory, that is, the number of matching words in memory. This measure largely depends on the residue recurrencies, or multiplicities, in the addition and multiplication tables module M . The major effort in this work is to evaluate the recurrencies in simultaneous multioperand residue addition and multiplication. The evaluation is simple in case of addition mod M , and also in multiplication mod M if M is prime. To treat the more difficult case of M nonprime, a recursive procedure was developed for computing the 2-operand multiplication recurrencies mod M . The basis of this technique is the precedence relationships associated with a tree representation of the factors of M . It is then shown that the general D -operand multiplication mod M, D > 2 and M nonprime, can be reduced to the 2-operand case by isomorphic transformation. Computation results of 2-operand residue arithmetic operations are provided. Applications to RNS arithmetic implementation are discussed.