OPTIMAL SIZE INTEGER DIVISION CIRCUITS 913

computation. In 3 (dealing with polynomial reciprocals) we use a circuit model with operations in an arbitrary ring as the basis. Optimal algorithms have been known for quite some time for addition and subtraction, and good algorithms exist for multiplication. Ifwe let SM(n) be the sequential time complexity of multiplication and M(n) be the size complexity of O(logn) depth multiplication using the circuit model, then the best known results are due to SchSnhage and Strassen [11] who give an algorithm based on discrete Fourier transforms with SM(n) O(nlognlog logn) and M(n) O(n lognlog log n). The problem of integer division was examined by Cook in his Ph.D. thesis [5], and it was shown by using second-order Newton approximations that the sequential time complexity of taking reciprocals is asymptotically the same as that of multiplication. Unfortunately, this method does not carry over to the circuit model for size O(M(n)) division circuits, we require depth t(log 2 n) from a direct translation of Cook’s method of Newton iteration. In addition, no one has been able to derive a new method for integer division with size O(M(n)) and depth less than ft(log 2 n