janmr blog

Multiple-Precision Subtraction

We now turn to multiple-precision subtraction for non-negative integers. The algorithm is very similar to that of multiple-precision addition, but some minor differences make it worth while considering subtraction separately.

We consider two -digit numbers, and , with (see a previous post on the number notation). We wish to compute an -digit result such that

where is some initial borrow, . Furthermore, a final borrow will indicate whether .

Let us first introduce a notation which Donald E. Knuth refers to as Iverson's convention: has value if is true and otherwise.

We now have the algorithm:

for . This is really just a formalization of the familiar pencil-and-paper method, but let us show that it does the right thing.

Note first that for . This is a consequence of the assumption for the initial borrow and the range of the operator. We next establish the relation

which holds since we have . We now observe that

We finally have

so . Since we have now established

and indicates whether .