# How to show MULT={a#b#c| a,b,c binary natural numbers and a ✕ b = c} is in Log Space?

Let MULT$=\{a\#b\#c| a,b,c \text{ binary natural numbers and } a\times b=c\}$

Prove that MULT $\in L$

How do I show that this language, MULT, is computable in Logarithmic space?

Let us assume a#b#c is on the input tape, we now need away of multiplying a with b and checking if the product is c, while using only $log(n)$ space while n is the length of the input.

• The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! – Raphael Feb 4 '18 at 22:21

In high-school multiplication, you multiply $a$ by $b$ by summing shifted copies of $b$, some of them zeroed out (according to $a$). You can implement this algorithm in logspace by calculating the result from LSB to MSB, keeping track of the carry. The crucial point is that the carry is only $O(\log n)$ bits long.