= Recall that in class we designed an algorithm that takes two n digit numbers x,...

 

Transcribed Image Text:

= Recall that in class we designed an algorithm that takes two n digit numbers x, y and returns their product ry, in base 10, in time O(n) where a log2 3. In this problem, we'll use a subroutine fastmultiply(x,y) that takes two n bit numbers and returns their product, in binary, in time O(n) with a = log2 3. We'll use fast binary multiplication to convert numbers from decimal to binary. As representation, we will represent decimal numbers as strings and binary numbers using bits as usual. Given this representation, you can index decimal numbers, but are unable to multiply two decimal numbers together, without first converting to binary. (a) We'll first design an algorithm to convert the decimal number 10" to binary. Assume that n is a power of 2. def pwr2bin(n): If n 1: return 1010 (decimal 10 in binary) Else: z=/* FILL ME IN */ Return fastmultiply(z,z). What is the appropriate value for z? What is the running time of the algorithm? = Recall that in class we designed an algorithm that takes two n digit numbers x, y and returns their product ry, in base 10, in time O(n) where a log2 3. In this problem, we'll use a subroutine fastmultiply(x,y) that takes two n bit numbers and returns their product, in binary, in time O(n) with a = log2 3. We'll use fast binary multiplication to convert numbers from decimal to binary. As representation, we will represent decimal numbers as strings and binary numbers using bits as usual. Given this representation, you can index decimal numbers, but are unable to multiply two decimal numbers together, without first converting to binary. (a) We'll first design an algorithm to convert the decimal number 10" to binary. Assume that n is a power of 2. def pwr2bin(n): If n 1: return 1010 (decimal 10 in binary) Else: z=/* FILL ME IN */ Return fastmultiply(z,z). What is the appropriate value for z? What is the running time of the algorithm?

Answer rating: 100% (QA)

To convert the decimal number 10n to binary using the provided algorithm we need to ... View the full answer