October 19, 2001

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: