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

Davida, George I.; Litow, Bruce

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.

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