Ze-Yuan Hu's page

Polynomial Multiplication

I finally got time to continue working through MAW. The problem 3.7 relates to polynomial multiplication.

Problem

Write a function to multiply two polynomials, using a linked list implementation. You must make sure that the output polynomial is sorted by exponent and has at most one term of any power.

  1. Give an algorithm to solve this problem in \(O(M^2N^2)\) time.
  2. Write a program to perform the multiplication in \(O(M^2N)\) time, where \(M\) is the number of terms in the polynomiial of fewer terms.
  3. Write a program to perform the multiplication in \(O(MNlog(MN))\) time.
  4. Which time bound above is the best?

Solution

Question 1

The first question is quite straightforward. We keep the result in a linked list with exponent sorted in descending order. Each time a multiply is performed, we search through the result linkedlist for the term with the same exponent as ours. If so, we simply add coefficients together. If not, we add our product as a new term.

Polynomial
multiply1(Polynomial A, Polynomial B)
{
Polynomial R = malloc(sizeof(struct Node));
PtrToNode dummyRPrev = R;
PtrToNode dummyR = R;
PtrToNode dummyA = A->Next;
PtrToNode dummyB = B->Next;

int tmpExponent, tmpCoefficient;

while (dummyA != NULL)
{
    while (dummyB != NULL)
    {
      tmpExponent = dummyA->exponent + dummyB->exponent;
      tmpCoefficient = dummyA->coefficient * dummyB->coefficient;

      // we go through the output polynomial to see if there is
      // a term with the same exponent as our tmpExponent.
      while (dummyR != NULL)
      {
        if (dummyR->exponent == tmpExponent)
        {
          dummyR->coefficient = dummyR->coefficient + tmpCoefficient;
          break;
        }
        else
        {
          dummyRPrev = dummyR;
          dummyR = dummyR->Next;
        }
      }

      // We couldn't find the term with the same exponent, so we create
      // a new term in our output polynomial.
      if (dummyR == NULL)
      {
        insert(tmpCoefficient, tmpExponent, dummyRPrev);
      }

      dummyR = R;
      dummyB = dummyB->Next;
    }
    dummyB = B->Next;
    dummyA = dummyA->Next;
  }

  return R;
}

The total running time is \(O(M*N)\). We start from the inner most loop. We go through the result linkedList to search for the duplicate exponent term. The running time depends on the length of the linkedList. The result linkedList can have at most \(M*N\) terms. Then, for the middle loop, we iterate through \(N\) times and for the outer most loop, we iterate through \(M\) times. So, the total running time is \(O(M*N*MN) = O(M^2N^2)\).

Question 2

We can certainly do better than \(O(M^2N^2)\).

Polynomial
multiply2(Polynomial A, Polynomial B)
{
  int lenA = 0, lenB = 0;
  PtrToNode dummyA = A->Next;
  PtrToNode dummyB = B->Next;
  Polynomial R = malloc(sizeof(struct Node));
  PtrToNode dummyTmp, dummyShort, dummyLong, Long;
  Polynomial Tmp = malloc(sizeof(struct Node));

  while(dummyA != NULL)
  {
    lenA++;
    dummyA = dummyA->Next;
  }

  while(dummyB != NULL)
  {
    lenB++;
    dummyB = dummyB->Next;
  }

  if (lenA < lenB)
  {
    dummyShort = A->Next;
    dummyLong = B->Next;
    Long = B;
  }
  else
  {
    dummyShort = B->Next;
    dummyLong = A->Next;
    Long = A;
  }

  while(dummyShort != NULL)
  {
    dummyTmp = Tmp;
    while(dummyLong != NULL)
    {
      int coefficient = dummyShort->coefficient * dummyLong->coefficient;
      int exponent = dummyShort->exponent + dummyLong->exponent;
      insert(coefficient, exponent, dummyTmp);
      dummyTmp = dummyTmp->Next;
      dummyLong = dummyLong->Next;
    }
    R = add(R, Tmp);
    dummyLong = Long->Next;
    deletePolynomial(Tmp);
    dummyShort = dummyShort->Next;
  }

  return R;
}

Suppose polynomials \(A\) has \(M\) terms, and polynomials \(B\) has \(N\) terms. \(M < N\). Instead of updating the result after each multiply, we multiply one term from \(A\) (the polynomials with fewer terms) by all the terms from \(B\) (the polynomials with more terms). Then we add this with the output linkedList using Polynomial add(...) function I implemented (can be found under polynomial.c). The add function has a runtime \(O(max(M,N))\) and thus we can get our runtime for multiply2:

\begin{equation*} O(max(N,0)) + O(max(N,N)) + O(max(N,2N)) + ... + O(max(N, N(M-1))) = O(M^2N) \end{equation*}

Also, we calculate the length of \(A\) taking \(O(M)\); we calculate the length of \(B\) taking \(O(N)\); and we do deleteList during the while loop taking \(O(MN)\). So, the total runtime is:

\begin{equation*} O(M^2 N) + O(M) + O(N) + O(MN) = O(M^2 N) \end{equation*}

Note

For this implementation, I kind of using an interface within the function. The logic begins with while (dummyShort != NULL) are the same for both \(M<N\) and \(M>N\). So, there is potential to write the same logic twice for these two cases respectively. The solution I use is to provide an interface using dummyLong and dummyShort variables.

Please note we need to multiply one term from the polynomials with fewer terms by all the terms from the polynomial with more terms. If we do the other way around, the runtime will be \(O(MN^2)\).

Question 3 & 4

I haven't coded up for question 3 because I want to wait for finishing sorting chapter. However, I can see how we can get \(O(MNlog(MN))\). This solution is very similar to Question 1. We first multiply all terms out using \(O(MN)\). Then, we sort resulting \(MN\) terms by exponent. Then, we run through the linked list merging any summing any terms with the same exponent (which will be contiguous). The sort takes \(O(MNlog(MN))\) time. The multipies and the merging of duplicates can be performed in \(O(MN)\) time. So, we have:

\begin{equation*} O(MN) + O(MNlog(MN)) + O(MN) = O(MNlog(MN)) \end{equation*}

When we actually compare the runtime of three solutions, we can see 1st one is the worst among the three. However, for 2nd one and 3rd one, the comparison result depends on the size of \(M\) and \(N\). If \(M\) and \(N\) are close in size, then \(O(MNlog(MN))\approx O(MNlog(M^2))=O(MNlog(M))\), which is better than \(O(M^2N)\). However, if \(M\) is very small in comparison to \(N\), then \(M\) is less than \(log(MN)\) and in this case, 2nd one is better than 3rd one.

comments powered by Disqus