6

ARITHMETIC OPERATIONS: DIVISION

Integer or finite length fractional numbers can be multiplied exactly, whenever sufficient length is allowed for the result. Division doesn't share this feature. As a matter of fact, division generally does not provide a finite length result. The accuracy must be defined beforehand by setting the unit in the least significant position (ulp) of the result. The number of algorithmic cycles will therefore depend on the desired accuracy, not on the operand length.

Digit recurrence algorithms represent the most common class of division techniques: a single quotient-digit is produced at each computation step. The classic pencil and paper method belongs to this class. The time complexity is thus a linear function of the desired number of quotient-digits. SRT division ([SWE1957], [ROB1958], [TOC1958]) has been widely used in computer applications. The digit recurrence algorithmic step mainly consists in an estimation of the greatest multiple of the divisor to be subtracted from the remainder.

Functional iteration is another class of algorithms. These algorithms use function-solving techniques to converge, from an initial estimation, toward the quotient with the required precision. The main feature of this method rests on the faster than linear convergence, typically quadratic. The main drawbacks are the step complexity and the need for additional computations to provide the final remainder, thus increasing the rounding complexity. The most used functional iteration techniques are based on Newton–Raphson convergence equations and Taylor–MacLaurin expansions (Goldschmidt's algorithm). This technique has been used in several commercial applications.

Very high radix and variable latency classes of algorithms are described in the literature ([OBE1995]). Their practical use is more limited and more justified for specific applications ([OBE1995], [BRI1993]).

A number of division methods, more or less related to the above four main classes, are described in the literature ([OBE1997], [PAR1999], [FLY2001], [ERC2004]).