Division of integers is called exact if the remainder is zero. We show
that the high-order part and the low-order part of the exact quotient
can be computed independently from each other. A sequential implement
ation of this algorithm is up to twice as fast as ordinary exact divis
ion and four times as fast as the general classical division algorithm
if the dividend is twice as long as the divisor. A shared-memory para
llel implementation on two processors gains another factor of two in s
peed. (C) 1996 Academic Press Limited