# Assignment 03 Solution

\$35.00 \$29.05

Category:

## Description

This problem is meant to show the effect of using an asymptotically

fast algorithm on the running time required by a program.

The basic problem is simple polynomial multiplication. Given two polynomials

P(x) = p_0 + p_1x + p_2x^2 + …. + p_{n-1}x^{n-1} and

Q(x) = q_0 + q_1x + q_2x^2 + …. + q_{n-1}x^{n-1}

with n terms each, we want to compute the product P(x)Q(x). The obvious method

takes O(n^2) time, which will be inefficient. While there are O(nlogn) time

algorithms known, they use complex numbers and are approximate.

A simple method that is asymptotically faster, is to use recursion.

Write P(x) = P_0(x) + x^{n/2}P_1(x) and Q(x) = Q_0(x) + x^{n/2}Q_1(x)

where P_0, P_1, Q_0, Q_1 are polynomials with n/2 terms.

The product can then be written as

P_0(x)Q_0(x) + x^{n/2}(P_0(x)Q_1(x) + P_1(x)Q_0(x)) + x^n(P_1(x)Q_1(x))

which can be rewritten as

P_0(x)Q_0(x) + x^{n/2}((P_0(x)+P_1(x))(Q_0(x)+Q_1(x))-P_0(x)Q_0(x)-P_1(x)Q_1(x)) + x^n(P_1(x)Q_1(x))

This reduces the problem to 3 multiplications of polynomials of size n/2, and

gives a running time O(n^{log_2 3}).

You have to implement this method, to compute the product. It can be assumed that

n is a power of two and will be 2^18 or 2^19.

You need to be careful with the implementation. When using recursion, you should use

as few local variables as possible, since these need to be stored every time a recursive

call is made. Also, passing large objects like vectors, even by reference, should be avoided.

It is sufficient to pass only a vector iterator.

Your function should look like:

multiply(P, Q, R, n)

where P, Q are vector iterators pointing to the first elements of the polynomials to be

multiplied, R is a vector iterator pointing to where the first coefficient of the product

is to be stored, and n is the number of terms. You can try by passing vectors or arrays

to compare the running times.

Although this algorithm is asymptotically faster, the constants are larger, so it makes

sense to use it only for large n. So in your implementation, instead of a base case of

n = 1, you can stop at a larger power of 2, and use the simple method when n is less than

or equal to that power. Experiment to find the optimal stopping size below which recursion

should not be used.

For polynomials of size 2^18, you program should take at most a few seconds.

You can assume the coefficients will be small so all will fit in an int, including

for the result. Note that correctness can be checked easily here for small polynomials,

the main requirement is the efficiency.

Input Format:

The first line of input specifies n the number of terms.

The next two lines contain n integers each, separated by a space, giving the coefficients

of the two polynomials starting from the degree 0 term. Assume each coefficient is

between -10 to +10.

Output

Output the coefficients of the result in a single line, separated by a space, starting with

the degree 0 term.

NOTE: Since the input/output is large, you will need to set the following flags to

speed up I/O.

ios_base::sync_with_stdio(false);

cin.tie(0);

cout.tie(0);

Also, when compiling, you will need to use the optimization option to speed

up your program. This can be done as

g++ -O2 *.cpp

2 indicates the optimization level, going beyond that may not help.

To measure the time required, you can use the time command.

time ./a.out < in > out

For more accurate measurement, you can use the <chrono> library, which is available

starting from C++11. Search on the net to find out how.