ck ← carry

Note that in every loop iteration, the value of carry is 0 or 1, and the

value tmp lies between 0 and 2B ’ 1.

3.3.2 Subtraction

Let a = (ak’1 · · · a0 )B and b = (b ’1 · · · b0 )B be unsigned integers. Assume

that k ≥ ≥ 1. To compute the di¬erence c := a ’ b, we may use the same

3.3 Basic integer arithmetic 41

algorithm as above, but with the expression “ai + bi ” replaced by “ai ’ bi .”

In every loop iteration, the value of carry is 0 or ’1, and the value of tmp

lies between ’B and B ’1. If a ≥ b, then ck = 0 (i.e., there is no carry out of

the last loop iteration); otherwise, ck = ’1 (and b ’ a = B k ’ (ck’1 · · · c0 )B ,

which can be computed with another execution of the subtraction routine).

3.3.3 Multiplication

Let a = (ak’1 · · · a0 )B and b = (b ’1 · · · b0 )B be unsigned integers, with

k ≥ 1 and ≥ 1. The product c := a · b is of the form (ck+ ’1 · · · c0 )B , and

may be computed in time O(k ) as follows:

for i ← 0 to k + ’ 1 do ci ← 0

for i ← 0 to k ’ 1 do

carry ← 0

for j ← 0 to ’ 1 do

tmp ← ai bj + ci+j + carry

(carry, ci+j ) ← divmod(tmp, B)

ci+ ← carry

Note that at every step in the above algorithm, the value of carry lies

between 0 and B ’ 1, and the value of tmp lies between 0 and B 2 ’ 1.

3.3.4 Division with remainder

Let a = (ak’1 · · · a0 )B and b = (b ’1 · · · b0 )B be unsigned integers, with

k ≥ 1, ≥ 1, and b ’1 = 0. We want to compute q and r such that

a = bq + r and 0 ¤ r < b. Assume that k ≥ ; otherwise, a < b, and we can

just set q ← 0 and r ← a. The quotient q will have at most m := k ’ + 1

base-B digits. Write q = (qm’1 · · · q0 )B .

At a high level, the strategy we shall use to compute q and r is the

following:

r←a

for i ← m ’ 1 down to 0 do

qi ← r/B i b

r ← r ’ B i · qi b

One easily veri¬es by induction that at the beginning of each loop itera-

tion, we have 0 ¤ r < B i+1 b, and hence each qi will be between 0 and B ’ 1,

as required.

Turning the above strategy into a detailed algorithm takes a bit of work.

42 Computing with large integers

In particular, we want an easy way to compute r/B i b . Now, we could

in theory just try all possible choices for qi ” this would take time O(B ),

and viewing B as a constant, this is O( ). However, this is not really very

desirable from either a practical or theoretical point of view, and we can do

much better with just a little e¬ort.

We shall ¬rst consider a special case; namely, the case where = 1. In this

case, the computation of the quotient r/B i b is facilitated by the following,

which essentially tells us that this quotient is determined by the two high-

order digits of r:

Theorem 3.1. Let x and y be integers such that

0 ¤ x = x 2n + s and 0 < y = y 2n

for some integers n, s, x , y , with n ≥ 0 and 0 ¤ s < 2n . Then x/y =

x /y .

Proof. We have

x x s x

≥.

= +

y 2n

y y y

It follows immediately that x/y ≥ x /y .

We also have

y ’1

x x s x 1 x 1

¤

= + < + + + .

y 2n

y y y y y y y

Thus, we have x/y < x /y + 1, and hence, x/y ¤ x /y . 2

From this theorem, one sees that the following algorithm correctly com-

putes the quotient and remainder in time O(k) (in the case = 1):

carry ← 0

for i ← k ’ 1 down to 0 do

tmp ← carry · B + ai

(carry, qi ) ← divmod(tmp, b0 )

output the quotient q = (qk’1 · · · q0 )B and the remainder carry

Note that in every loop iteration, the value of carry lies between 0 and

b0 ¤ B ’ 1, and the value of tmp lies between 0 and B · b0 + (B ’ 1) ¤ B 2 ’ 1.

That takes care of the special case where = 1. Now we turn to the

general case ≥ 1. In this case, we cannot so easily get the digits qi of

the quotient, but we can still fairly easily estimate these digits, using the

following:

3.3 Basic integer arithmetic 43

Theorem 3.2. Let x and y be integers such that

0 ¤ x = x 2n + s and 0 < y = y 2n + t

for some integers n, s, t, x , y with n ≥ 0, 0 ¤ s < 2n , and 0 ¤ t < 2n .

Further suppose that 2y ≥ x/y. Then we have

x/y ¤ x /y ¤ x/y + 2.

Proof. For the ¬rst inequality, note that x/y ¤ x/(y 2n ), and so x/y ¤

x/(y 2n ) , and by the previous theorem, x/(y 2n ) = x /y . That proves

the ¬rst inequality.

For the second inequality, ¬rst note that from the de¬nitions, x/y ≥

x /(y +1), which is equivalent to x y’xy ’x ¤ 0. Now, the inequality 2y ≥

x/y is equivalent to 2yy ’ x ≥ 0, and combining this with the inequality

x y ’ xy ’ x ¤ 0, we obtain 2yy ’ x ≥ x y ’ xy ’ x, which is equivalent to

x/y ≥ x /y ’ 2. It follows that x/y ≥ x /y ’ 2. That proves the second

inequality. 2

Based on this theorem, we ¬rst present an algorithm for division with re-

mainder that works assuming that b is appropriately “normalized,” meaning

that b ’1 ≥ 2w’1 , where B = 2w . This algorithm is shown in Fig. 3.1.

Some remarks are in order:

1. In line 4, we compute qi , which by Theorem 3.2 is greater than or

equal to the true quotient digit, but exceeds this value by at most 2.

2. In line 5, we reduce qi if it is obviously too big.

3. In lines 6“10, we compute

(ri+ · · · ri )B ← (ri+ · · · ri )B ’ qi b.

In each loop iteration, the value of tmp lies between ’(B 2 ’ B) and

B ’ 1, and the value carry lies between ’(B ’ 1) and 0.

4. If the estimate qi is too large, this is manifested by a negative value

of ri+ at line 10. Lines 11“17 detect and correct this condition: the

loop body here executes at most twice; in lines 12“16, we compute

(ri+ · · · ri )B ← (ri+ · · · ri )B + (b ’1 · · · b0 )B .

Just as in the algorithm in §3.3.1, in every iteration of the loop in lines

13“15, the value of carry is 0 or 1, and the value tmp lies between 0

and 2B ’ 1.

It is quite easy to see that the running time of the above algorithm is

O( · (k ’ + 1)).

44 Computing with large integers

for i ← 0 to k ’ 1 do ri ← ai

1.

rk ← 0

2.

for i ← k ’ down to 0 do

3.

qi ← (ri+ B + ri+ ’1 )/b ’1

4.

if qi ≥ B then qi ← B ’ 1

5.

carry ← 0

6.

for j ← 0 to ’ 1 do

7.

tmp ← ri+j ’ qi bj + carry