Log depth circuits for division and related problems. (English) Zbl 0619.68047

Beame, Paul W.; Cook, Stephen A.; Hoover, H. James

SIAM J. Comput. 15, 994-1003 (1986).

We present optimal depth Boolean ciruits (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.

MSC:

68Q25	Analysis of algorithms and problem complexity
68Q05	Models of computation (Turing machines, etc.) (MSC2010)
94C10	Switching theory, application of Boolean algebra; Boolean functions (MSC2010)

Keywords:

circuit depth; circuit complexity; depth complexity; optimal depth Boolean ciruits; integer division; powering; multiple products; space complexity; algorithm; divisibility