Question

Develop a recursive algorithm that multiply two integer numbers x and y, where x is an m-bit number and y is an n-bit number (10 points), and analyze the time complexity of this algorithm (10 points).

Answer 1

let and

we can write x and y as:

assuming botm m and n are power of 2.

now their product is

where x_l,y_l, x_ry_l, x_ly_r, x_ry_r are multiplication of m/2 and n/2 digit numbers.

So we have reduced the bigger problem into 4 smaller subproblems of same type

The algo is:

Multiply (x,y,m,n)

xl=left half of x

xr= right half of x

yl=left half of y

yr=right half of y

return Multiply(xl,yl,m/2,n/2)+2^m/2Multiply(xr,yl,m/2,n/2)+2^n/2Multiply(xl,yr,m/2,n/2)+2^(m+n)/2Multiply(xr,yr,m//2,n/2)

Note. multiplying a binary number by 2^k is equivalent of shifting the number right to k positions. so multiplying a binary number by 2^k takes constan time:

with this the recurrence is given by

T(m,n)=4T(m/2,n/2)+O(n+m) (4 subproblems of size m/2 and n/2 taking linear time to multiply bt 2^k)

which is O(nm)