Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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