janmr blog

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 $n$-digit numbers with $n \geq 1$, $u=(u_{n-1} \ldots u_1 u_0)_b$ and $v=(v_{n-1} \ldots v_1 v_0)_b$. Since $b^{n-1} \leq u, v \leq b^n - 1$ we have $2 b^{n-1} \leq u+v \leq 2 b^n - 2$ which, when using the fact that $b \geq 2$, leads to $b^{n-1} \leq u+v \leq b^{n+1} - 1$ (note how a tighter bound of the form $b^p \leq u+v \leq b^q - 1$ is not possible).

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

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

$$\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, \ldots, n-1$, and finally $w_n \leftarrow k_n$.

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

$$u_i + v_i + k_i = w_i + k_{i+1} b$$

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

$$\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+k_0$.

It is clear that each resulting digits of $w$ satisfies $0 \leq w_i \leq b-1$ for $i = 0, \ldots, n-1$, as it should. The value of $w_n$, though, depends on $k_n$.

Assume that $0 \leq k_i \leq 1$ for some $i=0, \ldots, n-1$. Since $u_i+v_i+k_i \leq b-1+b-1+1 = 2b-1$ we see that $k_{i+1} = \lfloor (u_i + v_i + k_i)/b \rfloor \leq 1$. So if we have $0 \leq k_0 \leq 1$ as initial value for the algorithm we have, by induction, that $0 \leq k_i \leq 1$ for all $i=0, \ldots, n$.

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