2
$\begingroup$

Given three numbers $m$, $n$ and $p$ in interleaved binary encoding1, it's obviously possible to check in $O(1)$ space whether $m+n=p$. It's less obvious2 that it isn't possible to check in $O(1)$ space whether $m\cdot n=p$. I wonder whether one can prove that it isn't possible to check in $O(\log N)$ space3 whether $m\cdot n=p$. On the other hand, are there any known non-trivial upper bounds on the space complexity of this problem, like $O(N/\log N)$?

The problem described above is a simplified version of the "Multiplication decision problem: Is the $k$th bit of the product of $m$ and $n$ a one?" Since this problem is more "powerful" (and also better known), I wonder whether one can show that this problem can't be decided in $O((\log N)^2)$ space.


1. The interleaved binary encoding starts with the lowest significant bit, and allows "leading" zeros for the most significant bits.

2. The proof idea I have in mind would use such an algorithm as building block for a decision procedure of Robinson arithmetic. I call this less obvious, because the fact that Robinson arithmetic is undecidable may be well known, but still remains non-trivial.

3. Here $N$ is the length of the input $m$, $n$ and $p$ in binary encoding.

$\endgroup$
  • $\begingroup$ A clarification: what is the model of computation? I think that even deciding $m+n=p$ with a Turing machine that has a read-only input tape and a single read/write work tape, is not possible in $O(1)$ space (unless the numbers are given in an interleaved format). Usually the space complexity is measured counting the number of distinct cells used in the work tape (and ignoring the cells of the read-only input tape). $\endgroup$ – Vor Oct 27 '13 at 13:57
  • $\begingroup$ @Vor Very good question/clarification. This question occurred to me while reading "Diskrete algebraische Methoden: Arithmetik, Kryptographie, Automaten und Gruppen" by Volker Diekert, Manfred Kufleitner and Gerhard Rosenberger. I now see that they do use interleaved input, starting with the lowest significant bit, and allowing "leading" zeros for the most significant bits. I didn't even realize that this detail was important, before you mentioned it. $\endgroup$ – Thomas Klimpel Oct 27 '13 at 14:14
  • 2
    $\begingroup$ Ok, to prove that it is impossible to do it in $O(1)$ you can use the fact that the corresponding language is not regular (you can store the O(1) space using the states and the TM becomes a DFA). Three pointers + a carry counter are enough to decide the problem (see en.wikipedia.org/wiki/Multiplication_algorithm#Space_complexity), so unless I'm missing something it can be done in $O(\log N)$ space. $\endgroup$ – Vor Oct 27 '13 at 16:38
  • $\begingroup$ @Vor Cool. I don't think that you are missing something. But I have a question about your $O(1)$ proof. How do you show that the corresponding language is not regular, without reference to the fact that Robinson arithmetic is undecidable? (The proof I had in mind is essentially identical to your proof in that I also start by constructing a DFA for multiplication. Then I use this DFA as building block for a decision procedure of Robinson arithmetic, because I don't know a simpler way to prove that the corresponding language is not regular.) $\endgroup$ – Thomas Klimpel Oct 27 '13 at 17:25
  • $\begingroup$ This is only an idea: if you use the interleaved rapresentation then $L = \{ (m_1 n_1 p_1) (m_2 n_2 p_2)....(m_k n_k p_k) \mid m n = p\}$ ($m_i,n_i,p_i$ are the i-th bits of m, n, p). But if $L$ is regular, then it is also regular if intersected with the regular language $L' = (0 0 0)^+ (1 1 0) (0 0 0)^+ (0 0 1)$ (informally it restrict $L$ to deciding squares $n^2=p$) and you can apply the pumping lemma (for regular languages :-) to $L \cap L'$. $\endgroup$ – Vor Oct 27 '13 at 17:58
1
$\begingroup$

You can do it in $O(\lg N)$ space, if you're willing to accept a randomized algorithm with an exponentially small probability of error. In practice, this algorithm is practical and every bit as good as a deterministic algorithm with no possibility of error.

The idea is to choose a random $\ell$-bit prime $\alpha$, reduce $m,n,p$ modulo $\alpha$, and then check whether the congruence $m\times n \equiv p \pmod{\alpha}$ holds modulo $\alpha$. This test can be done with $O(\ell)$ bits of space (about $3\ell$ bits). Moreover, it suffices to take $\ell = O(\lg N)$. In particular, if you want the probability of error to be at most $1/2^t$, it suffices to take $\ell=O(t + \lg N)$. The constants hidden by the big-O notation are small (something like 3 or so).

Now take $t=100$, and you get a practical algorithm. The probability of error is $1/2^{100}$, which is so small as to be negligible. It's more likely that you have a cosmic ray bit flip that causes your computation to give the wrong answer than that you get a wrong answer due to bad luck. (And cosmic ray bit flips affect deterministic algorithms, too, so the notion of an algorithm with zero error is not something that can be implemented in the real world; the best we can hope for is for the probability of error to be negligible.)


The analysis of this relies upon the prime number theorem. I don't have time to write out the full analysis right now, but the basic idea is that the algorithm gives the wrong answer only if $\alpha$ divides $mn-p$. Since $|mn-p|$ is (at most) $2N$ bits long, there can be at most $2N/\ell$ distinct $\ell$-bit prime divisors of $mn-p$. Also, by the Prime Number Theorem, there are about $2^{\ell}/\ell$ possible $\ell$-bit primes. Therefore, the probability that the randomly chosen $\alpha$ happens to divide $mn-p$ is at most $(2N)/2^{\ell}$. Now solve for $\ell$, and you get the result I claimed above.

Importantly, the probability of error is taken only over the internal coin flips of the algorithm, not over the possible values of $m,n,p$. In other words, even if an adversary chooses the values of $m,n,p$, the probability of error will still be at most $1/2^t$.

$\endgroup$
  • $\begingroup$ I just wonder whether you noticed that @Vor already gave a perfect answer to the question in a comment. I also wonder why we should choose a $l$-bit prime $\alpha$ at random, when we could just check with every $l$-bit prime instead, without increasing the space bound. I will think about your answer a bit, to better understand it and see whether the described method can be derandomized easily. $\endgroup$ – Thomas Klimpel Oct 27 '13 at 20:10
  • $\begingroup$ @ThomasKlimpel, oops, I missed Vor's comment! That's a great answer, better than mine. As far as why check with just a single prime: I assumed (perhaps mistakenly) we care about both time complexity and space complexity. $\endgroup$ – D.W. Oct 27 '13 at 23:55
  • $\begingroup$ @ThomasKlimpel, it turns out that checking every $\ell$-bit prime doesn't help. You need $\ell \ge \lg N$ in any case to deal with a worst-case value of $mn-p$ that's carefully constructed to be a product of distinct $\ell$-bit primes. For example, if $\ell=O(1)$, then you can choose $m,n,p$ so that $mn-p$ is a product of all $\ell$-bit primes and so that $0<m,n,p\le 2^N$. Such an erroneous $m,n,p$ will have zero probability of being detected. $\endgroup$ – D.W. Oct 28 '13 at 6:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.