Skip to main content

Optimal size integer division circuits

Publication ,  Journal Article
Reif, JH; Tate, SR
Published in: SIAM Journal on Computing
January 1, 1990

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(log n log log n), where M(n) is the size complexity of O(log n) depth integer multiplication circuits. Currently, M(n) is known to be O(n log n 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(log n log log n), where PM(n) is the size complexity of optimal depth polynomial multiplication.

Duke Scholars

Published In

SIAM Journal on Computing

DOI

ISSN

0097-5397

Publication Date

January 1, 1990

Volume

19

Issue

5

Start / End Page

912 / 924

Related Subject Headings

  • Computation Theory & Mathematics
  • 4903 Numerical and computational mathematics
  • 4901 Applied mathematics
  • 4613 Theory of computation
  • 0802 Computation Theory and Mathematics
  • 0101 Pure Mathematics
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Reif, J. H., & Tate, S. R. (1990). Optimal size integer division circuits. SIAM Journal on Computing, 19(5), 912–924. https://doi.org/10.1137/0219064
Reif, J. H., and S. R. Tate. “Optimal size integer division circuits.” SIAM Journal on Computing 19, no. 5 (January 1, 1990): 912–24. https://doi.org/10.1137/0219064.
Reif JH, Tate SR. Optimal size integer division circuits. SIAM Journal on Computing. 1990 Jan 1;19(5):912–24.
Reif, J. H., and S. R. Tate. “Optimal size integer division circuits.” SIAM Journal on Computing, vol. 19, no. 5, Jan. 1990, pp. 912–24. Scopus, doi:10.1137/0219064.
Reif JH, Tate SR. Optimal size integer division circuits. SIAM Journal on Computing. 1990 Jan 1;19(5):912–924.

Published In

SIAM Journal on Computing

DOI

ISSN

0097-5397

Publication Date

January 1, 1990

Volume

19

Issue

5

Start / End Page

912 / 924

Related Subject Headings

  • Computation Theory & Mathematics
  • 4903 Numerical and computational mathematics
  • 4901 Applied mathematics
  • 4613 Theory of computation
  • 0802 Computation Theory and Mathematics
  • 0101 Pure Mathematics