# What is the fastest addition algorithm on a turing machine?

What's the asymptotic running time of the fastest algorithm for adding two $n$-digit decimal numbers on a Turing machine? To specify, the input is of the form $a_1+a_2$ where $a_1$ and $a_2$ are written out in the usual decimal expansion, and the output on the tape is just the result, $a_1+a_2$ (there is no need to keep the inputs). The best I can do so far is $O(n^2)$ time using this program I made: http://morphett.info/turing/turing.html?185f35a035e386d2a927c15b869b422a

The way this algorithm works is by finding the rightmost "non-added" digit of the number to the right of the addition sign (henceforth No. 2), marks this with an "o", and moving left until it finds a "non-added" digit of the number to the left of the addition sign (henceforth No. 1) and marking the result with a letter so that the machine will know how many decimal places to go to the left when adding next time. If there are any carries, these places are marked with numbers rather than letters because they haven't been 'reached' yet other than by the carry. The machine ends when all the digits on the right-hand number have been turned into "o"s and the machine encounters the plus sign instead of a number. Then, it cleans up all the "o"s and transforms all the letters into numbers and deletes any 0's at the beginning of the number.

I won't provide a rigorous proof, but this algorithm can be seen to be $O((n_2)^2)$ time complexity intuitively by the fact that for each digit in No. 2, the turing machine has to move about $n_2$ (which I use to denote the length of $a_2$) steps to the left, and since there are $n_2$ digits in No. 2, this algorithm takes about $n_2\times n_2=(n_2)^2$ steps. (Thus it runs in $O(n^2)$ time, assuming both numbers are of the same length, $n_1=n_2=n$). This improves on the naïve exponential time implementation of just subtracting one from No. 2 and adding one to No. 1 until No. 2 is exhausted, but is there any faster algorithm?

EDIT: Just to clarify I want the fastest algorithm for adding two decimal numbers of equal length, $n$. I use $n_1$ and $n_2$ as the lengths of $a_1$ and $a_2$ respectively only to emphasize that the algorithm is technically only quadratic in $n_2$, which is where it gets the $O(n^2)$ runtime from. I tried calculating the exact number of steps the algorithm takes, which is $n_1+2(n_2)^2+5n_2+max(n_1,n_2)+5+2c+d$, where c is the number of carries (bounded by $n_1$) and d is the number of digits in the result. Thus, a more precise runtime would be $O((n_2)^2+n_1)$, but left this out for conciseness and because in the end I only cared about the case $n_1=n_2=n$.

• I know that [task] takes O(n) time, so there should be a [Turing] machine program to [finish task] in O(n) time, right? No. Algorithm analysis using Big-O-notation is used implying a RAM machine, and while universal machines are equivalent in what they can do, that does not extend to resource usage. – greybeard May 7 '16 at 5:35
• Okay, I was suspecting it would be something like that, especially since checking if a number is odd or even takes constant time, yet it would take a turing machine O(n) time to read through the whole string and get to the end to decide. Do you know for sure whether adding can't be done on a turing machine in better than O(n^2) time? (Like, perhaps it can be done in O(nlogn) time or something like that?) – exfret May 7 '16 at 16:14
• Would the size of the tape alphabet matter? And even if it does, increasing the size of the tape alphabet should at some point stop reducing time complexity (or at least have some limit). – exfret May 7 '16 at 21:16
• (Regarding the question: How fast can you copy a number?) – greybeard May 8 '16 at 7:39
• @greybeard Thank you, I have modified my question accordingly so that there is no longer ambiguity in the meanings of $n$, $n_1$, and $n_2$. Also, when I said the naïve implementation was exponential, I meant in the length of the input string (in case that clears any confusion). This is because of the same reason unary addition is exponential: the number of steps taken is at least the number, $a_2$, which grows exponentially with its number of decimal digits, $n$. – exfret May 8 '16 at 14:22

## 1 Answer

(This should be a comment but I can't comment yet)

Just to clarify, when you have an integer $n$, it's represented on $\operatorname{size}(n)=\log_2 n$ bits.

So here, you are given $n_1$ and $n_2$ and you want to compute $n_1+n_2$. Let $f(n_1, n_2)$ be the number of steps needed to compute that. You seem to be claiming that $f(n_1, n_2)=O\left((n_2)^2\right)=O\left(\left(2^{\operatorname{size}(n_2)}\right)^2\right)$, which is obviously false. Now if you change it to $f(n_1, n_2)=O\left((\operatorname{size}(n_2))^2\right)=O\left((\log_2 n_2)^2\right)$, it becomes a little bit more plausible.

But that still can't be the complexity because if you have $n_1=2^{k}-1$ and $n_2=2^0$, your algorithm will at least read $n_1$, which takes $O\left(\operatorname{size}(n_1)\right)=O\left(\log_2 n_1\right)=O(k)$ while $O\left((\log_2 n_2)^2\right)=O(1)$ in these cases. The complexity should depend on the size of $n_1$ one way or another.

• Stricly speaking the algorithm is in $O\left( (2^{\text{size}(n_1+n_2)})^{2} \right)$, because Big-O notation is only an upper bound. The only complaints would be that there are better upper bounds and it's not what is intended. – Lieuwe Vinkhuijzen May 8 '16 at 9:50
• The correct parameter is the input size. You can add an $a$-bit number and a $b$-bit number in time $O((a+b)^2) = O(n^2)$, where $n = \Theta(a+b)$ is the input length. – Yuval Filmus May 8 '16 at 10:09
• @XavierM Okay, I realize I left a lot of ambiguity in the question. I was referring to $n_1$ and $n_2$ as both the numbers being added and the lengths of the numbers being added, which led to my inaccurate asymptotic runtime claims. As for the $n_1$ term in the runtime, I left that out because it was dominated by the $(n_2)^2$ term, and since I wanted $n_1=n_2=n$, the n_1 term didn't matter. However, I was unclear about this, as well, so I will fix this. – exfret May 8 '16 at 14:29