Suppose we have two integers, x and y, each with n digits. For simplicity, we'll work in decimal (base 10) and we represent x as a:b and y as c:d
Using standard multiplication, we get that:
x*y = a*c*10^n + (a*d + b*c)*10^(n/2) + b*d
However, Karatsuba noticed that:
x*y = a*c*10^n + (a*c + b*d + (a-b)*(d-c))*10^(n/2) + b*d
There are only three multiplications of size n/2 (a*c, b*d and (a-b)*(d-c))
No comments:
Post a Comment