janmr blog

Multiple-Precision Addition

This post will cover a basic addition algorithm for multiple-precision non-negative integers. The algorithm is based upon that presented in Section 4.3.1, The Classical Algorithms, of The Art of Computer Programming, Volume 2, by Donald E. Knuth. The notation and bounds used in this post were presented in a previous post.

We consider adding two nn-digit numbers with n1n \geq 1, 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. Since bn1u,vbn1b^{n-1} \leq u, v \leq b^n - 1 we have 2bn1u+v2bn22 b^{n-1} \leq u+v \leq 2 b^n - 2 which, when using the fact that b2b \geq 2, leads to bn1u+vbn+11b^{n-1} \leq u+v \leq b^{n+1} - 1 (note how a tighter bound of the form bpu+vbq1b^p \leq u+v \leq b^q - 1 is not possible).

This means that u+vu+v can be represented using nn or n+1n+1 digits, so we set w=(wnw1w0)bw=(w_n \ldots w_1 w_0)_b.

Assuming k0k_0 is set to some initial value (more on this below) we now have the following algorithm:

wi(ui+vi+ki)  mod  bki+1(ui+vi+ki)/b\begin{aligned} w_i &\leftarrow (u_i + v_i + k_i) \;\text{mod}\; b \\ k_{i+1} &\leftarrow \lfloor (u_i + v_i + k_i)/b \rfloor \end{aligned}

for i=0,1,,n1i = 0, 1, \ldots, n-1, and finally wnknw_n \leftarrow k_n.

The algorithm sets the digits of ww such that w=u+v+k0w = u+v+k_0. This can be seen by first observing that p=p  mod  b+p/bbp = p \;\text{mod}\; b + \lfloor p/b \rfloor b for any integer pp. Using this relation on the variables set during the algorithm, we have

ui+vi+ki=wi+ki+1bu_i + v_i + k_i = w_i + k_{i+1} b

for i=0,1,,n1i = 0, 1, \ldots, n-1. We now have

u+v=i=0n1(ui+vi)bi=i=0n1(ui+vi+ki)bii=0n1kibi=i=0n1(wi+ki+1b)bii=0n1kibi=i=0n1wibi+knbnk0,\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 + k_n b^n - k_0, \end{aligned}

showing that w=u+v+k0w=u+v+k_0.

It is clear that each resulting digits of ww satisfies 0wib10 \leq w_i \leq b-1 for i=0,,n1i = 0, \ldots, n-1, as it should. The value of wnw_n, though, depends on knk_n.

Assume that 0ki10 \leq k_i \leq 1 for some i=0,,n1i=0, \ldots, n-1. Since ui+vi+kib1+b1+1=2b1u_i+v_i+k_i \leq b-1+b-1+1 = 2b-1 we see that ki+1=(ui+vi+ki)/b1k_{i+1} = \lfloor (u_i + v_i + k_i)/b \rfloor \leq 1. So if we have 0k010 \leq k_0 \leq 1 as initial value for the algorithm we have, by induction, that 0ki10 \leq k_i \leq 1 for all i=0,,ni=0, \ldots, n.

This shows how (not surprisingly) k0k_0 can be seen as an “initial carry” and how each ki+1k_{i+1} is 00 or 11, depending on whether a carry was produced from the iith digit addition.