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.

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.