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$ in base $b$.
$h$ = high bits
$l$ = low bits
$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∗43$
$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^{log3})=O(n^{1.584…})$
https://ide.geeksforgeeks.org/at5ELrflt6