Synthesis of Arithmetic Circuits: FPGA, ASIC and Embedded Systems

6.1 NATURAL NUMBERS

Let X and Y be two natural numbers with Y > 0. Define Q and R, respectively, as the quotient and the remainder of the division of X by Y, with an accuracy of p fractional base-B digits:

where Q and R are natural numbers, and R < Y. In other words,

so that the unit in the least significant position (ulp) of Q.B^−p and R.B^−p is equal to B^−p. In the particular case where p = 0, that is,

Q and R are the quotient and the remainder of the integer division of X by Y.

The basic algorithm applies to operands X and Y such that

In the general case, to ensure that X < Y, a previous alignment step is necessary. Assume that X is an m-digit base-B number, that is, X < B^m; then

substitute Y by Y′ = B^m.Y, so that Y′ ≥ B^m.1> X;

compute the quotient Q and the remainder R′ of the division of X by Y′, with an accuracy of p + m fractional base-B digits, that is,

so that

The next theorem ...