Simple Polynomial Addition and Subtraction

• Download source - 23.6 KB

Introduction

This project illustrates one way to implement addition and subtraction of polynomials in C#.

Background

As you remember from your first algebra class, in 3.14x³, 3.14 is the coefficient, x is the variable, and 3 is the exponent. This is called a term, and a polynomial is a sum of 1 or more terms. Adding and subtracting polynomials is quite simple. For example, to add 4x³ + 3x² + 5x and 3x³ - 2x² + 3x, you line up the like terms, and add the coefficients:

4x³ + 3x² + 5x
3x³ - 2x² + 3x
--------------
7x³ + 1x² + 8x

Things can get tricky when the terms have multiple variables, for example, x³y²z⁴. Since this is mathematically identical to z⁴y²x³, if we represent the polynomial as a List in C#, we will have to implement some type of sorting to keep all of our terms consistent. This is where Lambda Expressions are helpful. Lambda Expressions are a powerful feature of C# and are documented in numerous places on the web and in CodeProject so I will not attempt to explain them. Jon Skeet for one, does a great job of explaining Lambda Expressions.

Using the Code

The class Variable stores a variable like x³ where Name is 'x' and Exp is 3. Note that we are using C#'s Auto Implemented Properties.

public class Variable
{
   public char Name { get; set; }
   public int Exp { get; set; }
}

The class Term is used to store a term like 3.0x²y³ where 3.0 is the coefficient, and Vars is a Generic List of two Variables, one where Name is 'x' and Exp is 2, and one where Name is 'y' and Exp is 3.

public class Term
{
    public double Coefficient { get; set; }
    public List<Variable> Vars { get; set; }
}

The class that stores the polynomial, Poly, is simply a Generic List of Terms:

public class Poly
{
    private List<Term> Terms { get; set; }
}

I admit the constructing of the polynomial in code is rather inelegant, and I plan on adding a parser to the next version to simplify the task. This then, is how we would build the two-term polynomial 3.5x³y²z⁴ - 2.7x²y³:

Poly polynomial1 = new Poly();
Term t10 = new Term(+3.5, new List<Variable> 
{ new Variable('x', 3), new Variable('y', 2), new Variable('z', 4) });
Term t11 = new Term(-2.7, new List<Variable> 
{ new Variable('x', 2), new Variable('y', 3) });
polynomial1.AddTerm(t10);
polynomial1.AddTerm(t11);
Console.WriteLine("{0}", polynomial1.ToString());

Note that ToString() is overloaded and displays the polynomial like this:

+  3.50x^3y^2z^4 -  2.70x^2y^3

When the two polynomials have terms that are identical, the coefficients are added as mentioned previously. This is done in the public Poly Sum(Poly addend) method by going through each term of the polynomial and adding the coefficients. (In this version, I converted the lists to arrays to simplify this task.) However, suppose we wish to add two polynomials that have terms (ignoring the coefficients for the moment) that are mathematically identical, but for which the variables are in a different order, for example 10.0x³y²z⁴ and 20.0z⁴y²x³. The strategy I chose is to sort the variables alphabetically using this Lambda Expression in the AddTerm() method:

term2.Vars.Sort((t1, t2) => t1.Name.CompareTo(t2.Name));

Now the polynomials will have the variables in the same order: 10.0x³y²z⁴ and 20.0z³y²z⁴. Also in AddTerm(), I build a string called sortString that simply contains the variables and exponents without the coefficient to make it easy to compare two terms to see if they can be added. In this example, the sortString is "x3y2z4". When we add two polynomials, as we march through the list of terms, and if the sortString's are the same, that means we add the coefficients. Since it is customary to write a polynomial with the term with the highest coefficient of the first variable first, I use this Lambda Expression to sort all the terms:

Terms.Sort((t1, t2) => t2.SortString.CompareTo(t1.SortString));

The Sum() method in the Poly class assumes both polynomials have the same terms and differ only in their coefficient. The issue is what to do when there a term that is present in one polynomial but missing from the other. The strategy I chose is to add the missing term to the polynomial that is missing it with a coefficient of zero (I call this a "dummy" term"). This is implemented in the method Normalize(Poly p1, Poly p2) in the Poly class.

Points of Interest

The Term class implements the IEquatable interface. The Equals method compares sortString to determine if two terms are equivalent. I have included links in the source code that describe this interface.

History

• November 30^th, 2014: Version 1