Decimal to Binary. Recall that in class we designed an algorithm that takes two n digit numbers z, y and returns their product xy, in base 10, in time O(na) where a log23. 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(na) with a log23. 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? (b) The next procedure is supposed to convert a decimal integer r with n digits into binary. Assume that n is a power of 2 def dec2bin(x) If length(x) = 1: return binary(x) Else: Split r into L the leading n/2 digits and R, the trailing n/2 digits Return /* FILL ME IN* The subroutine binary(x) performs a lookup into a table containing the binary value of all decimal numbers 0,...,9. What are we supposed to return? What is the running time of this algorithm? Decimal to Binary. Recall that in class we designed an algorithm that takes two n digit numbers z, y and returns their product xy, in base 10, in time O(na) where a log23. 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(na) with a log23. 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? (b) The next procedure is supposed to convert a decimal integer r with n digits into binary. Assume that n is a power of 2 def dec2bin(x) If length(x) = 1: return binary(x) Else: Split r into L the leading n/2 digits and R, the trailing n/2 digits Return /* FILL ME IN* The subroutine binary(x) performs a lookup into a table containing the binary value of all decimal numbers 0,...,9. What are we supposed to return? What is the running time of this algorithm
