C++, how do i create polynomial using ADT?

[Sadaiyappan]

Hi, I know the operations and what they must do, it's the implementation that I don't know how to do. How do I create an ADT to represent polynomials? I don't know where to begin.

 

[QuixoticOne]

Your question isn't incredibly clear. There could be a lot of different meanings and strategies for polynomial representation depending on what you're trying to do.

You might do it very differently if you were working on a symbolic mathematics computer algebra system than if you were working on a numerically calculating polynomial evaluator.

A common way to represent polynomials is by a vector (1D) or matrix (2D) of their coefficients with the index along a row represents the coefficient of the corresponding power term.

2*x^0 + 3*x^1 + 4*x^2 + 5*x^3 + 6*x^4, ... k*x^n
= Row Vector { 2, 3, 4, 5 , 6,..., k }.
Or sometimes one may choose the ordering of the coefficients to be reversed.

http://www.network-theory.co.u...octave/octave_153.html
http://www.obihiro.ac.jp/~suzu...e/html/octave_124.html

Look up in wikipedia and planet math and wolfram's math world:
http://en.wikipedia.org/wiki/Vandermonde_matrix
http://en.wikipedia.org/wiki/Polynomial_matrix
http://en.wikipedia.org/wiki/Characteristic_polynomial
http://en.wikipedia.org/wiki/Characteristic_equation
http://en.wikipedia.org/wiki/Determinant

So, basically, all you need are vectors and matrices + code.

 

[Sadaiyappan]

well i wanted to use a linked list, but I don't know the syntax and code for creating a linked list that has a polynomial stored in it..

 

[Sadaiyappan]

As I understand this below is the basic code for linked list:

struct node
{
int coeff; // coefficient
char var; // variable
int exp; // exponent (must be positive)
node *nxt; // Pointer to next node
};

node *start_ptr = NULL;

But I was wondering where I would place this code (does it go in the implementation of the interface or in the driver program itself???)

 

[degibson]

#include <list>

class PolyNode {
int m_nCoeff;
/* Anything else you feel you want */
};

list<PolyNode> l;

See also: www.cppreference.com (for list API, for example)

 

[QuixoticOne]

Your class / data structure definition would typically go in a header file, and the code that uses that class / ADT would go in a code file. You said that you're using C++; STL has built in LIST types by the way.

Coefficients are not typically restricted to integers.

There's not too much point in storing a 'char' variable element unless you know that you're trying to handle polynomials in multiple variables. If you are using multiple variables and expressions that can symbolically refer to a polynomial or which when evaluated generate a polynomial, the coefficient and exponent might as well be expressions themselves, and the 'variable' itself turned into an expression.

A[0] * Q^E[0] + A[1] * Q^E[1] + ..... can certainly be a polynomial too depending on the values of A[], Q, and E[], but if you're trying to store the symbolic representation of it then a string or some kind of list either for the whole expression or for the sub elements of the expression would be appropriate. If you knew this was designed to be a polynomial in one variable, Q, you might just store the expression (string, numeric, or other type) element vectors A[] and E[] and treat Q as implicit or as a variable in the instance class and not associated with each term.


If you're just dealing purely numerically with a polynomial in one variable then just using a vector of some sufficiently precise numeric type like perhaps 'double' to represent the coefficients alone is convenient for numeric processing.