Fast Polynomial Multiplication

#include <iostream>

using namespace std;


int m_count1 = 0;
int LEVEL = 0;



class term
{
public:
  int coefficient;
  int exponent;
  term *next;
  term(int,int,term * = 0);
};
term::term(int c,int e,term *n)
{
  coefficient = c;
  exponent = e;
  next = n;
}

class polynomial
{

public:
  term *head;
  void insertLast(int,int);
  polynomial(){head = 0;};
  polynomial(polynomial &);
  ~polynomial();
  void clear();
  bool insert(int,int);
  bool empty(){return head==0;};
  void print();
  int no_of_terms();
  polynomial operator+(polynomial);
  polynomial operator-(polynomial);
  polynomial operator*(polynomial);
  polynomial operator=(polynomial);


};

polynomial polynomial::operator=(polynomial s)
{

  clear();

  term* p= s.head;
  while(p != 0)
  {
    insertLast(p->coefficient,p->exponent);
    p = p->next;
  }
  return *this;
}



polynomial::~polynomial()
{
  term *p;
  while(head != 0)
  {
    p = head;
    head = head->next;
    delete p;
  }
}

void polynomial::clear()
{
  term *p;
  while(head != 0)
  {
    p = head;
    head = head->next;
    delete p;
  }
}


polynomial::polynomial(polynomial &s)
{
  head = 0;

  term* p= s.head;
  while(p != 0)
  {
    insertLast(p->coefficient,p->exponent);
    p = p->next;
  }
} 
void polynomial::insertLast(int c,int e)
{
  
  if(head == 0)
    head = new term(c,e,head);
  else
  {
    term* p = head;
    while(p->next != 0)
      p = p->next;
    p->next = new term(c,e);
  }
}


bool polynomial::insert(int c,int e)       // sorted insert
{
  if(head == 0)
  {
    head = new term(c,e,head);
    return true;
  }
  if(head->exponent>e)
  {
    head = new term(c,e,head);
    return true;
  }

  term *p = head;
  term *q = head;

  while(p != 0  && p->exponent != e)
  {
    q = p;
    p = p->next;
  }
  if(p != 0 )
  {
    p->coefficient += c;
    return true;
  }
  else
  {
  p = head->next;
  q = head;

  while(p != 0  && p->exponent < e)
  {
    q = p;
    p = p->next;
  }
  q->next = new term(c,e,p);
  return true;
  }
}


void polynomial::print()
{
  term *p = head;
  while(p != 0)
  {
    cout <<p->coefficient;
    if(p->exponent != 0)
      cout <<"X^" << p->exponent << " ";
    if(p->next != 0)
      if(p->next->coefficient >= 0)
      cout << "+";
    p = p->next;
  }
  cout << endl;
}




polynomial polynomial::operator +(polynomial l)
{
  term *p = head;
  term *q = l.head;
  polynomial l2;


  while(q != 0)
  {
    l2.insert(q->coefficient,q->exponent);
    q = q->next;
  }

  q = l2.head;


  while(p != 0)
  {
  
    l2.insert(p->coefficient,p->exponent);
    p = p->next;
  }

  return l2;
}


polynomial polynomial::operator -(polynomial l)
{

  term *p = head;
  term *q = l.head;
  polynomial l2;


  while(p != 0)
  {
  
    l2.insert(p->coefficient,p->exponent);
    p = p->next;
  }

  while(q != 0)
  {
    l2.insert(-(q->coefficient),q->exponent);
    q = q->next;
  }

  q = l2.head;



  return l2;

}

polynomial polynomial::operator *(polynomial l)   // human  way multiplication
{
  term *p = head;
  term *q = l.head;
  polynomial l2;
  while(p != 0)
  {
    while(q != 0)
    {
    l2.insert(p->coefficient*q->coefficient,p->exponent+q->exponent);
    q = q->next;
    }
    q = l.head;
    p = p->next;
  }
  return l2;
}


int polynomial::no_of_terms()
{
  int count = 0;

  term *p = head;

  while(p != 0)
  {
    p = p->next;
    count++;
  }

  return count;
}










