Optimal size integer division circuits
John H. Reif · 1989
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 Ο(M(n)) and depth Ο(lognlog logn), where M(n) is the size complexity of Ο(logn) depth integer multiplication circuits. Currently, M(n) is known to be Ο(nlogn 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 Ο(n logc n) for any c, and simultaneous depth less than Ω(log2 n). Our circuits are logspace uniform; that is, they can be constructed by a deterministic Turing machine in space Ο(log n).