I need to have return types to be bitstring (which could be either a string or an array of 0s and 1s) Also n is assumed to be a power of 2. You can see that in the return statement, we have 2^(n/2) with no floor and ceiling. So I need to find a way to handle the case where n is not a power of 2.

PsuedoCode given:

I also have to include : To measure the time taken by each input

for each input n {

start_time_stamp = ...get current time stamp... ; // get start time

f(n); // run the function with only one input

end_time_stamp = ...get current time stamp... ; // get end time

time_elapsed = end_time_stamp - start_time_stamp;

}

My Current Code:

import java.math.BigInteger;

public class DivideAndConquer {

public static String multiply(String x, String y) {

int n = Math.max(x.length(), y.length());

if (n == 1) {

int xi = Integer.parseInt(x, 2);

int yi = Integer.parseInt(y, 2);

return Integer.toBinaryString(xi * yi);

}

// Split x and y into left and right halves

int k = (n + 1) / 2;

String xl = x.substring(0, n - k);

String xr = x.substring(n - k);

String yl = y.substring(0, n - k);

String yr = y.substring(n - k);

// Recursively compute the three partial products

String p1 = multiply(xl, yl);

String p2 = multiply(xr, yr);

String p3 = multiply(addBinary(xl, xr), addBinary(yl, yr));

// Combine the partial products to get the final result

String t1 = padRight(p1, 2 * k);

String t2 = padRight(subtractBinary(subtractBinary(p3, p1), p2), k);

return addBinary(addBinary(t1, t2), p2);

}

public static String addBinary(String a, String b) {

BigInteger ai = new BigInteger(a, 2);

BigInteger bi = new BigInteger(b, 2);

BigInteger sum = ai.add(bi);

return sum.toString(2);

}

public static String subtractBinary(String a, String b) {

BigInteger ai = new BigInteger(a, 2);

BigInteger bi = new BigInteger(b, 2);

BigInteger diff = ai.subtract(bi);

return diff.toString(2);

}

public static String padRight(String s, int n) {

return String.format("%1$-" + n + "s", s).replace(' ', '0');

}

public static void main(String[] args) {

String x = "101011";

String y = "1101";

String result = multiply(x, y);

System.out.println(x + " * " + y + " = " + result);

}

}

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=multply(xL+xR,yL+yR) return P12n+(P3P1P2)2n/2+P2