Polynomial Calculation

• Download demo project - 7 Kb
• Download source - 13 Kb

Introduction

This article is about how to calculate the points of a curve given a function in polynomial form as a string.

Examples of supported expressions:

• y = 3x + 4
• y = 2.5x^2 + 1/2x - 3
• y = x^1/2 + 3
• y = 4/3x^3 + x^2

Background

In a current project a data file contains the limits for a measured value. Some limits are curves with one X value and two Y values, Y1 and Y2. The curve is stored as three arrays of values. With many such curves in the file it uses a lot of space and it is tedious to enter and modify the data, especially if both of the Y values were constants, so I wanted a solution where the amount of data stored could be minimized but also make it easier to maintain the limits.

The obvious solution was to store the equation of the curve instead of the individual values. I looked around for any suitable solution, but they usually ended up be too advanced for my needs or addressing a different problem. Hence, I decided to write my own method that could take an arbitrary polynomial as a string and calculate the points of the curve.

This is the result and maybe it can be useful to someone else.

Using the code

The Windows form application is just used for showing the result in a graphical way. The main focus has been on the algorithm used to calculate the result.

Trying out the demo is pretty simple. Just follow the steps below.

1. Enter an expression in the supported form.
2. Select a value for x-start.
3. Select a value for x-end.
4. Enter the number of points to create. The points will be evenly distributed over the range.
5. Press the Calculate button and the points will be shown both in tabular and graphic form.

Regular Expressions

One main part of the code are the regular expressions that are used to parse the polynomial.

Polynomial Split

One expression is used to split the polynomial into separate terms and keep track of the sign. It also keeps track of the sign.

private static Regex PolynomSplitterExpression = new Regex(@"y\s*=((?<term>[^\+\-]+)(?<sign>[\+\-])?)+");

The polynomial 2.5x^2 + 1/2x - 3 will be divided into the following terms:

(The column names are the same as the group names of the regular expression)

Term Analyser

The other expression is used to split each term into constants and exponents that can be used in the code.

private static Regex TermSplitterExpression = new Regex(@"^(?<k_n>[0-9\.]*)\s*(/)?\s*(?<k_d>[0-9]*)\s*(?<x>x{0,1})\s*(\^\s*(?<exp_n>[0-9\.]+)\s*(/)?\s*(?<exp_d>[0-9]*))?$");

For each X-value the term is calculated according to the formula in the table and added to the Y-value.

Source Code

This code calculates the value of the fraction given the numerator and denominator as strings.

#region Calculate the constant and exponent for each term
foreach (Capture capTerm in m.Groups["part"].Captures)
{
  Match mTerm = TermSplitterExpression.Match(capTerm.Value.Trim());
  if (!mTerm.Success)
    throw new Exception(String.Format("The term '{0}' is not supported.", capTerm.Value.Trim()));

  string s = m.Groups["sign"].Captures[captureIndex++].Value.Trim();
  if ((s == "+") || (s == "")) // If empty a positive value is assumed.
    sign = 1;
  else if (s == "-")
    sign = -1;

  // Calculate the value of k and set the sign
  k = sign * CalculateFractionValue(mTerm.Groups["k_n"].Value, mTerm.Groups["k_d"].Value);

  // Check if x is present and calculate the exponent value
  if (String.IsNullOrEmpty(mTerm.Groups["x"].Value))
    exponent = 0.0;
  else
    exponent = CalculateFractionValue(mTerm.Groups["exp_n"].Value, mTerm.Groups["exp_d"].Value);
  
  // Add the values to the data table
  dtTerms.Rows.Add(k, exponent);
}
#endregion

private double CalculateFractionValue(string _num, string _den)
{
  // Initialize with default values
  double numerator = 1.0;
  double denominator = 1.0;
  // Get the numerator if not empty
  if (!String.IsNullOrEmpty(_num))
  {
    numerator = Convert.ToDouble(_num);

    // Get the denominator if not empty
    if (!String.IsNullOrEmpty(_den))
      denominator = Convert.ToDouble(_den);
  }

  // Calculate the fraction
  return (numerator / denominator);
}

I have chosen to use a DataTable as the container for the calculated points, just out of convenience for how I will use the points later. Of course a dictionary can be used instead if that is more suitable for other needs.

The code extract below shows how the curve points are calculated.

// Calculate the step size used for the Y value calculations
double stepSize = (endX - startX) / (double)countX;
double y = 0.0;
for (double x = startX; x <= endX; x += stepSize)
{
  y = 0.0;
  foreach (DataRow drTerm in dtTerms.Rows)
  {
    k = (double)drTerm["k"];
    exponent = (double)drTerm["exp"];

    // y = k * Math.Pow(x, exponent) could be used for all calculations
    // but this code is a bit more efficient for a large number of points
    if (exponent == 0.0)
      y += k;
    else if (exponent == 1)
      y += (k * x);
    else
      y += (k * Math.Pow(x, exponent));
  }

  // Add the values to the data table
  dtPoints.Rows.Add(x, y);
}

Limitations

As I so far only had use for the most basic polynomials, the following terms are not supported:

• 1/x (neither can x^-1 be used)
• e^x
• ln(x)
• log_n(x)

Maybe this will be added in a future release.

Points of Interest

For help on understanding regular expressions and how to write them I recommend this site. Regular-Expressions.info

There are plenty of sites with good information, but this one has helped me a lot in the past.

History