README.md

Polynomial Multiplication

• Given two polynomials, present an algorithm to multiplicate them. Since input is n+1 coefficients of each polynomial of n degree, as well as output is 2n + 1 coefficients from resulted polynomial.

• Develop a solution using:

  • trivial multiplication
  • divide and conquer
  • Fast Fourier Transform

• Input:

        n
        i0 i1 ... in
        j0 j2 ... jn

• Output:

        Trivial
        result

        Divide-n-Conquer
        result

        Fast Fourier Transform
        result

• Solution

Running

• Compiling:

    $ make

• Running an instance:

    ./polymul "path_instance"

• Example: running an instance "input_simple1.dat":

    ./polymul instances/input_simple1.dat

Back