30-1 Divide-and-conquer multiplication

a. Show how to multiply two linear polynomials \(ax + b\) and \(cx + d\) using only three multiplications. (\(\textit{Hint:}\) One of the multiplications is \((a + b) \cdot (c + d)\).)

b. Give two divide-and-conquer algorithms for multiplying two polynomials of degree-bound \(n\) in \(\Theta(n^{\lg 3})\) time. The first algorithm should divide the input polynomial coefficients into a high half and a low half, and the second algorithm should divide them according to whether their index is odd or even.

c. Show how to multiply two \(n\)-bit integers in \(O(n^{\lg 3})\) steps, where each step operates on at most a constant number of \(1\)-bit values.

(Omit!)

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用