6. The standard algorithm for multiplying two n-bit binary integers r and y costs (n). A...

   

Transcribed Image Text:

6. The standard algorithm for multiplying two n-bit binary integers r and y costs (n). A naive divide-and-conquer algorithm is to let z=: 2/2a +b and y = 2n/c+d, then ry = = (2/2a + b) (2/2c+d) 2" ac + 2/2 (ad + bc) + bd The complexity is T(n) = 4T() + (n) = (n). There is no improvement to the standard algorithm. (a) By observing that ad + bc = (a + b)(c+d) - (ac+bd). we can use only three multiplications. Describe this divide-and-conquer algorithm in a pseudocode. (b) What is the complexity of the algorithm. (e) Illustrate the algorithm for multiplying integersz = 10011011 and y = 10111010 (just show one level of the recursion). Please provide full answer. Thanks in advance! 6. The standard algorithm for multiplying two n-bit binary integers r and y costs (n). A naive divide-and-conquer algorithm is to let z=: 2/2a +b and y = 2n/c+d, then ry = = (2/2a + b) (2/2c+d) 2" ac + 2/2 (ad + bc) + bd The complexity is T(n) = 4T() + (n) = (n). There is no improvement to the standard algorithm. (a) By observing that ad + bc = (a + b)(c+d) - (ac+bd). we can use only three multiplications. Describe this divide-and-conquer algorithm in a pseudocode. (b) What is the complexity of the algorithm. (e) Illustrate the algorithm for multiplying integersz = 10011011 and y = 10111010 (just show one level of the recursion). Please provide full answer. Thanks in advance!

Answer rating: 100% (QA)

The image contains a text related to a divide and conquer algorithm for multiplying two nbit binary integers where n is even The text provides a naive ... View the full answer