Exercise (Karatsuba) In the lecture you have seen Karatsuba's algorithm to multiply two n-digit numbers in time O(nlog2(3))=O(n1.59). In this exercise, we improve the algorithm to time O(nlog3(5))=O(n1.47). a. Design an algorithm which, given an n-digit even number A, computes A/2. Your algorithm should run in time O(n). b. Prove that we can compute the product of two n-digit numbers by computing three squares of n-digit numbers. In particular, given an algorithm to compute the square A2 of a given n-digit number A in time T(n), show how to multiply two n-digit numbers in time O(T(n)). Hint: What is (a+b)2a2b2 ? c. Prove a variant of Karatsuba's algorithm which computes the square of a given n-digit number A by recursively computing three squares of (2n+1)-digit numbers. Prove that the running time of this algorithm is O(nlog2(3))=O(n1.59). d. Now adapt the algorithm to recursively compute six squares of (3n+1)-digit numbers. Prove that the running time of this algorithm is O(nlog3(6))=O(n1.64). e. Further adapt the algorithm to recursively only compute five squares of (3n+1)-digit numbers. Prove that the running time of this algorithm is O(nlog3(5))=O(n1.47). Hint: What is (a+b+c)2+(ab+c)2 and what is (a+b+c)2(ab+c)2