Implement the long-hand multiplication algorithm for two n-bit unsigned numbers, with no recursion, no divide-and-conquer, etc. note: you need to multiply bitstrings not integers, return value of the program should be a bitstring. E.g., x = 11110000, y = 10111100, then if z = x y, your program should return z = 1011000001000000.

Now implement the divide-and-conquer recursive methods, using arity (branching factor) of 3 (ref. textbook, pg. 47, Fig 2.1). dont assume the number of bits is always even. You will need to take care of this carefully in implementing the algorithm outlined in the book.

implement the na ve divide&conquer recursive method without the Gaussian trick. the arity of your recursion tree will be 4. can use the same program written for the previous problem, instead of 3, there will be 4 multiplications. verify that the running time is the same as the na ve algorithm O(n2).

IN C++ PROGRAMMING PLEASE

Figure 2.1 A divide-and-conquer algorithm for integer multiplicati 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=multyy(xL+xR,yL+yR) return P12n+(P3P1P2)2n/2+P2