In class we discussed Karatsuba's divide-and-conquer algorithm for integer multiplication, which multiplies n-bit numbers by recursively multiplying n bit numbers. We take two numbers X and Y and split them each into their most significant half and least significant half: X = 2^n/2A + B and Y = 2^n/2C + D. Now, we can write the product

XY =(2^n - 2^n/2)AC+2^n/2(A+B)(C+D)+(1-2^n/2)BD.

Using this relation, write pseudocode for a recursive function Karatsuba(X,Y,n) to multiply two n-bit numbers X and Y . You may assume that you have access to a routine shift(U,m) that will shift the number U by m bits to the left (you may use negative values of m to shift to the right) as well as access to routines add(U,V) and subtract(U,V) that respectively compute U + V and U - V and run in linear time. You can assume that the usual -, /, +, and * operators can be used on small numbers (like n) as well as on X and Y for your base-cases when n <=4.

If you like, you can assume you have a split(X,A,B) operator that splits X into its left and right halves A and B, but see if you can implement this using the shift operator.