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 all currently-known constructions ... 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 FOM). ... more >>>