12,255,451 members (29,353 online)
Tip/Trick
alternative version

7.2K views
10 bookmarked
Posted

# Polynomial Calculation

, 21 Jun 2014 CPOL
 Rate this:
How to calculate the points on a curve from a given polynomial.

## Introduction

#### 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
}
#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
}
```

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

## Share

 Architect Philippines
I have worked with mobile phone testing in manufacturing for 20 years.
Originally from Sweden, but moved to China in 2012.
At the moment I am on a sabbatical year in the Philippines.

Over the years I have used various programming languages such as Pascal, C, C++, C#, SQL, XML, XSLT.

## You may also be interested in...

 First Prev Next
 My vote of 5 Gun Gun Febrianza30-Oct-14 17:38 Gun Gun Febrianza 30-Oct-14 17:38
 Re: My vote of 5 George Jonsson30-Oct-14 17:54 George Jonsson 30-Oct-14 17:54
 Horner's scheme YvesDaoust23-Jun-14 2:30 YvesDaoust 23-Jun-14 2:30
 Re: Horner's scheme George Jonsson23-Jun-14 3:09 George Jonsson 23-Jun-14 3:09
 Vote of 4 Kenneth Haugland22-Jun-14 12:52 Kenneth Haugland 22-Jun-14 12:52
 Re: Vote of 4 George Jonsson22-Jun-14 15:33 George Jonsson 22-Jun-14 15:33
 Last Visit: 31-Dec-99 18:00     Last Update: 6-May-16 10:41 Refresh 1