13,289,274 members (54,808 online)
Tip/Trick
alternative version

#### Stats

5.9K views
4 bookmarked
Posted 17 Dec 2012

# Multivariate polynomial

 Rate this:
Implement a multivariate polynomial class for a large number of terms.

## Introduction

Multivariate Polynomial is a C# class library providing basic polynomial arithmetics such as addition, multiplication and exponentiation, differentiation by one variable , Division by one term polynomial and evaluation by get variable and it's value.

Multivariate polynomial definition:

F(x,y,z,k,l)=2.2xy1.2z6k-5

A polynomial that multivarates, look at this grammar definition :

multivariate polynomial structure is :

E1[+/-]E2[+/-]E3…[+/-]En

that E is

[R][a…z][R][a…z][R]…[a…z][R]

and R is

[N].[N] or [N]

and in other hand a multivariate polynomial is terms that each term is a function of some variable

Example:

```23.42bd5.3fgh3j3s1.43+d3f3s3+4x+3432432
23.42bd5.3fgh3j3s1.43+d3f3s3+4x+3432432
d3f3s4-34e3r4w10
796.28bd5.3e3fgh3j3r4s1.43w10-23.42bd5.3fgh3j3s1.43-34d3e3f3r4s3w10
+d3f3s3+3432432d3f3s4+4d3f3s4x-116702688e3r4w10-136e3r4w10x```

This class implements operators and polynomial string readers and you can calculate polynomial operations simply the same as scalar variables:

```P1=p2*p3+p4/p5+p6;
P2=(p1/p2*p4)/p7-p12+p2;```

My goal in this class is to implement a multivarate polynomial class for large number of terms for example 50000, and using structures for memory usage and speed (low complexity).

For this reason I implement a polynomial term array and control it using a heap structure .

Heap structure is a continuous memory that that does not have any gap in the array and results in speedy access.

This class implements:

1. Read and get string format of polynomial in sorted way (standard writing)
2. Control memory usage
3. Ease of use
4. Take care about class structure and its separation
5. Find term in from log n to N at most complexity
6. Insert terms in log N complexity
7. Get memory for terms when it needed
8. Write ToString in all subclass levels to multivariate polynomial
9. Sorting term laws:
• From left to right in 2 term , from less character variable code ( comparing variables)
• In equal variable name less power is first

## Using the code

Object definition :

`MutliVariantPolynomial ff=new MutliVariantPolynomial(50000); `

This constructor gets maximum term number and builds a refrence polynomial term array

or

`MutliVariantPolynomial ff=MutliVariantPolynomial("2.2xy1.2z6k-5",10000) `

this constructor build polynomial with polynomial string that describe in introduction

## Points of Interest

this class for fast sorting and build strings and add terms , define some property in multivariate polynomial such as TermVarString and TermString :

TermVarString: a sring that build from concatenation of term variables ( in sorted order)

TermString: a sring that build from concatenation of term variables and It's power( in sorted order and rounded power in fixed point number)

CompareTo Method in PolynomTerm:

```internal int CompareTo(PolynomTerm polynomTerm)
{
if (termVarString != polynomTerm.termVarString)
{
if(termVarString=="")
return 1;
if (polynomTerm.termVarString == "")
return -1;
}

int mogh=termVarString.CompareTo(polynomTerm.termVarString);
if (mogh >0)
return 1;
if (mogh<0)
return -1;

foreach (char ch in termVarString)
{
if (termPartials[ch - 'a'].pow > polynomTerm.termPartials[ch - 'a'].pow)
return 1;
if (termPartials[ch - 'a'].pow < polynomTerm.termPartials[ch - 'a'].pow)
return -1;
}

return 0;
}```

and smallest priority is empty `TermVarString` or constants.

The classes that are implemented in this project is:

Constants: Define Static Constants for other class using

TermPartial: x2 and y1.2 and z is termpartial of -4x2y1.2z and this class goal is manage termpartial

PolynomTerm: manage one term in polynomial : [R][a…z][R][a…z][R]…[a…z][R] that contain one coefficient and one array of termpartial.

MutliVariantPolynomial: manage last polynomial that contain some `PolynomTerm` object in array and it's insert and delete and find and `tostring` operation implemented by heap structure.

Example of `InsertTerm` code in `MultivaratePolynomial` class that inserts a new term in polynomial is :

```bool InsertTerm(PolynomTerm x)
{
int i;
PolynomTerm pt;
if (cntTerm == maxTerm)
return false;
else
{
cntTerm++;
i = cntTerm;
terms[cntTerm] = x.Clone();
while (true)
{
if (i == 1)
break;
if (terms[i].CompareTo(terms[i / 2]) >= 0)
break;
pt = terms[i];
terms[i] = terms[i / 2];
terms[i / 2] = pt;
int kk = i;
i = i / 2;
if (kk % 2 == 0)
{
if (kk < cntTerm)
if (terms[kk].CompareTo(terms[kk + 1]) > 0)
{
pt = terms[kk];
terms[kk] = terms[kk + 1];
terms[kk + 1] = pt;
}
}
else if (kk != 1)
if (terms[kk - 1].CompareTo(terms[kk]) > 0)
{
pt = terms[kk - 1];
terms[kk - 1] = terms[kk];
terms[kk] = pt;
}
}
terms[i] = x.Clone();
return true;
}
}```

Version 1.0