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 -digit numbers with , and . Since we have which, when using the fact that , leads to (note how a tighter bound of the form is not possible).

This means that can be represented using or digits, so we set .

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

for , and finally .

The algorithm sets the digits of such that . This can be seen by first observing that for any integer . Using this relation on the variables set during the algorithm, we have

for . We now have

showing that .

It is clear that each resulting digits of satisfies for , as it should. The value of , though, depends on .

Assume that for some . Since we see that . So if we have as initial value for the algorithm we have, by induction, that for all .

This shows how (not surprisingly) can be seen as an “initial carry” and how each is or , depending on whether a carry was produced from the th digit addition.