Question

Assume that you multiply the two two-digit numbers 36 and 52 using the method that does only three atomic multiplies. Show that steps of the algorithm on this example.

Answer 1

We can use Karatsuba algorithm to achieve the required goal as follows:

let the two numbers be X = 36 and Y = 52,

let X = X0X1 and Y = Y0Y1 ( for given example)

so, X0 = 3, X1 = 6 and Y0 = 5, Y1 = 2

Now, product of two numbers be:-

X * Y = X0X1 * Y0Y1

= 100 ( X0*Y0) + 10 (X0 * Y1 + X1 * Y0) + X1 * Y1

36 * 52 = 100 ( 3 * 5) + 10 (3 * 2 + 6 * 5) + (6 * 2)

= 1500 + 360 + 12

= 1872

by doing this we only need 3 atomic multiplications to multiply two 2-digit numbers.