CS 325
Homework # 5
Polynomial Multiplication
In this homework, you will contrast different methods of multiplying two polynomials with
n coefficients where n = 2k
.
1. Write a program that uses the classical iterative method for multiplying two polynomials.
2. Write a program that uses the divide and conquer algorithm (which reduces the problem
to three half–size multiplications) for multiplying polynomials.
3. Write a program that uses the Fast Fourier Transform technique for multiplying polynomials.
4. Compute to Θ order the run–times for the these methods. (You can cite the book or
notes for this). Which one do you expect to be the fastest for large degree polynomials?
5. Choose several pairs of polynomials, P and Q, for various reasonable values of n (polynomial degree = 2k − 1) and compute the products P Q of the polynomials using your
programs. Show that your programs all give the same results, or explain why your
programs give differing results.
6. Plot the running times of your programs as a function of the number of coefficients.
(Pick a reasonable plotting format to help display the differences between the methods.)
7. Which program runs faster for a small number of coefficients? Use your runtime plots
to predict when the other programs might become faster (i.e. the crossover points).
