Overloading the * operator to multiply two polynomials

Question

Beginner at C++ here. I specifically need help trying to figure out what is wrong with my overloaded * operator which is supposed to multiply two polynomials of a class Poly I made. My other overloaded operators appear to work just fine. Here is the original question:

P(x) = 2x4 + 3x3 – 12x2 + x – 19 (4th order polynomial)
  or 
P(x) = 2x7 + 5x5 – 7x2 + x – 19 (7th order polynomial)

Where the coefficients for the first and second equations can be described by the following array of     integers

'Coeff1[  ] = {-19, 1, -12, 3, 2}'
'Coeff2[[ ] = {-19, 1, -7, 0, 0, 5, 0, 2}'

Design and code a polynomial class in C++ that has the following properties:

class Poly{
private:
int order;  //order of the polynomial
int *coeff; // pointer to array of coeff on the heap
        // size of coeff array predicated on (order + 1)
public:
Poly( );        //default constructor – order=0 & coeff[0] =1
Poly(int Order , int Default = 1) ;// creates  Nth order poly
                                                             // and inits all coeffs
Poly(int Order, int *Coeff);  //creates an Nth polynomial & inits 
 ~Poly( );      // destructor
   :::::::                     // copy constructor

//mutators  & accessors
void set( ){// Query user for coefficient values);
void set(int coeff[ ], int size);  // input coeffs via external coeff vector
int getOrder( )const;  // get order of polynomial
int * get( );         //returns pointer to coeff array

//overloaded operators
Poly operator+( const Poly &rhs);       // add two polynomials
Poly operator-( const Poly &rhs);       // subt two polynomials
Poly operator*( const int scale);       // scale a  polynomial
Poly operator*(const Poly &rhs);        // mult two polynomials
bool  operator==(const Poly &rhs);      // equality operator
const int & operator[ ](int I)const;       // return the Ith coefficient
int & operator[ ](int I);                   // return the Ith coefficient

int operator( )(int X);         // evaluate P(x) according 

Poly & operator=(const Poly & rhs);
friend ostream & operator<<(ostream & Out, const Poly &rhs);

//other member functions
};

Demonstrate the following operations for the following Polynomials:
P1(x) = 2x4 + 3x3 – 12x2 + x – 19 (4th order polynomial)
P2(x) = 2x7 + 7x5 – 6x2 + x – 19 (7th order polynomial)

//display the following results  for the polynomials defined above
o   P3 = P1 + P2;
o   P3 = P2 – P1;
o   P3 = P1*10;
o   P3 = 10*P1;
o   P3 = P1*P2;
o   bool flag  = (P1==P2);
o   P1[3] = P2[5];  // assign the 5th coefficient of P2 to 3rd coefficient of P1
o   int Z = P1(int  X = 5);   // evaluate  Polynomial for input X
 // suggest using Horner’s method


o   The displayed polynomial for P2 should be printed as follows
    2X^7 + 7X^5 – 6X^2 + 1X – 1

Heres my code so far:

#include <iostream>
#include <cmath>

using namespace std;

class Poly
{
private:
int order;
int *coeff;

public:
Poly();
Poly(int Order, int Default=1);
Poly(int Order, int *Coeff);
Poly(const Poly &copy);
~Poly();

void set();                             //ask the user for the coefficient values
void set(int *Coeff, int size);            //put the coefficient values in a external coeff vector
int getOrder() const;               //gets the order of the polynomial
int* get() const;                             //returns pointer to coeff array

Poly operator +(const Poly &rhs);
Poly operator -(const Poly &rhs);
Poly operator *(const int scale);
Poly operator *(const Poly &rhs);


bool operator ==(const Poly &rhs);
const int & operator [](int access) const;
int & operator [](int access);
int operator ()(int X);
Poly & operator =(const Poly &rhs);

friend ostream & operator <<(ostream &Out, const Poly &rhs);
};

