Publications [#318123] of John H. Reif

Journal articles or Book chapters PUBLISHED

1. Reif, JH; Tate, SR, Optimal size integer division circuits, undefined (January, 1989), pp. 264-273 [doi]
   (last updated on 2026/01/16)

   Abstract:
   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. Our circuits are logspace uniform; that is, they can be constructed by a deterministic Turing machine in space O(log n). Our results match the best known depth bounds for logspace uniform circuits, and are optimal in size. The general method of high order iterative formulas used is of independent interest as a way of efficiently using parallel processors to solve algebraic problems. In particular, our algorithm implies that any rational function can be evaluated in these complexity bounds. As an introduction to high order iterative methods we also present a circuit for finding polynomial reciprocals.