Since Counting and Permutations, I've been practising more C++. For example, last week (Lecture 6) we were given a task to add, subtract and multiply polynomials.
The main functionality that we are practising is overloading operators. Our solution is to be based on arrays, not lists or vectors etc so that does restrict possible implementation options.
Working with polynomials turned out to be quite complicated. A polynomial is a series of terms, so I decided to create a Term class. The idea here is to encapsulate the coefficient and the exponent into a Term datatype:
class Term
{
public:
/// <summary>
/// Create a term
/// </summary>
Term(int coeff, int exp): exp(exp), coeff(coeff), isCancelled(false) {}
/// <summary>
/// Default constructor
/// </summary>
Term(): coeff(0), exp(0), isCancelled(false) {}
/// <summary>
/// Copy another Term
/// </summary>
Term operator+(Term& other) // not actually using this
{
assert(exp == other.GetExponent());
return Term(coeff + other.GetCoeff(), exp);
}
/// <summary>
/// Get Coefficient in term
/// </summary>
int GetCoeff() const
{
return coeff;
}
/// <summary>
/// Set Coefficient
/// </summary>
void SetCoeff(int inCoeff)
{
coeff = inCoeff;
}
/// <summary>
/// Get term exponent
/// </summary>
int GetExponent() const
{
return exp;
}
/// <summary>
/// Set Exponent
/// </summary>
void SetExponent(int inExp)
{
exp = inExp;
}
/// <summary>
/// Get if term is cancelled
/// </summary>
bool IsCancelled() const
{
return isCancelled;
}
/// <summary>
/// Sets if the term is cancelled
/// </summary>
void SetIsCancelled(bool yesno)
{
isCancelled = yesno;
}
private:
int coeff;
int exp;
bool isCancelled;
};
We were encouraged to define getters an setters which, in my opinion just make the code look messy. Anyway, each term can optionally be cancelled. I incorporated this when I decided to implement a Simplify() function on the polynomial class. Speaking of the Polynomial class, I'll drop it in here and then try to discuss the various parts in isolation.
class Polynomial
{
public:
/// <summary>
/// Construct a empty polynomial with space for inNumTerm polynomials (can't grow)
/// </summary>
/// <param name="inNumTerms">Number of terms this polynomil has</param>
Polynomial(int inNumTerms, bool useSequentialExponents = false) : numTerms(inNumTerms)
{
terms = new Term[inNumTerms];
if(useSequentialExponents)
{
for(auto t = 0; t < inNumTerms;t++)
{
terms[t].SetExponent(t);
}
}
}
/// <summary>
/// Construct a polynomial as a series of input terms (copied)
/// </summary>
Polynomial(Term inTerms[], int inNumTerms)
{
terms = CopyTerms(inNumTerms, inTerms);
numTerms = inNumTerms;
}
/// <summary>
/// Construct a Polynomial by copying another
/// </summary>
/// <param name="other"></param>
Polynomial(const Polynomial& other)
{
terms = CopyTerms(other.GetNumTerms(), other.terms);
numTerms = other.GetNumTerms();
}
~Polynomial()
{
delete [] terms;
}
/// <summary>
/// a) Add two polynomials
/// </summary>
Polynomial operator+(const Polynomial other)
{
auto maxNumTerms = GetLargestExponent(*this, other) + 1;
// Ensure the polynomial are in standard format i.e, acending powers of x
Polynomial meStd = ToStdFormat(*this, maxNumTerms);
Polynomial youStd = ToStdFormat(other, maxNumTerms);
// Create empty resulting polynomial in standard format, i.e acending powers of x
Polynomial resultPoly(maxNumTerms, true);
// Add like terms
for(auto t = 0; t < maxNumTerms;t++)
{
resultPoly.terms[t].SetCoeff(meStd.terms[t].GetCoeff() + youStd.terms[t].GetCoeff());
}
return resultPoly;
}
/// <summary>
/// b) Subtract two polynomials
/// </summary>
Polynomial operator-(const Polynomial other)
{
auto largestExponent = GetLargestExponent(*this, other);
auto maxNumTerms = largestExponent + 1;
Polynomial meStd = ToStdFormat(*this, maxNumTerms);
Polynomial youStd = ToStdFormat(other, maxNumTerms);
Polynomial result(maxNumTerms, true);
for(auto t = 0; t < maxNumTerms;t++)
{
result.terms[t].SetCoeff(meStd.terms[t].GetCoeff() - youStd.terms[t].GetCoeff());
}
return result.Simplify();
}
/// <summary>
/// c) Assign one polynomial to another
/// </summary>
Polynomial& operator=(Polynomial& other)
{
terms = other.GetTerms();
numTerms = other.GetNumTerms();
}
/// <summary>
/// d) Multiply two polynomials
/// </summary>
Polynomial operator*(const Polynomial other)
{
Polynomial theirPoly = other;
// Result will have a fixed number of terms, i.e poly1.GetNumTerms() x poly2.GetNumTerms()
auto resultNumTerms = numTerms * theirPoly.GetNumTerms();
// Create empty polynomial
Polynomial resultPoly(resultNumTerms);
int resultTermNum = 0;
// Distribute and multiply our terms over other's terms
for(auto numOurTerm = 0; numOurTerm < numTerms; numOurTerm++)
{
for(auto numTheirTerm = 0; numTheirTerm < theirPoly.GetNumTerms(); numTheirTerm++)
{
auto theirTerm = theirPoly.GetTerms()[numTheirTerm];
// Multiply the coefficient
auto coeffResult = terms[numOurTerm].GetCoeff() * theirTerm.GetCoeff();
// calculate the exponent
int expResult = terms[numOurTerm].GetExponent() + theirTerm.GetExponent();
// Store the result into the result term
auto* ptrResultTerm = &resultPoly.GetTerms()[resultTermNum];
// store
ptrResultTerm->SetCoeff(ptrResultTerm->GetCoeff() + coeffResult); // combine with existing term
ptrResultTerm->SetExponent(expResult);
resultTermNum++; // move onto the next term to calculate in the result polynomial
}
}
// Return result but simplify the polynomial first
return resultPoly.Simplify();
}
/// <summary>
/// e) Overload += compound assignment operator
/// </summary>
Polynomial& operator+=(const Polynomial& other)
{
// Copy result of addition of two polynomials (use overloaded + operator on Polynomial)
auto temp = *this + other;
// assign result into self
numTerms = temp.GetNumTerms();
terms = CopyTerms( numTerms, temp.GetTerms());
return *this;
}
/// <summary>
/// e) Overload -= compound assignment operator
/// </summary>
Polynomial& operator-=(const Polynomial& other)
{
// Copy result of subtraction of two polynomials (use overloaded - operator on Polynomial)
auto temp = *this - other;
// assign result into self
numTerms = temp.GetNumTerms();
terms = CopyTerms(numTerms, temp.GetTerms());
return *this;
}
/// <summary>
/// Get the largest exponent
/// </summary>
int GetLargestExponent(Polynomial p1, Polynomial p2)
{
auto largestExponent = p1.GetDegree();
if(largestExponent < p2.GetDegree())
{
largestExponent = p2.GetDegree();
}
return largestExponent;
}
/// <summary>
/// Get Number of terms
/// </summary>
int GetNumTerms() const
{
return numTerms;
}
/// <summary>
/// Get terms
/// </summary>
Term* GetTerms()
{
return terms;
}
/// <summary>
/// Set terms
/// </summary>
void SetTerms(Term* inTerms)
{
terms = inTerms;
}
/// <summary>
/// Get highest exponent
/// </summary>
int GetDegree() const
{
auto largestExponent = 0;
for(auto t = 0; t < numTerms;t++)
{
if( terms[t].GetExponent() > largestExponent)
{
largestExponent = terms[t].GetExponent();
}
}
return largestExponent;
}
/// <summary>
/// Check if polynomial has a specific term
/// </summary>
bool HasTerm(int coeff, int exp)
{
for(auto t = 0; t < numTerms; t++)
{
if(terms[t].GetCoeff() == coeff && terms[t].GetExponent() == exp)
{
return true;
}
}
return false;
}
/// <summary>
/// Create new polynomial in standard format i.e, nx0 nx1 nx2 nx3 ...
/// </summary>
Polynomial ToStdFormat(Polynomial poly, int degree)
{
Polynomial std = Polynomial(degree, true);
for(auto t = 0; t < poly.numTerms;t++)
{
auto exp = poly.terms[t].GetExponent();
std.terms[exp].SetCoeff(poly.terms[t].GetCoeff());
}
return std;
}
private:
int numTerms;
Term* terms;
/// <summary>
/// Simplify/aggregate like terms in the polynomial
/// </summary>
Polynomial Simplify()
{
Polynomial result(numTerms);
for(auto t = 0; t < numTerms; t++)
{
// Add this term to the result and we'll add to it if we find like terms:
result.terms[t] = terms[t];
// Look for like terms in the other terms
for(auto t2 = 0; t2 < numTerms; t2++)
{
// Dont consider myself or other terms that are empty/cancelled as candiates to use for simplification
if(t == t2 || (terms[t2].IsCancelled() || terms[t].IsCancelled()))
{
continue;
}
// if exponents are the same, can simlify terms as like-terms:
if(terms[t].GetExponent() == terms[t2].GetExponent())
{
// Add like term to result term
auto* resultTerm = &result.GetTerms()[t];
resultTerm->SetCoeff(resultTerm->GetCoeff() + terms[t2].GetCoeff());
resultTerm->SetExponent(terms[t].GetExponent());
// cancel term
terms[t2].SetIsCancelled(true);
}
}
}
return result;
}
/// <summary>
/// Make a copy of inTerms and use that to replace our terms
/// </summary>
Term* CopyTerms(int inNumTerms, Term inTerms[])
{
auto newTerms = new Term[inNumTerms];
// Take a copy of all terms and use as our own
for (auto t = 0; t < inNumTerms; t++)
{
// copy term
newTerms[t] = inTerms[t];
}
return newTerms;
}
};
So let's start with one of the constructors. This one will create a new array of terms; you specify how many and then the 2nd argument allows the new, empty polynomial to be setup in the standard format for a polynomial which is where its terms are of ascending powers, otherwise, the exponent part for each term is set to just 0.
/// <summary>
/// Construct a empty polynomial with space for inNumTerm polynomials (can't grow)
/// </summary>
/// <param name="inNumTerms">Number of terms this polynomil has</param>
Polynomial(int inNumTerms, bool useSequentialExponents = false) : numTerms(inNumTerms)
{
terms = new Term[inNumTerms];
if(useSequentialExponents)
{
for(auto t = 0; t < inNumTerms;t++)
{
terms[t].SetExponent(t);
}
}
}
Next, this constructor will allow you to take the terms of another polynomial and use them as your own. It copies the terms and uses them to construct the new polynomial:
/// <summary>
/// Construct a polynomial as a series of input terms (copied)
/// </summary>
Polynomial(Term inTerms[], int inNumTerms)
{
terms = CopyTerms(inNumTerms, inTerms);
numTerms = inNumTerms;
}
This is similar to the next constructor, which is the copy constructor which just a copy of another polynomial and pretty much does the same as if you just passed in the copy of terms.
/// <summary>
/// Construct a Polynomial by copying another
/// </summary>
/// <param name="other"></param>
Polynomial(const Polynomial& other)
{
terms = CopyTerms(other.GetNumTerms(), other.terms);
numTerms = other.GetNumTerms();
}
To copy terms, I use this. It basically dynamically allocated a new set of terms in memory and makes clones of the incoming terms.
/// <summary>
/// Make a copy of inTerms and use that to replace our terms
/// </summary>
Term* CopyTerms(int inNumTerms, Term inTerms[])
{
auto newTerms = new Term[inNumTerms];
// Take a copy of all terms and use as our own
for (auto t = 0; t < inNumTerms; t++)
{
// copy term
newTerms[t] = inTerms[t];
}
return newTerms;
}
later, on I'm sure to delete the memory:
~Polynomial()
{
delete [] terms;
}
Here is where it starts becoming interesting, adding polynomials:
/// <summary>
/// a) Add to polynomials
/// </summary>
Polynomial operator+(const Polynomial other)
{
auto maxNumTerms = GetLargestExponent(*this, other) + 1;
// Ensure the polynomial are in standard format i.e, acending powers of x
Polynomial meStd = ToStdFormat(*this, maxNumTerms);
Polynomial youStd = ToStdFormat(other, maxNumTerms);
// Create empty resulting polynomial in standard format, i.e acending powers of x
Polynomial resultPoly(maxNumTerms, true);
// Add like terms
for(auto t = 0; t < maxNumTerms;t++)
{
resultPoly.terms[t].SetCoeff(meStd.terms[t].GetCoeff() + youStd.terms[t].GetCoeff());
}
return resultPoly;
}
The approach I took was to get two polynomials being added together into a format where we can just add each term position with the opposite term in the same position in the other polynomial.
That would be easy it's not guaranteed that the polynomials are like that. For instance, one could have a term with a power of 2 while the other polynomial doesn't have a term of degree 2, and starts instead at say, 4. So you need each polynomial to have the same number of terms, even if some are empty. That's what ToStdFormat function does. But before that, we need the resulting polynomial to also be the same number of terms. We determine the largest number of terms we need and then make polynomials of that degree and fill in the terms of the data and then add like terms. That's pretty much it.
I figured that we could do something similar with subtracting two polynomials. So converting the polynomials into the standard format makes it easier.
/// <summary>
/// b) Subtract two polynomials
/// </summary>
Polynomial operator-(const Polynomial other)
{
auto largestExponent = GetLargestExponent(*this, other);
auto maxNumTerms = largestExponent + 1;
Polynomial meStd = ToStdFormat(*this, maxNumTerms);
Polynomial youStd = ToStdFormat(other, maxNumTerms);
Polynomial result(maxNumTerms, true);
for(auto t = 0; t < maxNumTerms;t++)
{
result.terms[t].SetCoeff(meStd.terms[t].GetCoeff() - youStd.terms[t].GetCoeff());
}
return result.Simplify();
}
Here is where things get a lot more complicated. Multiplication. The problem with multiplication is that you've got to distribute terms, and ultimately you need to simplify like terms that are created as a result of the multiplication.
In essence, I'm just doing the procedure we learnt in school... Basically, we know that the number of resulting terms is a product of the number of terms of the two participating polynomials. We create a result polynomial with that many terms and then we set out to populate it.
/// <summary>
/// d) Multiply two polynomials
/// </summary>
Polynomial operator*(const Polynomial other)
{
Polynomial theirPoly = other;
// Result will have a fixed number of terms, i.e poly1.GetNumTerms() x poly2.GetNumTerms()
auto resultNumTerms = numTerms * theirPoly.GetNumTerms();
// Create empty polynomial
Polynomial resultPoly(resultNumTerms);
int resultTermNum = 0;
// Distribute and multiply our terms over other's terms
for(auto numOurTerm = 0; numOurTerm < numTerms; numOurTerm++)
{
for(auto numTheirTerm = 0; numTheirTerm < theirPoly.GetNumTerms(); numTheirTerm++)
{
auto theirTerm = theirPoly.GetTerms()[numTheirTerm];
// Multiply the coefficient
auto coeffResult = terms[numOurTerm].GetCoeff() * theirTerm.GetCoeff();
// calculate the exponent
int expResult = terms[numOurTerm].GetExponent() + theirTerm.GetExponent();
// Store the result into the result term
auto* ptrResultTerm = &resultPoly.GetTerms()[resultTermNum];
// store
ptrResultTerm->SetCoeff(ptrResultTerm->GetCoeff() + coeffResult); // combine with existing term
ptrResultTerm->SetExponent(expResult);
resultTermNum++; // move onto the next term to calculate in the result polynomial
}
}
// Return result but simplify the polynomial first
return resultPoly.Simplify();
}
This result however is like terms being in the resulting polynomial and that annoyed me. So I created a complicated simplify method, how ironic.
What this method does is it goes through each term in the result, and looks ahead for other like terms in it. If it finds it, it adds them together and puts the result back into the first term, and set the other like term to cancelled. Thats why the Term class has that function. Long story short, the resulting polynomial has a whole bunch of terms that are either aggregated by other like terms and those like terms that were used are cancelled and will not be printed when we print a polynomial. They are effectively 0 coefficient term after we used them:
/// <summary>
/// Simplify/aggregate like terms in the polynomial
/// </summary>
Polynomial Simplify()
{
Polynomial result(numTerms);
for(auto t = 0; t < numTerms; t++)
{
// Add this term to the result and we'll add to it if we find like terms:
result.terms[t] = terms[t];
// Look for like terms in the other terms
for(auto t2 = 0; t2 < numTerms; t2++)
{
// Dont consider myself or other terms that are empty/cancelled as candiates to use for simplification
if(t == t2 || (terms[t2].IsCancelled() || terms[t].IsCancelled()))
{
continue;
}
// if exponents are the same, can simlify terms as like-terms:
if(terms[t].GetExponent() == terms[t2].GetExponent())
{
// Add like term to result term
auto* resultTerm = &result.GetTerms()[t];
resultTerm->SetCoeff(resultTerm->GetCoeff() + terms[t2].GetCoeff());
resultTerm->SetExponent(terms[t].GetExponent());
// cancel term
terms[t2].SetIsCancelled(true);
}
}
}
return result;
}
I added the ability to print polynomials and terms too. You can see how I avoid printing cancelled terms or terms with 0 as a coefficient.
/// <summary>
/// Print a Term
/// </summary>
std::ostream& operator<<(std::ostream& stream, Term& term)
{
stream << term.GetCoeff() << "x^" << term.GetExponent();
return stream;
}
/// <summary>
/// Print a Polynomial
/// </summary>
std::ostream& operator<<(std::ostream& stream, Polynomial& poly)
{
for( auto t = 0; t < poly.GetNumTerms();t++)
{
if(poly.GetTerms()[t].IsCancelled() || poly.GetTerms()[t].GetCoeff() == 0)
{
// skip printing empty terms, ie terms with coefficent of 0
continue;
}
stream << poly.GetTerms()[t] << " ";
}
return stream;
}
To try this out let add two polynomials:
\[ (10x^2 + 2x^3) + (x^2 + 3x^3 + 2x^4) \]
This is the code that will input that from the user:
int main(int argc, char* argv[])
{
runTests();
Polynomial poly1 = GetPolynomial("p1");
cout << "p1 = " << poly1 << endl;
Polynomial poly2 = GetPolynomial("p2");
cout << "p2 = " <<poly2 << endl;
cout << endl;
Polynomial sum = poly1 + poly2;
cout << "p1 + p1: " << sum << endl;
Polynomial product = poly1 * poly2;
cout << "p1 * p2:: " << product << endl;
Polynomial difference1 = poly1 - poly2;
cout << "p1 - p2: " << difference1 << endl;
Polynomial difference2 = poly2 - poly1;
cout << "p2 - p1: " << difference2 << endl;
Polynomial compoundAddResult = poly1 += poly2;
cout << "p1 += p2: " << compoundAddResult << endl;
cout << "p1 now: " << poly1 << endl;
Polynomial compoundSubtractResult = poly1 -= poly2;
cout << "p1 -= p2: " << compoundSubtractResult << endl;
cout << "p1 now: " << poly1 << endl;
}
This is how I read in the polynomials in from the user:
Polynomial GetPolynomial(std::string polyName)
{
cout << "Enter the number of terms for " << polyName << ":";
int numTerms;
cin >> numTerms;
Term* terms = new Term[numTerms];
cout << "Enter the coefficients:";
for(int t = 0; t < numTerms;t++)
{
int coeff;
cin >> coeff;
terms[t].SetCoeff(coeff);
}
cout << "Enter the exponents:";
for(auto t = 0; t < numTerms;t++)
{
int exp;
cin >> exp;
terms[t].SetExponent(exp);
}
// Create polynomial
Polynomial result(terms, numTerms);
delete [] terms;
return result;
}
You need to specify the number of terms for each polynomial, then give its the coefficients then its exponents. So for:
\[ (10x^2 + 2x^3) + (x^2 + 3x^3 + 2x^4) \]
Enter the number of terms for p1:2
Enter the coefficients:10 2
Enter the exponents:2 3
p1 = 10x^2 2x^3
Enter the number of terms for p2:3
Enter the coefficients:1 3 2
Enter the exponents:2 3 4
p2 = 1x^2 3x^3 2x^4
p1 + p1: 11x^2 5x^3 2x^4
p1 * p2:: 10x^4 32x^5 26x^6 4x^7
p1 - p2: 9x^2 -1x^3 -2x^4
p2 - p1: -9x^2 1x^3 2x^4
p1 += p2: 11x^2 5x^3 2x^4
p1 now: 11x^2 5x^3 2x^4
p1 -= p2: 10x^2 2x^3
p1 now: 10x^2 2x^3
Which pretty much covers overloading the +, - and compound += and -= operators.
Also, the multiplication nicely handles implying the polynomial so no duplication occurs. However, the problem with it is that, unlike addition and subtraction, the result is not in the standard format.
It's got other problems too. It's too complicated, it can't handle provided polynomials that are not in the standard format, i.e like terms or out-of-order exponents etc. so on the while, its a bit iffy to say the least, but it works in the simple cases which serves its purpose.
Now, coffee.