Help needed with polynomials using linked lists!!! urgent!!

[maple123]

Hey everyone,

I need help creating a program that will add and multiply polynomials using linked lists. The polynomials that will be added and multiplied by my program are taken from an input file. This file contains the polynomials in the form:

3 2
5 1
3 0
XXX
2 1
3 0

The polynomials represented here are 3x^2 + 5x + 3 and 2x + 3

I was thinking about representing the polynomials as linked lists where each node has an integer for the coefficient and an integer for the exponent and finally a pointer to the next node. Do I need more than one class to be able to add and multiply the polynomials or would one be sufficient?

[StuXYZ]

That doesn't sound useful idea. Consider this

(a) A polynomainal multiplication is a N * M process were the length of the polynominial are M and N.
(b) The polynominal can be sparse e.g. x^8+x.

Ok: the first thing is that an linked list can be used for almost ANY computer data/algorithm, for example Knuth shows the proof that a tree structure algorithm can be converted into a linked list algorithm
(at a cost of efficiency).

Second were do you want to go with this. If you have a REALLY sparse polynominial and you want to move to some kind of list, but a vector (for random access is better), which holds the powers and coefficients.
BUT the key element against a linked list is the insert construction is not likely to happen (or can be easily avoided). e.g consider multiplicaton. This can be done (low to high) or (high to low) . Let us consider high to low. Consider two polynomials with powers
A1,A2,A3... and B1,B2,B3.. where A1>A2 etc and B1>B2 etc.
Now the first multiplication you do is A1*B1 which gives the largest power, then you consider A2*B1 and A1*B2 either one must be the bigger term and hold the result of the other, then continue down the lists. You then have constructed in order the polynomial produce with the use of only one tempory and is it also ordered.

Now what else would you like to do with your polynominal, evaluation is easy regardless of storage type, BUT factorization becomes a complete mess, since you have to traverse the polynominal to many times to do the equivilent binary search that the mid point division mechanism use. This is a not good.

So overall I think you generate a good deal of extra overhead for minimal benefit.

The key element to the decision is what process is easier with a linked list that a simple flat array of (power, coeff) does not solve?
If you have a good answer for the question (a) use a linked list,
(b) please post a follow up since I am curious.

Summary:

I would use a simple struct for polynominal coeff. and power
and it would be a template class to take either complex/polynominal [This specialization is not perhaps necessary for your problem space].

The I would add a class to hold the polynominal. It will handle evaluation, root finding etc.

Minor point: polynominals are normally implemented with double, complex or polynominal coefficients. Think about the last one for a moment, the reason is that [tex]x^2y^2+3(x+1)y+4y+x+3=0[/tex]
is a polynominal of y with, coeffients [tex]x^2, 3x+7, x+3[/tex] for
the powers of y: (2,1,0).

[maple123]

I have to used the linked lists and believe that my program will not have to take into account some of the things in your comment such as root finding. All my program has to do is add, multiply, and output the result of both operations. After some googling, I still have some unanswered questions:

1. How do I transfer the data from the input file to the nodes in my linked
lists?
2. What would be the best way to store these polynomials using linked lists?
3. Where would be a good place to code the overloading of my operators for
addition and multiplication?
4. The program has to invoke my executable and input/output files on the
command-line. I am not sure what this is, can you please explain?

[Lerner]

1) Use an fstream in in mode or a dedicated input stream called and ifstream.
2) A given linked list represents a given polynomial. Each node in the linked list represents a term of the polynomial (a term means a coefficient a variable and an exponent of form cx^e). The nodes should be ordered, either ascending or descending, by the value of the exponent. Each node in a ginen list should have a unique exponent. You should have a class to represent nodes (terms) and a separate class to represent a list (polynomial).
3) the operators should be members of the list class.
4) after the pormpt in a console window you type in the name of the program to run (and whatever other variables the program needs entered at the command prompt).

[maple123]

Thank you for your help, Lerner. I am afraid I do not understand why the polynomial class is there. Wouldn't one be able to create a linked list of just Term nodes and that would be it for the polynomial? Also, I am kind of jumping around because I feel stuck on things and cannot proceed on them so I work on other things. One of these things I took a look at was the addition and multiplication. These are actually a lot harder than I thought they would be. I thought it would be easy but I forgot that the amount of terms I can have in the polynomial could always change. This way, I can't write a function that will explicitly go through the process of adding and multiplying terms. What would have to change if the amount of terms change with every polynomial?

To try and make it more clear, what I mean is that I will not always have a 3-term and 2-term polynomial to add/multiply. I could get a 6-term and 1-term, anything really. How would I overload my operators to accommodate for the change?

[Lerner]

Any list could be used as a representtion for a polynomial. If you are allowed to use the STL list class, go for it. If you have to write your own code for a list then you could do it C style (though you wouldn't be talking about overloading operators then) or you could create your own list class. Whether that class is called list or polynomial is immaterial. It will have to function as a list no matter what name it has. (Note, just so you know, polynomials don't have to be internally repesented by lists, but if representing a polynimial as a list is your assignment, then so be it).

Rember polynomials can be thought of as a group of terms of indefinite size. That is, the polynomial 1x^2 is the same as 1x^2 + 0x^1 + 0x^0 and it is the same as 0x^4 + 0x^3 + 1x^2 + 0x^1 + 0x^0. So, when using two polynomials you can compare the two to determine the one with the term with largest exponent that has a non-zero coefficient and expand the other one to have the same number of terms. Then, if you always include all terms of the polynomial, even those that have zero for a coefficient, and if the terms are sorted by exponent using the same rule (that is the terms are sorted either ascending or descending order in both polynomials) it becomes a matter of looping through the lists and manipulating coefficients of the terms with the same exponents to do adding and substracting. That means if you want to add x^2 + 6 and 4x - 6 you will really be adding
1x^2 + 0x^1 + 6x^0 and 0x^2 + 4x + -6x^0 to get 1x^2 + 4x^1 + 0x^0, or, written more conventionally, x^2 + 4x. I believe that mathematicians sometimes refer to the value of the largest exponent of the term with a non-zero coefficient in a polynomial as the rank of the polynomial.

To do muliplication you don't really need to expand the terms to get the same number of terms with the same exponents. (You don't even NEED to do it for addition/subtraction, but I sure find it easier when I do). You can just use a nested loop to generate all the terms in the product. Generally, you would also simplify the product by grouping like terms (that is, add the coefficients with terms having the same variables and the same exponents), though whether you want to do this or not is up to you.

Division of two polynomials is a whole nother story, and I won't venture there.

Here's a bare bones skeleton of how you might organize the process:

struct Term  //aka node
{};

struct Polynomial  //aka list
{
    Term * head;  //first Term (aka node) in the Polynomial (aka list)
    Polynomial add(); //could overload the + operator instead
    Polynomial subtract();//could overload the - operator instead
    Polynomial multiply();//could overload the * operator instead
    void display(); //could overload the << operator instead
    void build();
};

Polynomial A; 
Polynomial B;
Polynomial C;
A.build();
B.build();
C = A + B;
cout << C;
C = A - B;
cout << C;
C = A * B;
cout << C;

I warn you though. Don't try to write all of that at once. Be sure you can build polynomials and display them before you even atttempt to write code for the math operators.

[ayeshashahid]

can i see the overall code

[raptr_dflo]

can i see the overall code

If they had posted the overall code, then you'd be able to see it. Since the thread is over 2 years old at this point, I suspect the original poster has moved on.

Please do not post into ancient threads. Instead, create a new one if you have a specific question.