naive algorithm
multiply two $n -bit$ numbers, $x$ and $y$ that are in base $b$
Divide each number into two halves. let's say high bits $h$ and low bits $l$
$x = x_{h} *(b)^{n/2} + x_{l}$
$y = y_{h} *(b)^{n/2} + y_{l}$
$x*y = ( x_{h} *(b)^{n/2} + x_{l} ) * ( y_{h} *(b)^{n/2} + y_{l})$
$x*y = x_{h} *(b)^{n/2} * y_{h} *(b)^{n/2} + x_{l}*y_{h} *(b)^{n/2} + x_{h} *(b)^{n/2}*y_{l} + x_{l}*y_{l} $
$x*y = x_{h} * y_{h} *b^n + (x_{l}*y_{h} + x_{h} *y_{l} )*(b)^{n/2} + x_{l}*y_{l} $
$example: 1234_{10} * 8765_{10}$
$x = x_{h} *(b)^{n/2} + x_{l}$
$= 12*10^2 + 34$
$y = y_{h} *(b)^{n/2} + y_{l}$
$= 87*10^2 + 65$
$x*y = 12 * 87 *10^4 + (34*87 + 12 *65 )*(10)^{2} + 34*65 $
$= 1,08,16,010$
$T(n) = 4T(n/2) + O(n)$ which gives $O(n^2)$
Karatsuba Algorithm
To multiply two $n-bit$ numbers, $x$, and $y$, the Karatsuba algorithm performs three multiplications and a few additions, and shifts on smaller numbers that are roughly half the size of the original $x$ and $y$.
$a = x_{h}*y_{h}$
$d = x_{l}*y_{l}$
$e = (x_{h} + x_{l}) * ( y_{h} + y_{l} ) - a - d$
$x*y = a*r^n + e*r^{n/2} + d$
$example: 12_{10} * 43_{10}$
$x_{h} = 1 , x_{l} = 2 , y_{h} = 4 , y_{l} = 3$
$a = x_{h}*y_{h} = 1*4 = 4$
$d = x_{l}*y_{l} = 2*3 = 6$
$e = (x_{h} + x_{l}) * ( y_{h} + y_{l} ) - a - d = (1 + 2)*(4+3) - 4 - 6$ = 3*7 - 4 - 6 = 21 - 4 - 6 = 11$
$x*y = a*r^n + e*r^{n/2} + d = 4*10^2 + 11*10 + 6 = 400 + 110 + 6 = 516$
$T(n)=3T(n/2)+O(n)$
$T(n) =O(n^{log 3}) = O(n^{1.584…})$
https://ide.geeksforgeeks.org/at5ELrflt6
