A) (55 points) Implement the divide-and-conquer recursive method. You should not assume the number of bits is always even. You will need to take care of this carefully in implementing the algorithm

Language- Java

function multiply (x,y) Input: Positive integers x and y, in binary Output: Their product n=max( size of x, size of y) if n=1: return xy xL,xR= leftmost n/2, rightmost n/2 bits of x yL,yR= leftmost n/2, rightmost n/2 bits of y P1=multiply(xL,yL) P2=multiply(xR,yR) P3=multiply(xL+xR,yL+yR) return P12n+(P3P1P2)2n/2+P2