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 .
Commenting is not possible for this post, but feel free to leave a question,
correction or any comment by using the contact page