The essential idea in the fast parallel computation of division and
related problems is that of Chinese remainder representation
(CRR) -- storing a number in the form of its residues modulo many
small primes. Integer division provides one of the few natural
examples of problems for which ... more >>>

Integer division has been known to lie in P-uniform TC^0 since
the mid-1980's, and recently this was improved to DLOG-uniform
TC^0. At the time that the results in this paper were proved and
submitted for conference presentation, it was unknown whether division
lay in DLOGTIME-uniform TC^0 (also known as ... more >>>