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.