In this homework, you will contrast di erent methods of multiplying two polynomials with
coe cients where n = 2k.
Write a program that uses the classical iterative method for multiplying two polyno-mials.
Write a program that uses the divide and conquer algorithm (which reduces the problem to three half{size multiplications) for multiplying polynomials.
Write a program that uses the Fast Fourier Transform technique for multiplying poly-nomials.
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?
Choose several pairs of polynomials, P and Q, for various reasonable values of n (poly-
nomial 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 di ering results.
Plot the running times of your programs as a function of the number of coe cients. (Pick a reasonable plotting format to help display the di erences between the methods.)
Which program runs faster for a small number of coe cients? Use your runtime plots to predict when the other programs might become faster (i.e. the crossover points).
