Loading...
Please wait, while we are loading the content...
Similar Documents
OPTIMAL SIZE INTEGER DIVISION CIRCUITS 913
| Content Provider | CiteSeerX |
|---|---|
| Abstract | 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) |
| File Format | |
| Access Restriction | Open |
| Subject Keyword | Optimal Size Integer Division Circuit Circuit Model Sequential Time Complexity Known Result Arbitrary Ring Lognlog Log New Method Optimal Algorithm Polynomial Reciprocal Size Complexity Nlognlog Logn Integer Division Discrete Fourier Transforms Direct Translation Second-order Newton Approximation Newton Iteration Good Algorithm Division Circuit Depth Multiplication |
| Content Type | Text |
| Resource Type | Thesis |
