a. Show how to multiply two linear polynomials ax + b and cx + d using only

Question:

a. Show how to multiply two linear polynomials ax + b and cx + d using only three multiplications. One of the multiplications is (a + b) · (c + d).

b. Give two divide-and-conquer algorithms for multiplying two polynomials of degree-bound n in Θ(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.

Fantastic news! We've Found the answer you've been seeking!

Step by Step Answer:

Related Book For  book-img-for-question

Introduction to Algorithms

ISBN: 978-0262033848

3rd edition

Authors: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest

Question Posted: