What could be easier than integer addition? After all, you've learned this since your first years in elementary school.

Instead, let's now describe an algorithm for adding two integers. Before you read on, come up with your own description of how to find the sum of two integers.

Algorithm X.1: Adding two non-negative integers

Suppose we want to add two non-negative integers $M$ and $N$.

Input: two non-negative integers $M$ and $N$.
Output: a non-negative integer.

1. Set a carry value to $0$.
2. Label the digits of $M$ and $N$ as $M_m$, ..., $M_0$ and $N_n$, ..., $N_0$, where the subscript represents the digit corresponding to $10^k$.
3. Assume $M_{m + 1} = M_{m + 2} = \cdots = 0$; the same for the digits of $N$.

4. Let the digits of the sum be represented by $S_k$.
5. Let $\ell$ be assigned the value $0$.
6. Add the carry value, $M_\ell$ and $N_\ell$ and assign this to $S_\ell$.
7. If $S_\ell \ge 10$, subtract $10$ from $S_\ell$ and set the carry value to $1$,
8. otherwise, set the carry value to $0$.
9. If $\ell = \max{m, n} + 1$, we are finished,
10. otherwise, add $1$ to the value of $\ell$ and return to Step 5.

Note that by labelling each of the digits with an integer, it is reasonably straight-forward to describe how to add these two integers together.

Additionally, note that there is only one carry value, and it is constantly reused, as opposed to the more traditional addition where the carries are added to each next column:

          111   11
           97513253
         +  3982358
	   --------
	  101495611

This example also indicates why it is necessary to continue until $\ell = \max{m, n} + 1$, and not just $\max{m, n}$.

Algorithm: Adding two negative integers

Input: two negative integers $M$ and $N$.
Output: an integer.

If $M < 0$ and $N < 0$, to calculate $M + N$, we do the following:

1. Apply Algorithm X.1 to add $-M$ and $-N$ and let this sum be $S$.
2. Negate the result $-S$.

Algorithm: Subtracting a negative integer from a non-negative integer

Input: a non-negative integer $M$ and and a negative integer $N$.
Output: an integer.

If $M > 0$ and $N < 0$, to calculate $M - N$, we do the following:

1. Apply Algorithm X.1 to add $M$ and $-N$ and let this sum be $S$.

Algorithm: Subtracting a non-negative integer from a negative integer

If $M < 0$ and $N > 0$, to calculate $M - N$, we do the following:

1. Apply Algorithm X.1 to add $-M$ and $N$ and let this sum be $S$.
2. Negate the result $-S$.

Algorithm: Adding multiple integers

Describe an algorithm for adding $k$ integers, where $k \ge 0$.

For this algorithm, you could try to describe a more complex algorithm that tries to add all of the integers simultaneously:

         454453
          860534
          816415
          170465
          484459
           56869
          684442
          285840
          214180
          307450
        + 189265
         -------
         4069919

However, this would require you to create an entirely new algorithm; and the computer would have to have instructions on adding $k + 1$ numbers. Instead, you should hopefully come up with an algorithm that allows you to add $k$ positive integers by adding the $k$^th positive integer onto the sum of the first $k - 1$ integers.

You can compare your solution with ours.