Optimal Size Integer Division Circuits
- UNCG Author/Contributor (non-UNCG co-authors, if there are any, appear on document)
- Stephen R. Tate, Professor and Department Head (Creator)
- Institution
- The University of North Carolina at Greensboro (UNCG )
- Web Site: http://library.uncg.edu/
Abstract: Division is a fundamental problem for arithmetic and algebraic computation. This
paper describes Boolean circuits (of bounded fan-in) for integer division (finding reciprocals) that
have size O(M(n)) and depth O(lognloglogn), where M(n) is the size complexity of O(logn)
depth integer multiplication circuits. Currently, M(n) is known to be O(n logn log log n), but any
improvement in this bound that preserves circuit depth will be reflected by a similar improvement
in the size complexity of our division algorithm. Previously, no one has been able to derive a
division circuit with size O(n logc n) for any c, and simultaneous depth less than Ω(log2 n). The
circuit families described in this paper are logspace uniform; that is, they can be constructed by a
deterministic Turing machine in space O(log n).
The results match the best-known depth bounds for logspace uniform circuits, and are optimal
in size.
The general method of high-order iterative formulas is of independent interest as a way of efficiently
using parallel processors to solve algebraic problems. In particular, this algorithm implies
that any rational function can be evaluated in these complexity bounds.
As an introduction to high-order iterative methods a circuit is first presented for finding polynomial
reciprocals (where the coefficients come from an arbitrary ring, and ring operations are unit cost
in the circuit) in size O(PM(n)) and depth O(logn log logn), where PM(n) is the size complexity
of optimal depth polynomial multiplication.
Optimal Size Integer Division Circuits
PDF (Portable Document Format)
1793 KB
Created on 3/14/2011
Views: 2005
Additional Information
- Publication
- SIAM Journal on Computing Vol. 19, No. 5, pp. 912-924, October 1990
- Language: English
- Date: 1990
- Keywords
- Algebraic computation, Integer division, Circuit complexity, Powering