Log Depth Circuits For Division And Related Problems
- 25 August 2005
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 1-6
- https://doi.org/10.1109/sfcs.1984.715894
Abstract
We present optimal depth Boolean circuits (depth O(log n)) for integer division, powering, and multiple products. We also show that these three problems are of equivalent uniform depth and space complexity. In addition, we describe an algorithm for testing divisibility that is optimal for both depth and space.Keywords
This publication has 4 references indexed in Scilit:
- Comparison of arithmetic functions with respect to boolean circuit depthPublished by Association for Computing Machinery (ACM) ,1984
- Logarithmic depth circuits for algebraic functionsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1983
- On uniform circuit complexityJournal of Computer and System Sciences, 1981
- On Relating Time and Space to Size and DepthSIAM Journal on Computing, 1977