 int main()  {

 int coeff1[] = {-19,1,-12,3,2};
 int coeff2[] = {-19,1,-7,0,0,5,0,2};

 Poly P1(4,coeff1);
 Poly P2(7, coeff2);
 Poly P3;

 cout << "P1: " << P1 << endl;
 cout << "P2: " << P2 << endl;

 P3 = P1 * P2;
 cout << "P1 * P2: " << P3 << endl;

 return 0;
}


Poly::Poly() : order(0)
{
coeff = new int[1];
coeff[0] = 1;

}

Poly::Poly(int Order, int Default) : order(Order)
{
coeff = new int[order+1];

for (int i = 0; i < order+1; i++){
    coeff[i] = Default;
}

}

Poly::Poly(int Order, int *Coeff) : order(Order), coeff(Coeff)
{

}

Poly::Poly(const Poly & copy)
{
order = copy.getOrder();
coeff = new int[order+1];

for (int i = 0; i < order+1; i++){
    coeff[i] = copy.get()[i];
}
}

Poly::~Poly()
{
//if(coeff){
//delete [] coeff;
//}
}

void Poly::set()
{
cout << "Enter your coefficients:\n";

for (int i = 0; i < order+1; i++){
    cin >> coeff[i];
}
}

void Poly::set(int *Coeff, int size)
{
delete [] coeff;
coeff = new int[size];
order = size;

for (int i = 0; i < order+1; i++){
    coeff[i] = Coeff[i];
}
} 

int Poly::getOrder() const
{
return order;
}

int* Poly::get() const
{
return coeff;
}

Poly Poly::operator +(const Poly &rhs)
{
int length = max(order+1, rhs.getOrder()+1);
int *answer = new int[length];

for (int i = 0; i < length + 1; i++){
    answer[i] = coeff[i] + rhs.get()[i];

}

if (order > rhs.getOrder()){
    for (int i = order+1 - rhs.getOrder()+1 ; i < order+1; i++){
        answer[i] = coeff[i];
    }
}

else if (order < rhs.getOrder()){
    for (int i = rhs.getOrder()+1 - order+1; i < rhs.getOrder()+1; i++){
        answer[i] = rhs.get()[i];
    }
}

return Poly(length-1, answer);
}

Poly Poly::operator -(const Poly &rhs)
{
int length = max(order+1, rhs.getOrder()+1);
int *answer = new int[length];

for (int i = 0; i < order+1 && i < rhs.getOrder() + 1; i++){
    answer[i] = coeff[i] - rhs.get()[i];
}

if (order > rhs.getOrder()){
    for (int i = order+1-rhs.getOrder()+1; i < order+1; i++){
        answer[i] = coeff[i];
    }
}

else if (order < rhs.getOrder()){
    for (int i = rhs.getOrder()+1 - order+1; i < rhs.getOrder()+1; i++){
        answer[i] = 0 - rhs.get()[i];
    }
}

return Poly(length-1, answer);
}

Poly Poly::operator *(const int scale)
{
int *answer = new int[order+1];

for (int i = 0; i < order+1; i++){
    answer[i] = coeff[i] * scale;
}

return Poly(order, answer);
}

Poly Poly::operator *(const Poly &rhs)
{    
int *shorter = NULL;
int *longer  = NULL;
int s = 0;
int l = 0;

if(order < rhs.getOrder()){
    shorter = coeff;
    s       = order;
    longer  = rhs.coeff;
    l       = rhs.order;
} else {
    shorter = rhs.coeff;
    s       = rhs.order;
    longer  = coeff;
    l       = order;
}

Poly sum = Poly(l, longer) * shorter[0];
int *prod;
int nl;
for (int i = 1; i <= s; i++){
    nl = l + i;

    prod = new int[nl + 1];

    for(int j = 0; j < i; j++){
        prod[j] = 0;
    }

    for(int k = 0; k <= l; k++){
        prod[k+i] = shorter[i] * longer[k];
    }

    sum = sum + Poly(nl, prod);
}

return sum; 
}

bool Poly::operator ==(const Poly &rhs)
{
bool result;

if (order == rhs.order){
    result = true;

    for(int i = 0; i<order+1; i++){
        if (coeff[i] != rhs.get()[i]){
            result = false;
        }
    }

}else result = false;

return result;
}

const int& Poly::operator[](int access) const
{
return coeff[order + 1 - access];
}

int& Poly::operator [](int access)
{
return coeff[order + 1 - access];
}

int Poly::operator ()(int x)
{
int total = 0;
for(int i = 0; i < order + 1; i++){
    total += coeff[i] * pow(x, i);
}
return total;

}

Poly &Poly::operator =(const Poly &rhs)
{
order = rhs.getOrder();
coeff = rhs.get();
return *this;

}

ostream& operator <<(ostream & Out, const Poly &rhs)
{
Out << rhs.get()[rhs.getOrder()] << "x^" << rhs.getOrder();      //first

for (int i = rhs.getOrder()-1; i > 0; i--){
    if (rhs.get()[i] < 0 || rhs.get()[i] > 1) {

    if(rhs.get()[i] > 0){
    Out << " + ";
    }

    Out  << rhs.get()[i] << "x^" << i << " ";

    }else if (rhs.get()[i] == 1){
        Out << "+ x ";
    }else if (rhs.get()[i] == 1){
        Out << "- x";
    }

}
if (rhs.get()[rhs.getOrder() - rhs.getOrder()] > 0) {
    Out << " + " << rhs.get()[rhs.getOrder() - rhs.getOrder()];      //last

}else Out << rhs.get()[rhs.getOrder() - rhs.getOrder()];      //last


Out << endl;

return Out;
}

`

Here is my current output. The answer I keep getting is half of the correct answer but I can't seem to get the first half.

P1: 2x^4 + 3x^3 -12x^2 + x -19

P2: 2x^7 + 5x^5 -7x^2 + x -19

P1 * P2: -114x^5 + 49x^4 -76x^3  + 362x^2 -38x^1  + 361

Any help is appreciated. Thank you

Answer 1

I think this:

sum = sum + Poly(length, prod);

should be

sum = sum + Poly(length + i - 1, prod);

Also, the loop on i should stop at the shortest coeff array length.

Here's a modified version of the function:

 Poly Poly::operator *(const Poly &rhs)
 {
   int *shorter = NULL;
   int *longer  = NULL;
   int s = 0;
   int l = 0;

   if(order < rhs.order){
     shorter = coeff;
     s       = order;
     longer  = rhs.coeff;
     l       = rhs.order;
   } else {
     shorter = rhs.coeff;
     s       = rhs.order;
     longer  = coeff;
     l       = order;
   }

   Poly sum = Poly(l, longer) * shorter[0];
   int *prod;
   int nl;
   for (int i = 1; i <= s; i++){
     nl = l + i;

     prod = new int[nl + 1];

     for(int j = 0; j < i; j++){
       prod[j] = 0;
     }

     for(int k = 0; k <= l; k++){
       prod[k+i] = shorter[i] * longer[k];
     }

     sum = sum + Poly(nl, prod);
   }

   return sum;
 }

Note how it is based on order values rather than coeff array lengths (contrarily to the fix I indicated at the top of this answer).

If it doesn't work for you, then you may have other bugs in the code you didn't provide, or your algorithms work with array lengths, so you might have to adjust either to get things working.

Finally, as it has been said in other answers, you should use the tools provided by the standard library instead of handling array allocation by hand.

Answer 2

Your code (for the polynomial multiplication) contains no comments and is rather opaque and hard to read/understand. So, I refuse to compile it (mentally) and can only guess, but it seems you don't know how multiplication of polynomials is defined, since your product polynomial is set to have order = min(order(A), order(B)) + 1, while correct is order(A)+order(B).

I suggest, you

1 make sure you understand polynomial multiplication before starting to code

2 write clear code with minimal instructions and useful comments (or better: useful variable names)

3 manage memory via the C++ standard library (using std::vector<>)

4 structure your code (write polynomial& polynomial::operator+=(polynomial const&) and then define the product as a standalone (can be a friend) via

polynomial operator*(polynomial const&a,polynomial const&b)
{
  auto c=a;
  c*=b;
  return std::move(c);
}

though you may want to improve on this particular design (avoiding the re-allocation the is necessary in the above code in the c*=b operation).

Answer 3

First, stop manually managing memory. Replace order and coeff with std::vector<int> values;. This bundles size() for order, and handles memory management for you.

If you don't know how to use std::vector yet, learn: it is far easier than learning how to write your own Poly class.

The next step in implementing Poly * Poly is to implement Poly& operator*=( Poly const& rhs );

The final step is friend Poly operator*( Poly lhs, Poly const& rhs ) { return std::move(lhs*=rhs); } There is little reason to use more than one line, and it can be inline.

That leaves operator*=.

The first step in implementing *= it so implement operator+(Poly const&, Poly const&), again via Poly& operator+=(Poly const&). As addition is easy, I will leave that to you.

The next step is scalar multiplication. Implement Poly& operator*=(int), and from it friend Poly operator*(Poly lhs, int x) { return std::move( lhs*=x ); } and friend Poly operator*(int x, Poly rhs) { return std::move( rhs*= x ); }. This is called 'scalar multiplication'.

Once we have those, *= becomes easy.

1. Store a copy of our initial value. (Poly init = std::move(*this);)

2. Create a return value (empty).

3. For each coefficient on the right hand side, do retval += coeff * init;

4. return *this = std::move(retval);

This is a sketch of the solution. To solve it really, you'll want to implement tests at each phase. Because I implemented *= in terms of other operations, testing each of those operations to make sure they work is key to having a debuggable *=. Then you test *=, then you test *, and then you are done.

If you are compiling in a compliant C++ compiler, a nice thing about using std::vector is that your default copy, move, assign and move-assign operations do the right thing, as does your default destructor. Seek to manage resources with specialized resource management classes, and follow The Rule of Zero, and you will have less pain.

Note that the above *= is not much easier to write than *, but in general *= is easier, so you should get into the habit anyhow.

Finally, note that this allocates more memory than is required, and is not optimal. It is, however, easy to get correct. After you have something like the above implemented, you can make it more optimal a number of ways. You can use karatsuba multiplication, you could use expression templates to avoid intermediate multiplication on the result += coeff * init; lines, you could reserve the right amount of space in result, or you could start playing with indexes manually.

The first step should be correctness, because if you have a correct algorithm you can at the very least use it to test your more optimal (trickier) algorithms.