Multiplication:

We implement standard polynomial multiplication here which is of oreder n² where n is the maximum degree of the two polynomials being multiplied. Later, we will do this using the Fast Fourier Transform and reduce it to an order nlog(n) method.

    // ************************************ //
    // Overloaded Operator *                //
    // ************************************ //
FLOAT_POLY FLOAT_POLY::operator*(const FLOAT_POLY& P)
{
  //cout << "entering overloaded * for P+Q" << endl;
  FLOAT_POLY* PRODUCT;
  PRODUCT = new FLOAT_POLY();
  if(head==NULL && P.head==NULL){
    //both this and the incoming polynomial are degenerate
    //cout << "Both this and incoming polynomial are degenerate" << endl;
    return(*PRODUCT);
    }
  if(head!=NULL && P.head==NULL){
    //we multiply nothing, so return NULL
    return(*PRODUCT);
    }
  if(head==NULL && P.head!=NULL){
    //*this is NULL, so return NULL
    return(*PRODUCT);
    }
  if(head!=NULL && P.head!=NULL){
    //both *this and P are non NULL
    //
    // *this          = \sum_{i=0}^n a_i x^{p_i}
    // P              = \sum_{j=0}^m a_j x^{q_j}
    // new polynomial = \sum_{k=0}^K c_k x^{r_k}
    //     where c_k = \sum_{j=0}^n a_i b_j such that i+j = p_i + q_j
    //
    //cout << "Both polys are non null so we start the mulitplication" << endl;
    FLOAT_POLY_CELL* current = P.head;
    FLOAT_POLY_CELL* temp = head;
    while(temp!=NULL){  
      while(current!=NULL){
        PRODUCT->insert_nosort(current->element*temp->element,
                               current->power + temp->power);
        current = current->next;
        }
      current = P.head;
      temp = temp->next;
      }
    PRODUCT->mergesort();
    return(*PRODUCT);
    }
}

    // ************************************ //
    // Overloaded Operator *=               //
    // ************************************ //
FLOAT_POLY& FLOAT_POLY::operator*=(const FLOAT_POLY& P)
{
  FLOAT_POLY* PRODUCT;
  PRODUCT = new FLOAT_POLY();
  if(head==NULL && P.head==NULL){
    //both this and the incoming polynomial are degenerate
    return(*this);
    }
  else if(head!=NULL && P.head==NULL){
    //we multiply nothing, so return NULL
    return(*this);
    }
  else if(head==NULL && P.head!=NULL){
    //*this is NULL, so return NULL
    return(*this);
    }
  else{
    //both *this and P are non NULL
    //
    // *this          = \sum_{i=0}^n a_i x^{p_i}
    // P              = \sum_{j=0}^m a_j x^{q_j}
    // new polynomial = \sum_{k=0}^K c_k x^{r_k}
    //     where c_k = \sum_{j=0}^n a_i b_j such that i+j = p_i + q_j
    //
    FLOAT_POLY_CELL* current = P.head;
    FLOAT_POLY_CELL* temp = head;
    while(temp!=NULL){  
      while(current!=NULL){
        PRODUCT->insert_nosort(current->element*temp->element,
                               current->power + temp->power);
        current = current->next;
        }
      current = P.head;
      temp = temp->next;
      }
    PRODUCT->mergesort();
    *this = *PRODUCT;
    return(*this);
    }
}