polynomial poly_mul(polynomial p,polynomial q)
{
  LEVEL++;
  if((p.no_of_terms()==1) || (q.no_of_terms() == 1))  // human way will be O(n) so we will leave it
  {
    cout << endl << "INPUT OF LEVEL" << LEVEL << " :" << endl;
    cout << "p = ";
    p.print();
    cout << "q = ";
    q.print();
    polynomial d;
    d = p*q;
    m_count1 += (q.no_of_terms() * p.no_of_terms()); // to count the number multiplication (schoolbook)

    cout << endl << "OUTPUT (RESULT) OF LEVEL" << LEVEL << " :" << endl;
    d.print();
    LEVEL--;
    return d;
  }


  if(p.no_of_terms()==2 && q.no_of_terms()==2)
  {

    cout << endl << "INPUT OF LEVEL" << LEVEL << " :" << endl;
    cout << "p = ";
    p.print();
    cout << "q = ";
    q.print();

      term *p_ptr = p.head;
      term *q_ptr = q.head;

      int c1,c2,c3,e1,e2,e3;
      int sp12 = p_ptr->coefficient;
      int sq12 = q_ptr->coefficient;

      c1 = p_ptr->coefficient * q_ptr->coefficient;
      m_count1++;										// to count the number multiplication
      e1 = p_ptr->exponent + q_ptr->exponent;


      p_ptr = p_ptr->next;
      q_ptr = q_ptr->next;

      sp12 += p_ptr->coefficient;
      sq12 += q_ptr->coefficient;



      c3 = p_ptr->coefficient * q_ptr->coefficient;
      m_count1++;										// to count the number multiplication
      e3 = p_ptr->exponent + q_ptr->exponent;

      c2 = sp12 * sq12 - c1 - c3;
      m_count1++;										// to count the number multiplication
      e2 = (e1+e3)/2;								// to calculate the mid exponent

      polynomial z;
      z.insertLast(c1,e1);          // we can use (insert) function but we know the order
      z.insertLast(c2,e2);
      z.insertLast(c3,e3);


    cout << endl << "OUTPUT (RESULT) OF LEVEL" << LEVEL << " :" << endl;
    z.print();




      LEVEL--;
      return z;
  }



  if(p.no_of_terms() == q.no_of_terms())
   {
    cout << endl << "INPUT OF LEVEL" << LEVEL << " :" << endl;
    cout << "p = ";
    p.print();
    cout << "q = ";
    q.print();


     polynomial p1;
     polynomial p2;
     polynomial q1;
     polynomial q2;


     polynomial c_first;
     polynomial c_mid;
     polynomial c_last;

     polynomial c;





     term *p_ptr = p.head;
     term *q_ptr = q.head;


     int p_size = p.no_of_terms();
     int q_size = q.no_of_terms();
     int comm = 0;


     int i = 0;

     
     while(p_ptr != 0 && i < (p_size/2))
     {
       i++;
       p1.insert(p_ptr->coefficient,p_ptr->exponent);
       p_ptr = p_ptr->next;
     }

     if(p_ptr != 0)
      comm = p_ptr->exponent;         // take common from p2


     while(p_ptr != 0)
     {
       p2.insert(p_ptr->coefficient,p_ptr->exponent-comm);
       p_ptr = p_ptr->next;
     }


      i = 0;

     while(q_ptr != 0 && i < (q_size/2))
     {
       i++;
       q1.insert(q_ptr->coefficient,q_ptr->exponent);
       q_ptr = q_ptr->next;
     }
    
     
     
     if(q_ptr != 0)
      comm = q_ptr->exponent;       // take common from q2

     while(q_ptr != 0)
     {
       q2.insert(q_ptr->coefficient,q_ptr->exponent-comm);
       q_ptr = q_ptr->next;
     }



     c_first = poly_mul(p1,q1);

     c_last = poly_mul(p2,q2);



     polynomial sum_p12;
     polynomial sum_q12;

     sum_p12 = p1 + p2;
     sum_q12 = q1 + q2;



     c_mid = poly_mul(sum_p12,sum_q12);
     c_mid = c_mid - c_first;
     c_mid = c_mid - c_last;

///////// To know the correct power for mid terms and last terms ////////////////
     int l_e = 0;

     term *m = c_last.head;

     while(m != 0)
     {
       if( m->next == 0)
         l_e = m->exponent;
       m = m->next;
     }


     m = c_mid.head;

     while(m != 0)
     {
       m->exponent += (p_size + q_size - 2 - l_e)/2 ;

       m = m->next;
     }




     m = c_last.head;



     while(m != 0)
     {
       m->exponent += (p_size + q_size - 2 - l_e);

       m= m->next;
     }

////////////////////////////////////////////////////////////////

     c = c_first + c_mid + c_last;    // putting the parts together to get the result





    cout << endl << "OUTPUT (RESULT) OF LEVEL" << LEVEL << " :" << endl;
    c.print();


    LEVEL--;
     return c;
  }

  else
  {


    cout << endl << "INPUT OF LEVEL" << LEVEL << " :" << endl;
    cout << "p = ";
    p.print();
    cout << "q = ";
    q.print();



    polynomial big;
    polynomial small;
    if(p.no_of_terms() > q.no_of_terms())
    {
      big = p;
      small = q;
    }
    else
    {
      big = q;
      small = p;
    }

    int no_of_parts;

    ////////////// calculate number of parts ////////////////
    if(big.no_of_terms() % small.no_of_terms() == 0)
      no_of_parts = (big.no_of_terms()/small.no_of_terms());
    else
      no_of_parts = (big.no_of_terms()/small.no_of_terms())+1;

    /////////////////////////////////////////////////////////

    polynomial *parts = new polynomial[no_of_parts];
    polynomial c_part;
    polynomial c_ALL;

    int count = 0;
    int v=0;
    int comm_part;
    bool comm_done;

    term* big_ptr = big.head;
    term* part_ptr;

  ///// splitting /////////////////////////

    while(big_ptr != 0)
    {
      if(count == small.no_of_terms())
      {
        v++;
        count = 0;
      }
      parts[v].insert(big_ptr->coefficient,big_ptr->exponent);
      big_ptr = big_ptr->next;
      count++;
    }

  ////////////////////////////////////////





  ///// take common for part then multiply (small * part)
  ///// then return the common to c_part (result of part * small)
  ///// then every time we get c_part we add it to c_ALL to get the result

    for(v=0 ; v < no_of_parts ; v++)
    {
      comm_done = false;
      part_ptr = parts[v].head;
      while(part_ptr != 0)
      {
        if(!comm_done)
        {
          comm_part = part_ptr->exponent;
          comm_done = true;
        }
        part_ptr->exponent -= comm_part;
        part_ptr = part_ptr->next;
      }

      c_part = poly_mul(small,parts[v]);
      part_ptr = c_part.head;
      while(part_ptr != 0)
      {
        part_ptr->exponent += comm_part;
        part_ptr = part_ptr->next;
      }
      c_ALL = c_ALL + c_part;
    }


    cout << endl << "OUTPUT (RESULT) OF LEVEL" << LEVEL << " :" << endl;
    c_ALL.print();


    LEVEL--;
    return c_ALL;
    }
  }













