### Associative table lookup processing for multioperand residue arithmeticAssociative table lookup processing for multioperand residue arithmetic

Access Restriction
Subscribed

 Author Papachristou, Christos A. Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1987 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science 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 $\textit{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 $\textit{M},$ and also in multiplication mod $\textit{M}$ if $\textit{M}$ is prime. To treat the more difficult case of $\textit{M}$ nonprime, a recursive procedure was developed for computing the 2-operand multiplication recurrencies mod $\textit{M}.$ The basis of this technique is the precedence relationships associated with a tree representation of the factors of $\textit{M}.$ It is then shown that the general $\textit{D}-operand$ multiplication mod M, D > 2 and $\textit{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. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 1987-04-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 34 Issue Number 2 Page Count 21 Starting Page 376 Ending Page 396

#### Open content in new tab

Source: ACM Digital Library