Here is a simple Polynomial class.
Its purpose is to show how one can simply create a Polynomial class without using abstract datastructures such as linked lists etc.
Each term is printed out in order of its power - from highest to lowest.
Inspiration was taken from a Java source code, the link appears to now be dead.
//-----------------------------------------------------------------------------
//
// A Polynomial Class
//
// Author: Iamthwee 2008 (c)
//
// Improvements:
// Could use a dynamic array as opposed to a static one.
// Could improve the print function to tidy up the output.
// Suffers from a space complexity issue but achieves lexicographic sorting
// very easily. I.e. prints terms in order of powers highest to lowest
// Could use operator overloading for code syntax candy lovers.
//
// Notes:
// Bugs may exist, not thorougly tested.
//
//------------------------------------------------------------------------------
#include <iostream>
using namespace std;
class Polynomial
{
//define private member functions
private:
int coef[100]; // array of coefficients
// coef[0] would hold all coefficients of x^0
// coef[1] would hold all x^1
// coef[n] = x^n ...
int deg; // degree of polynomial (0 for the zero polynomial)
//define public member functions
public:
Polynomial::Polynomial() //default constructor
{
for ( int i = 0; i < 100; i++ )
{
coef[i] = 0;
}
}
void set ( int a , int b ) //setter function
{
//coef = new Polynomial[b+1];
coef[b] = a;
deg = degree();
}
int degree()
{
int d = 0;
for ( int i = 0; i < 100; i++ )
if ( coef[i] != 0 ) d = i;
return d;
}
void print()
{
for ( int i = 99; i >= 0; i-- ) {
if ( coef[i] != 0 ) {
cout << coef[i] << "x^" << i << " ";
}
}
}
// use Horner's method to compute and return the polynomial evaluated at x
int evaluate ( int x )
{
int p = 0;
for ( int i = deg; i >= 0; i-- )
p = coef[i] + ( x * p );
return p;
}
// differentiate this polynomial and return it
Polynomial differentiate()
{
if ( deg == 0 ) {
Polynomial t;
t.set ( 0, 0 );
return t;
}
Polynomial deriv;// = new Polynomial ( 0, deg - 1 );
deriv.deg = deg - 1;
for ( int i = 0; i < deg; i++ )
deriv.coef[i] = ( i + 1 ) * coef[i + 1];
return deriv;
}
Polynomial plus ( Polynomial b )
{
Polynomial a = *this; //a is the poly on the L.H.S
Polynomial c;
for ( int i = 0; i <= a.deg; i++ ) c.coef[i] += a.coef[i];
for ( int i = 0; i <= b.deg; i++ ) c.coef[i] += b.coef[i];
c.deg = c.degree();
return c;
}
Polynomial minus ( Polynomial b )
{
Polynomial a = *this; //a is the poly on the L.H.S
Polynomial c;
for ( int i = 0; i <= a.deg; i++ ) c.coef[i] += a.coef[i];
for ( int i = 0; i <= b.deg; i++ ) c.coef[i] -= b.coef[i];
c.deg = c.degree();
return c;
}
Polynomial times ( Polynomial b )
{
Polynomial a = *this; //a is the poly on the L.H.S
Polynomial c;
for ( int i = 0; i <= a.deg; i++ )
for ( int j = 0; j <= b.deg; j++ )
c.coef[i+j] += ( a.coef[i] * b.coef[j] );
c.deg = c.degree();
return c;
}
};
int main()
{
Polynomial a, b, c, d;
a.set ( 7, 4 ); //7x^4
a.set ( 1, 2 ); //x^2
b.set ( 6, 3 ); //6x^3
b.set ( -3, 2 ); //-3x^2
c = a.minus ( b ); // (7x^4 + x^2) - (6x^3 - 3x^2)
c.print();
cout << "\n";
c = a.times ( b ); // (7x^4 + x^2) * (6x^3 - 3x^2)
c.print();
cout << "\n";
d = c.differentiate().differentiate();
d.print();
cout << "\n";
cout << c.evaluate ( 2 ); //substitue x with 2
cin.get();
}
i use it in commercial use , and take some change to better printing and optimized coding in plus,minus,multiple methods
see the code at http://SeeTheCode.co.cc
Yes you may use it for commercial use and are free to modify the code as you wish.
First off I commend you for investigating what I think is one of the most difficult classes to write. As always with a polynomial class, it is a case of compromises, and further improvements as scope and efficiency are improved.
There are a few aspects that I think the code would be better for.
First is that obviously polynomials are rarely integer, double or complex are common, and more interesting polynomials exist.
Second: Please don't do copy by value, use a copy by reference:
Polynomial minus ( Polynomial b ) // this copies a 100 integer array!!
{ }it is better to write:
Polynomial minus(const Polynomial& B) const
{ }I have added (a) constant and (b) B is copied by reference.
Finally, care needs to be taken with the degree. Often a polynomial system is being simplified. You would expect the degree to reduce in addition/subtraction. e.g
x^2+6x +3= 0 ; -x^2-4x+2=0 in addition make 2x+5=0 and the degree has reduced by one.
Basically, a polynomial class seems easy on the surface, but is horribly complex. There are significant problems along the way. Numerical issues abound, what do do about division, efficiency etc. Solutions, etc, special cases [quadratic->quintic],
and also do you want to handle 1/x etc.
What always seems to happen, is the the polynomial class is converted into a specialized polynomial class for the local use, and a different polynomial class ends up begin written for each project.
>First off I commend you for investigating what I think is one of the most difficult classes to write.
Thank you... But the hard work was taken from a java snippet. Really all I did was try to port it to c++ and probably did a p.iss poor job of it too.
>As always with a polynomial class, it is a case of compromises, and further improvements as scope and efficiency are improved.
Indeed.
>There are a few aspects that I think the code would be better for.
First is that obviously polynomials are rarely integer, double or complex are common, and more interesting polynomials exist.
True. I'd love to extend this to handle complex number or even multi-variate polynomials but I'm lazy.
>Second: Please don't do copy by value, use a copy by reference:
Noted.
>Finally, care needs to be taken with the degree. Often a polynomial system is being simplified. You would expect the degree to reduce in addition/subtraction. e.g
x^2+6x +3= 0 ; -x^2-4x+2=0 in addition make 2x+5=0 and the degree has reduced by one.
I believe the class as it stands does this.
>what do do about division
Yes division sure is messy.
I guess if I had all the time and patience in the world I would spend my time writing something like mathematica's engine.
Re: degree of polynomial.
I am sorry I mis-read/failed to understand the code. You are correct, in that the code does indeed find the correct degree.
Obviously, that is work in progress, since you seem to be implementing degree, as a way to improve efficiency. [e.g. limiting loops etc], and to avoid array overrun, in the case of multiplication [e.g. x^51 * x^50 is a problem].
I hope it works out. Everything associated with polynomials seems to be very very expensive. [cpu/memory etc] For example : the representation of quadratic/cubic surfaces in 3D. The solution of a three surface intersect, reducing three f(x,y,z)s, even at only order 2, [e.g. x^2, xy and below] gives a 16th power polynomial and 16^3 (4096) coefficient operations to reduce it from three equations in three variables to one equation in 1 variable. That is extremely expensive!!
I do think that you can just change your array to double or complex and with a few minor tweaks continue. e.g. instead of coeff[i]==0 you can write fabs(coeff[i])<tolerance . You might want to consider implementing a maxAbsCoeff and set the test to be fabs(coeff[i])<tolerance*maxAbsCoeff but depends on the problem set.
As to recreating mathematica, I would just settle for understanding about half of the maths in it.
Anyway, many thanks for submitting this code.
thank u
Good sir, do you have the contructor for you division? I can't seem to modify your code for the division part.
I think the way you set the polynomial really sucks. Why don't you use the same format as Matlab and set only the coeffiecents in an array where the index corresponds to the degree. For example, to set x^3 + x - 1, You could use a = [1, 0, 1, -1].
For degrees less than 1, for example, a = 1/x^2+ 1/x + 2 you could have an array within the array to hold positive powers in one and negative powers in the other. So this could be written as, a = [[2], [1,2]];
Keep up the good work.
why it doesn'y have a copyconstructor and assignment operator??? and even destructor???
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.