int main()
{ 

  char wait;



  polynomial p;
  polynomial q;
  polynomial c;





  int k,m;
cout<<"please enter the degree of the first polynomial : ";
cin>>k;
for(int i=0;i<=k;i++)
{
  cout<<"please enter the coefficient of the term "<< i+1 <<" (for X^"<< i <<" ) : ";

  cin>>m;
  p.insert(m,i);
}
cout<<"please enter the degree of the second polynomial : ";
cin>>k;
for(int i=0;i<=k;i++)
{
  cout<<"please enter the coefficient of the term "<< i+1 <<" (for X^"<< i <<" ) : ";

  cin>>m;
  q.insert(m,i);
}



cout << endl << endl <<"---------------------------------------------------------------------"<<endl << endl;


  c = poly_mul(p,q);
  cout << endl << endl << endl;
  cout << " ###########" << endl;
  cout << " # Result: #" << endl;
  cout << " ###########" << endl << endl;

  cout << " ";
  c.print();

  cout << endl << " The Number Of Multiplication: " << m_count1;

  cout << endl << endl << endl << " ===============================" << endl << endl << endl;

  cout << " ######################" << endl;
  cout << " # Schoolbook Method: #" << endl;
  cout << " ######################" << endl << endl;

c = p*q;
cout << " ";
c.print();

cout << endl << " The Number Of Multiplication: " << (p.no_of_terms() * q.no_of_terms());


  

  cin >> wait;
  
  
  
  
  
  
  return 0;
}