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 nn-digit numbers, u=(un1u1u0)bu=(u_{n-1} \ldots u_1 u_0)_b and v=(vn1v1v0)bv=(v_{n-1} \ldots v_1 v_0)_b, with n1n \geq 1 (see a previous post on the number notation). We wish to compute an nn-digit result w=(wn1w1w0)bw=(w_{n-1} \ldots w_1 w_0)_b such that

w=(uvk0)  mod  bnw = (u - v - k_0) \;\text{mod}\; b^n

where k0k_0 is some initial borrow, 0k010 \leq k_0 \leq 1. Furthermore, a final borrow knk_n will indicate whether u<v+k0u < v+k_0.

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

We now have the algorithm:

wi(uiviki)  mod  b,ki+1[ui<vi+ki],\begin{aligned} w_i &\leftarrow (u_i - v_i - k_i) \;\text{mod}\; b, \\ k_{i+1} &\leftarrow [u_i < v_i + k_i], \end{aligned}

for i=0,1,,n1i = 0, 1, \ldots, n-1. 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 0ki10 \leq k_i \leq 1 for i=0,1,,n1i = 0, 1, \ldots, n-1. This is a consequence of the assumption 0k010 \leq k_0 \leq 1 for the initial borrow and the range of the [][\cdot] operator. We next establish the relation

uivikib=[ui<vi+ki],-\left\lfloor \frac{u_i-v_i-k_i}{b} \right\rfloor = [u_i < v_i + k_i],

which holds since we have b=0(b1)1uiviki(b1)00=b1-b = 0-(b-1)-1 \leq u_i-v_i-k_i \leq (b-1)-0-0 = b-1. We now observe that

uiviki=(uiviki)  mod  b+uivikibb=(uiviki)  mod  b[ui<vi+ki]b=wiki+1b.\begin{aligned} u_i-v_i-k_i &= (u_i - v_i - k_i) \;\text{mod}\; b + \left\lfloor \frac{u_i-v_i-k_i}{b} \right\rfloor b \\ &= (u_i - v_i - k_i) \;\text{mod}\; b - [u_i < v_i + k_i] b \\ &= w_i - k_{i+1} b. \end{aligned}

We finally have

uv=i=0n1(uivi)bi=i=0n1(uiviki)bi+i=0n1kibi=i=0n1(wiki+1b)bi+i=0n1kibi=i=0n1wibii=0n1ki+1bi+1+i=0n1kibi=wknbn+k0,\begin{aligned} u - v &= \sum_{i=0}^{n-1} (u_i-v_i) b^i = \sum_{i=0}^{n-1} (u_i-v_i-k_i) b^i + \sum_{i=0}^{n-1} k_i b^i \\ &= \sum_{i=0}^{n-1} (w_i-k_{i+1} b) b^i + \sum_{i=0}^{n-1} k_i b^i = \sum_{i=0}^{n-1} w_i b^i - \sum_{i=0}^{n-1} k_{i+1} b^{i+1} + \sum_{i=0}^{n-1} k_i b^i \\ &= w - k_n b^n + k_0, \end{aligned}

so uvk0=wknbnu-v-k_0 = w-k_n b^n. Since 0wbn10 \leq w \leq b^n-1 we have now established

w=(uvk0)  mod  bn,w = (u - v - k_0) \;\text{mod}\; b^n,

and knk_n indicates whether u<v+k0u < v+k_0.