3
$\begingroup$

In Sipser's Introduction to Theory of Computation, he asks us to show that the language $MULT=\{(a,b,c):ab=c\}$ with $a,b,c\in\mathbb{Z}^+$ can be decided in log space.

I originally started out with a variant of the grade school long division algorithm: take the first few bits of $c$ and divide it by $a$ via repeated subtraction, and verify that you get the first digit of $b$. Wipe the slate clean and continue with the second, third,... digit.

If $a$ has $\log |c|$ digits I think this will run in log space, but there is no guarantee of that that I can see. (I may be confusing myself here, but I think this would require $\log a = \log\log c$, or $a=\log c$, which can fail if e.g. $a=b=\sqrt{c}$.)

Any hints?

1 Answers 1

5

Why not use grade-school long multiplication instead? You can compute any digit of a 1-by-$|b|$ digit multiplication in logarithmic space, and then you can also sum the $|a|$ staggered multiples of $b$ in logarithmic space. The only mildly non-trivial part of the latter is seeing that you can represent the sum of each column, plus the carry from the previous column, in $O(\log |a|)$ space.