Question 3: In class, we have seen a fast algorithm that computes the product of two large integers. You may think that squaring an integer is easier than multiplying two integers. After all, for squaring, you get one input integer x, and have to multiply it by itself, whereas for multiplication, you have to compute the product of two input integers x and y. In this question, you will show that this is not the case: The time complexity of multiplication is the same (except for constant factors) as that of squaring. 1. You are given an algorithm A that takes as input an integer x > 1, written in binary, and returns the integer x2. We denote the running time (i.e., the number of bit operations) of algorithm A by S(n), where n is the number of bits in the binary representation of x. 2. You learned in elementary school that, given two integers 2 2 1 and y > 1, both written in binary and both having n bits, their sum x +y and difference 2 y can be computed in O(n) time. 3. Given an integer x > 2, written in binary, and given an integer k > 1, such that r is a multiple of 2%, we can compute x/26 in 0(k) time, by just removing the rightmost k bits from the binary representation of x. Describe (in plain English or pseudocode), an algorithm B that takes as input two n-bit integers x and y, and returns the product xy. Your algorithm B must use algorithm A as a subroutine, as well as the results in 2. and 3. above, and its running time must be (S(n + 1)). It is easy to come up with an algorithm B that calls A three times. You will get more marks if your algorithm B calls A only twice. Hint: (x + y)2