×

Fast parallel arithmetic via modular representation. (English) Zbl 0736.68040

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.

MSC:

68Q25 Analysis of algorithms and problem complexity
68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
PDF BibTeX XML Cite
Full Text: DOI