Click here to Skip to main content
65,938 articles
CodeProject is changing. Read more.
Articles / web / HTML

Simple Polynomial Addition and Subtraction

5.00/5 (1 vote)
2 Dec 2014CPOL3 min read 19.4K   266  
Simple Polynomial Addition and Subtraction using Lambda Expressions for sorting Lists

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.14x3, 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 4x3 + 3x2 + 5x and 3x3 - 2x2 + 3x, you line up the like terms, and add the coefficients:

4x3 + 3x2 + 5x
3x3 - 2x2 + 3x
--------------
7x3 + 1x2 + 8x

Things can get tricky when the terms have multiple variables, for example, x3y2z4. Since this is mathematically identical to z4y2x3, 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 x3 where Name is 'x' and Exp is 3. Note that we are using C#'s Auto Implemented Properties.

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

The class Term is used to store a term like 3.0x2y3 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.

C#
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:

C#
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.5x3y2z4 - 2.7x2y3:

C#
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:

C#
+  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.0x3y2z4 and 20.0z4y2x3. The strategy I chose is to sort the variables alphabetically using this Lambda Expression in the AddTerm() method:

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

Now the polynomials will have the variables in the same order: 10.0x3y2z4 and 20.0z3y2z4. 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:

C#
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 30th, 2014: Version 1

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)