Davida, George I.; Litow, Bruce Fast parallel arithmetic via modular representation. (English) Zbl 0736.68040 SIAM J. Comput. 20, No. 4, 756-765 (1991). Summary: An almost uniform \(NC^ 1\) circuit family for integer division is presented. The circuit size is \(O(n^ 6/\log(n))\). The circuit design is based on modular representation for integers below \(2^ n\). In particular, a very efficient technique is introduced for computing “\(a<b\)?” when \(a\) and \(b\) are in modular representation. This leads to a uniform \(NC^ 1\) circuit of \(O(n^ 2)\) size for comparison of integers in modular representation. Cited in 10 Documents MSC: 68Q25 Analysis of algorithms and problem complexity 68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) Keywords:almost uniform; circuit; modular; comparison; parallelism; combinational; division PDF BibTeX XML Cite \textit{G. I. Davida} and \textit{B. Litow}, SIAM J. Comput. 20, No. 4, 756--765 (1991; Zbl 0736.68040) Full Text: DOI OpenURL