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 constitutes the justification of the basic division algorithm.

Theorem 6.1 Fundamental Equation of Division Given two natural numbers a and b such that a < b, there exists two natural numbers q and r satisfying Ba = q.b + r, with q ∈ {0, 1, …,B − 1} and r < b.

The iterative application of the preceding theorem, that is,

with r(0) = X, generates the following relation,

so that

Assume that a procedure division_step has been defined

procedure division_step (a, b: in natural; q, r: out natural);

that computes q and r such that B.a = q.b + r, with q ∈ {0, 1, …, B − 1} and r < b. Then the following basic division algorithm is a straightforward application of (6.4) and (6.5).

Algorithm 6.1 Basic Division

r(0):=X;
for i in 1..p loop
  division_step (r(i − 1), Y, q(i), r(i));
end loop,

It generates the base-B representation q(1)q(2)…q(p) of Q and the remainder R = r(p). If B = 2 the division_step procedure is very simple.

Algorithm 6.2 Base-2 Division Step

z:=2*a-b;
if z<0 then q:=0; r:=2*a; else q:=1; r:=z; end if;

If B is greater than 2 the division step is more complex, namely:

Algorithm 6.3 Base-B Division Step

if B*a<b then q:=0; r:=B*a;
elsif B*a<2*b then q:=1; r:=B*a-b;
elsif B*a<3*b then q:=2; r:=B*a-(2*b);
..
elsif B*a<(B-1)*b then q:=B-2; r:=B*a-((B-2)*b);
else q:=B-1; r:=B*a-((B-1)*b);

Observe that at every step of Algorithm 6.1, the new remainder r(i) is equal to B.r(i − 1) − q(i).Y. If q(i) = 0 then r(i) = B.r(i − 1) and the preceding remainder r(i − 1) is said to be restored (actually, restored and shifted). For that reason, the basic division algorithm is also known as the restoring division algorithm.

Comment 6.1 If a previous alignment is necessary, instead of substituting Y by Y′ = B^m.Y, an alternative option is to substitute X by X′ = X/B and Y by Y′ = B^m−1.Y, and to 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

Observe that the substitution of X by X′ is equivalent to the substitution of the first algorithm step, namely,

by

Examples 6.1

1. Compute 12/15 with an accuracy of 8 fractional bits:

So Q = 11001100 = 204, R = 12, and 2⁸.12 = 204.15 + 12.

2. (Integer division) Given an 8-bit natural number X(X < 256) and a positive integer Y, the integer division of X by Y is computed as follows. The divisor Y is substituted by Y′ = Y.256, the accuracy is equal to p + m = 0 + 8 = 8 bits, and the final remainder R′ will be substituted by R = R′/256. As an example, assume that X = 124 and Y = 15:

Thus Q = 00001000 = 8, R = 1024/256 = 4, and 124 = 8.15 + 4.

The same operation can be performed taking into account Comment 6.1:

Thus Q = 00001000 = 8, R = 512/128 = 4, and 124 = 8.15 + 4.

3. Given a 6-bit natural number X and a 3-bit positive integer Y, compute X/Y with an accuracy of p = 4. To ensure that X < Y, the divisor is substituted by Y′ = Y.2⁶, the division is performed with an accuracy of p = 4 + 6 = 10, and the final remainder will be divided by 2⁶. Assume that X = 101011 (43) and Y = 111 (7), so that Y′ = 111000000:

Thus

so that

Observe that Y′ is a multiple of 2⁶, so that the subtraction 2.r(i) − Y′ is performed with the four (highlighted) most significant bits of 2.r(i) and Y′; the other bits of 2.r(i) are just propagated to the next step.

Another observation is that all numbers are even. A better solution is to substitute Y by Y′ = Y.2⁵ and X by X/2 (Comment 6.1). Then 2.r(0) = X = 000101011. The computation is the same as before without the final bit (always equal to 0). The final result is

so that

Let us point out that most scientific hand calculators feature integer binary operations. Therefore, to produce a nonzero quotient, the initial multiplication of the dividend by 2^p is compulsory.

Algorithm 6.3 is quite unpractical. A better solution consists in looking first for a tentative value q_t of q. This process assumes that a normalization procedure sets both a and b as n-digit natural numbers such that a < b and Bⁿ > b ≥ Bⁿ⁻¹; that is, the leftmost digit of b is non-zero. The input parameters of the division_step procedure are a and b. One defines the truncated values a_t and b_t of a and b as follows (/ stands for integer division):

Observe that, as a < b, a_t < b/Bⁿ⁻³ < Bⁿ/Bⁿ⁻³ = B³; b_t < Bⁿ/Bⁿ⁻² = B² and b_t ≥ Bⁿ⁻¹/Bⁿ⁻² = B.

The tentative value of q, that is, q_t, is computed from

A 5-input (B-ary) look-up table (LUT) may be used as a fast computing device for that purpose.

Lemma 6.1 Given an n-digit dividend X, an n-digit divisor Y, and a remainder r(i) such that (/ stands for integer division)

and defining q_t as

then the correct value of q = B.r(i)/Y is either q_t or q_t − 1, that is,

From relations (6.8) and (6.9), it is obvious that Bⁿ⁻¹ ≤ Y ≤ Bⁿ − 1, while q_t ≤ B − 1.

If the k most significant digits of a given divisor Y are equal to 0, then a previous (normalizing) step will require substituting Y by Y.B^k so that Y.B^k ≥ Bⁿ⁻¹, while r(i) may be assumed an n-digit number with any number of zeros upfront. If an n-digit dividend X is given greater then the n-digit divisor Y, then a previous (normalizing) step will require substituting X by X/B.

Proof The rightmost part of inequality (6.10) (/ stands for real division) is derived from

where α stands for B.r(i) − r_t(i).Bⁿ⁻²; so α < Bⁿ⁻² and

The leftmost part of inequality (6.10) is proven as follows.

Equation (6.8) can be written

while (6.9) can be written

Using (6.13) in (6.14),

where β stands for Y − Y_t.Bⁿ⁻²; so β < Bⁿ⁻², then, as q_t ≤ B − 1

allowing (6.15) to be written

or

which completes the proof.

Algorithm 6.4 Restoring Base-B Division Step

at:=a/B**(n-3); bt:=b/B**(n-2);
qt:=at/bt;
remainder:=B*a-qt*b;
if remainder<0 then q:=qt-1; r:=remainder+b;
else q:=qt; r:=remainder; end if;

In this case, the restoring operation consists of adding the divisor to the remainder whenever the latter is negative. Then the remainder is iteratively shifted as in the basic division algorithm.

Example 6.2 Compute 752024/876544 (base 10):

So