At this point, we could ask you to write an algorithm for multiplying two positive integers; however, this is actually a very complex algorithm. Instead, we will create a number of simpler algorithms and then use these algorithms to describe an algorithm for multiplying two arbitrary integers.

Algorithm X.1: Multiplying a positive integer by $10^k$ for a non-negative integer $k$

Input: a non-negative integer $m$ and a power $k \ge 0$ of 10.
Output: a non-negative integer.

This is an easy algorithm to describe, and you have already determined such a description in your mind. However, we would like you to describe this algorithm in terms of the digits of the solution. Suppose that the positive integer $N$ has digits $N_0$, ..., $N_n$ where $N_\ell$ is the coefficient of $10^\ell$.

Algorithm X.2: Multiplying a positive integer by a single digit $n$

Input: a non-negative integer $m$ a single digit $d$.
Output: a non-negative integer.

Note that $9 \times 9 = 81$, so the largest carry this may result in is $8$, and $9 \times 9 + 8 = 89$, so the largest possible carry is still $8$. Using this,

Algorithm X.3(a): Multiplying two positive integers

Describe an algorithm for multiplying two positive integers; however, your algorithm should be focused on using Algorithms X.1 and X.2 and the algorithm for adding multiple integers.

Algorithm X.3: Multiplying two positive integers

In your description of Algorithm X.3(a), you may have disregarded the number of digits in each of the positive integers. Using your algorithm, is it easier to calculate $35 \times 509835098341534$ or $509835098341534 \times 35$. In the first case, there are likely adding fifteen positive integers, while in the second you are only adding two positive integers to get the final result. Which is more efficient?

Algorithm X.4: Multiplying two integers

Describe an algorithm for multiplying two integers, either of which may be positive or negative. Your algorithm may use $|N|$ to describe the absolute value of $N$.