# Multiplication using divide and conquer

Basic Approach to multiply 2 numbers say x , y $\left(binary\right)$ is $\Theta \left ( n^{2} \right )$ but if we apply Divide and conquer approach , we split it as-:

$x=x_{L}*2^{n/2}+x_{R}$

$y=y_{L}*2^{n/2}+y_{R}$

$x_{L}$ and $x_{R}$ contains leftmost and rightmost $n/2$ bits of $x$ respct. and same for $y_{L}$ and $y_{R}$

$x*y=2^{n}*x_{L}*y_{L}+2^{n/2}*\left (\left ( x_{L}*y_{R} \right )+ \left ( x_{R}*y_{L} \right )\right )+x_{R}*y{R}$

From the equation ,it is clear that we require 4 recursive calls to multiply 4 terms.

The recursive equation is given as-:

$f\left ( n \right )=4*f\left ( n/2 \right )+\Theta \left ( n \right )$

what is this $\Theta \left(n\right)$???? isn't it $\Theta \left(n^{2}\right)$ because it requires $\Theta \left(n^{2}\right)$ for simple multiplication..please help me out.!!

There are no simple multiplications in the RHS $2^{n}*x_{L}*y_{L}+2^{n/2}*\left (\left ( x_{L}*y_{R} \right )+ \left ( x_{R}*y_{L} \right )\right )+x_{R}*y_{R}$. As you've already noted there are four recursive multiplications: $x_{L}*y_{L}, x_{L}*y_{R}, x_{R}*y_{L}, x_{R}*y_{R}$. The only remaining multiplications are by powers of $2$, which just requires shifting an array of digits by a fixed offset: this only takes $\Theta(n)$ operations provided the array length is $\Theta(n)$ and the offset is $O(n)$. Besides multiplications, the only thing left are additions, which are again $\Theta(n)$.
Of course, solving this recurrence still gives $\Theta(n^2)$. The key to Karatsuba's algorithm for doing this more efficiently is a trick that lets you compute all four recursive multiplications using only three distinct multiplications.
• @sourav It's no different from multiplying a decimal number by $10000000$. These numbers are stored in binary — just think about it. – Erick Wong Nov 1 '16 at 7:41