Fast Parallel Arithmetic via Modular Representation
George I. Davida, Bruce E. Litow · SIAM Journal on Computing · 1991
An almost uniform $NC^1 $ circuit family for integer division is presented. The circuit size is $O(n^6 / \log (n))$. The circuit design is based on modular representation for integers below $2^n $. In particular, a very efficient technique is introduced for computing “$a < b$?” when a and b in modular representation. This leads to a uniform $NC^1 $ circuit of $O(n^2 )$ size for comparison of integers in modular representation.