Click here to Skip to main content
Click here to Skip to main content
Go to top

Polynomial Calculation

, 21 Jun 2014
Rate this:
Please Sign up or sign in to vote.
How to calculate the points on a curve from a given polynomial.

CalculatePolygonial snapshot

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:

Polynomial Split
sign term Comment
  2.5x^2 Empty sign will default be set to +
+ 1/2x  
- 3 The last term is negative

(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.

k and exponent
term k_n k_d signed k exp_n exp_d exponent Code
2.5x^2 2.5 1 2.5 2 1 2 y += 2.5 * Math.Pow(x, 2);
1/2x 1 2 0.5 1 1 1 y += 0.5 * x; (more simple calculation when the exponent = 1)
3 3 1 -3 0 1 0 y += -3; (no need for calculation when the exponent = 0)

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)
  • ex
  • ln(x)
  • logn(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

Version Date Description
1.0 2014-06-22 Release of the first version.

License

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

Share

About the Author

George Jonsson
Architect
China China
I have worked with mobile phone testing in manufacturing for 20 years.
Originally from Sweden, but moved to China in 2012.
Over the years I have used various programming languages such as Pascal, C, C++, C#, SQL, XML, XSLT.

Comments and Discussions

 
QuestionHorner's scheme PinmemberYvesDaoust23-Jun-14 2:30 
AnswerRe: Horner's scheme PinmemberGeorge Jonsson23-Jun-14 3:09 
QuestionVote of 4 PinprofessionalKenneth Haugland22-Jun-14 12:52 
AnswerRe: Vote of 4 PinmemberGeorge Jonsson22-Jun-14 15:33 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web04 | 2.8.140916.1 | Last Updated 22 Jun 2014
Article Copyright 2014 by George Jonsson
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid