Complexity of integer division
Paul W. Beame, Stephen A. Cook, and H. James Hoover. Log depth circuits for division and related problems
- integer divisibility is in L
Andrew Chiu, George Davida, and Bruce Litow. Division in logspace-uniform NC1
- integer division is in L
Uniform constant-depth threshold circuits for division and iterated multiplication
- integer division is in DLOGTIME-uniform TC0
- survey of the recents from the previous three
Q: Why is the classical binary long division not in L?
A: L computable means using O(log n) working memory where n is the number of bits. Assume input is given read-only and output is write-only and doesn’t count towards working memory.