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.
No takes yet. Share an insight, caveat, or question.
Beame et al. (1986) studied this question.
Synapse has enriched 5 related papers. Consider them for comparative context: