retagged by
941 views

2 Answers

0 votes
0 votes

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

Related questions

1 votes
1 votes
1 answer
1
A_i_$_h asked Oct 10, 2017
1,042 views
Given 2 long integers having n digits , it is required to multiply them.Assuming the numbers are represented in an array of size n . The time complexity to multiply them ...
2 votes
2 votes
1 answer
2
0 votes
0 votes
1 answer
3
1 votes
1 votes
1 answer
4
VIKRAM KASANA asked Dec 21, 2017
639 views
please help me to understand