Polynomial

[WilliamMorris]

Polynomial. I kinda have function which creates basic polynomial. But I need to form polynomial (𝑥 − 𝑎0 )(𝑥 − 𝑎1 ) … (𝑥 − 𝑎𝑛 )where a is double.What should I change?

#include <iostream>
using namespace std;

class Polynomial
{
private:
	int Nterms;
	double* pCoef;// from lowest to highest order
public:
	// functions
	double evaluateAt(double x);
	void print(void);

    // constructor
	Polynomial( double Coeffs[], int N_terms );// full construction from given array of coefficients
	// destructor
	~Polynomial();// destructor VERY important this case
};

// full constructor. Must be passed an array of coeffs. and the array size.
Polynomial::Polynomial( double Coeffs[], int N_terms )
{
	Nterms = N_terms;
	pCoef = new double[ Nterms ];// allocate an array to hold the coefficient values
	for(int i=0; i<Nterms; i++)
		pCoef[i] = Coeffs[i];// assign in straight order
}

// destructor - releases memory for the dynamically allocated coefficient array
Polynomial::~Polynomial()
{
	if( pCoef )
	{
		delete [] pCoef;
		pCoef = NULL;
	}
}
// finds P(x)
double Polynomial::evaluateAt(double x)
{
	double sum = 0.0;
	double xPow = 1.0;
	if( pCoef )
		for(int i=0; i<Nterms; i++)
		{
			//sum += xPow*pCoeffs[i];// add up the terms
			sum=
			xPow *= x;// build up the power of x from term to term
		}

	return sum;
}
// simple version produces crude output. Finetune to suit.
void Polynomial::print(void)
{
	// 1st term
	cout << pCoef[Nterms-1] << "x^" << Nterms-1;
	// remaining terms
	for(int i=Nterms-2; i>=0; i--)
		cout << " + " << pCoef[i] << "x^" << i;
	return;
}

int main(void)// example use
{
	// Pnum = 8*x^4 + 10*x^3 + x^2 + 29*x + 19
	double Cnum[5] = { 19.0, 29.0, 1.0, 10.0, 8.0 };
	Polynomial Pnum( Cnum, 5 );
	cout << "Pnum = ";
	Pnum.print();

	return 0;
}
 

[ne555]

I'm not sure what you want to do.
If you want to transform to the factorized form then https://en.wikipedia.org/wiki/Root-finding_algorithm#Finding_roots_of_polynomials

If you want the reverse, then just multiply them (convolution).

If you want to work directly in that form

class poly_atom{ //x-a_0
//...
   double coeff; //a_0
   //note: no a_1
};

class polynomial{
   std::vector<poly_atom> factors;
   double gain; //this multiplies all the factors, it is missing in your formula
};

Sorry, I'm quite rusty on the nomenclature. The idea is to have 2 classes:
- ones that represent (x-a)
- the polynomial, that's a collection of (x-a) and also has a multiply factor.

[gunnerfunner]

OP: you can try overloading the ctor (see below) but like ne555 I'm not quite sure what exactly you're trying to do

#include <iostream>
#include <string>
using namespace std;

class Polynomial
{
private:
	int Nterms;
	double* pCoef;// from lowest to highest order

public:
	// functions
	double evaluateAt(double x);
	void print(void);

    // constructor
	explicit Polynomial( double Coeffs[], int N_terms ) ;// full construction from given array of coefficients
	// destructor
	Polynomial (double Coeffs[], int N_terms, const string& x);
	~Polynomial();// destructor VERY important this case
};

// full constructor. Must be passed an array of coeffs. and the array size.
Polynomial::Polynomial( double Coeffs[], int N_terms )
{
	Nterms = N_terms;
	pCoef = new double[ Nterms ];// allocate an array to hold the coefficient values
	for(int i=0; i<Nterms; i++)
		pCoef[i] = Coeffs[i];// assign in straight order
}
Polynomial::Polynomial (double Coeffs[], int N_terms, const string& x )
{
    Nterms = N_terms;
	pCoef = new double[ Nterms ];// allocate an array to hold the coefficient values
	for(int i=0; i<Nterms; i++)
		pCoef[i] = Coeffs[i];// assign in straight order
    //x = string("x");
    for (int i = 0; i < Nterms; i++)
    {
        cout << "(" <<x<<"-"<< pCoef[i]<<")";
    }
}
// destructor - releases memory for the dynamically allocated coefficient array
Polynomial::~Polynomial()
{
	if( pCoef )
	{
		delete [] pCoef;
		pCoef = NULL;
	}
}
// finds P(x)
double Polynomial::evaluateAt(double x)
{
	double sum = 0.0;
	double xPow = 1.0;
	if( pCoef )
		for(int i=0; i<Nterms; i++)
		{
			//sum += xPow*pCoeffs[i];// add up the terms
			sum=
			xPow *= x;// build up the power of x from term to term
		}

	return sum;
}
// simple version produces crude output. Finetune to suit.
void Polynomial::print(void)
{
	// 1st term
	cout << pCoef[Nterms-1] << "x^" << Nterms-1;
	// remaining terms
	for(int i=Nterms-2; i>=0; i--)
		cout << " + " << pCoef[i] << "x^" << i;
	return;
}

int main(void)// example use
{
	// Pnum = 8*x^4 + 10*x^3 + x^2 + 29*x + 19
	double Cnum[5] = { 19.0, 29.0, 1.0, 10.0, 8.0 };
	Polynomial Pnum( Cnum, 5 );
	cout << "Pnum = ";
	Pnum.print();
	cout << '\n';
	string x = "x";

    Polynomial Pnum1 (Cnum, 5, "x");
	return 0;
}

[WilliamMorris]

Well this program makes basic polynomial. But I have to form polynomial according to this formula (𝑥 − 𝑎0 )(𝑥 − 𝑎1 ) … (𝑥 − 𝑎𝑛 ), a1, a2 are the different numbers and by multiplicating it should form polynomial.

[WilliamMorris]

Or at least it should form with brackets

[gunnerfunner]

(x + a)(x + b) = x^2 + (a + b)x + ab // not using the multiplication operator explicitly
(x + a)(x + b)(x + c) = x^3 + (a + b + c)x^2 + (ab + bc + ac)  x + abc
(x + a)(x + b)(x + c)(x + d) = x^4 + (a + b + c + d)  x^3 + (ab + bc + ca + ad + bd + cd) x^2 
				+ (abc + abd + bcd + cad) x + abcd 
....
(x + a)(x + b)(x + c) ... (x + n) = x^n + (a + b + ... + n) x^(n-1) + (all combinations of 2
from the n coefficients, multiply elements of each combination, then sum) x^(n-2) 
+ (all combinations of 3 from the n coefficients, multiply each combination, then sum) x^(n-3) 
+ ... + (abcd...n)

From here on, if you or anyone else have any solutions then I'd be very interested in seeing that. I've tried a few things but not being able to quite pin it down. Most of the stuff out there works on the first n integers 1, 2, ... , 3 while your co-efficients vector could have integers in any order. I'm guessing we'll need to sort this vector first but what happens then?

[lastchance]

WilliamMorris

Can you clarify exactly what you want to do.

There is nothing stopping you having a separate class with polynomial stored as the product form.

- Do you want to convert from the normal power series form to product form (i.e. find roots - problem is that some of these may be complex)?
- Do you want to convert from the product form to the power-series form? (Probably most easily done recursively, multiplying a bracket at a time).
- Or do you simply want to create a "product polynomial" class? In this case, you probably only need to change the evaluateAt( x ) and print() member functions of your existing class (and you will also have to be careful about how many coefficients you have: a[0] ... a[N] is N+1 coefficients).

You do need to be clear about what you are doing.

[gunnerfunner]

lastchance: I had a bet with myself that sooner or later you'd be on this thread ;)

[lastchance]

I had a bet with myself that sooner or later you'd be on this thread ;)

Whoops - acquiring a reputation, it seems! I do prefer the maths/science/engineering threads, I confess.

Let's see if the original poster can be a little clearer about his problem.

[WilliamMorris]

maybe I could use this function on multiplying polynomials?

pol& operator*(const pol& A); 
pol& pol::operator*(const pol& C)
{
	double G[100];
	for(int i=0;i<=maxl;i++)
	{
		G[i]=A[i];
	}
	delete []A;
	A=new double [100];
	for(int i=0;i<100;i++)
	{
		A[i]=0;
	}

    for(int i=0;i<=maxl;i++)
		{
			
			for(int j=0;j<=C.maxl;j++)
			{
			
				
				if(i+j!=0&&i+j!=maxl+C.maxl)
				{
					A[i+j]=A[i+j]+ G[i]*C.A[j];
				}
					else 
					{
						A[i+j]=G[i]*C.A[j];
					}
					
			}
		}
		maxl=maxl+C.maxl;
	
    return (*this);
} 

[WilliamMorris]

I just give you an example. I need to form a polynomial like this at first (x-1)(x-5)(x-6)(x-7) and give the product of this equations in the answer.

[lastchance]

WilliamMorris

I borrowed your code and tweaked it so that I have polynomial classes in both power series and product form. It is a bit different from yours in that my polynomials have N+1 coefficients, as I prefer x^N to be the highest degree term. This code is at the bottom.

If you want to create a polynomial by multiplying brackets then I suggest that you do it recursively by multiplying one bracket at a time, for which you could write a member function of your original polynomial class; then:
(x-c) * (N^th order polynomial) = (N+1)^th-order polynomial
Say,
(x-c) * (a₀ + a₁x + ... a_Nx^N) = b₀ + b₁x + b₂x² + ... b_N+1x^N+1
where, by considering the ith term,
b_i=a_i-1-ca_i (in a for() loop on i)

(I have not included this is not in my code here.)

#include <iostream>
#include <sstream>
#include <string>
#include <cstdlib>
#include <cmath>
using namespace std;


class Poly
{
private:
   double *a;
   int N;
public:
   Poly( int n, double *coeff );
   ~Poly();
   double evaluate( double x );
   string toString();
};

Poly::Poly( int n, double *coeff )
{
   N = n;
   a = new double[N+1];
   a = coeff;
}


Poly::~Poly()
{
   delete [] a;
}


double Poly::evaluate( double x )
{
   double value = a[N];
   for ( int i = N - 1; i >= 0; i-- ) value = a[i] + x * value;
   return value;
}


string Poly::toString()
{
   stringstream ss;
   string before;
   bool first = true;

   for ( int i = 0; i <= N; i++ ) 
   {
      if ( a[i] != 0.0 )
      {
         before = " + ";
         if ( first )
         {
            if ( a[i] < 0.0 ) before = "-";
            else              before = "";
         }
         else if ( a[i] < 0.0 ) before = " - ";

         ss << before << abs( a[i] );
         if ( i > 0 ) ss << " * x^" << i;

         first = false;
      }
   }
   return ss.str();
}


//======================================================================


class ProdPoly
{
private:
   double *a;
   int N;
public:
   ProdPoly( int n, double *coeff );
   ~ProdPoly();
   double evaluate( double x );
   string toString();
};

ProdPoly::ProdPoly( int n, double *coeff )
{
   N = n;
   a = new double[N+1];
   a = coeff;
}


ProdPoly::~ProdPoly()
{
   delete [] a;
}


double ProdPoly::evaluate( double x )
{
   double value = 1.0;
   for ( int i = 0; i <= N; i++ ) value *= ( x - a[i] );
   return value;
}


string ProdPoly::toString()
{
   stringstream ss;
   string before;
   for ( int i = 0; i <= N; i++ ) 
   {
      before = "-";   if ( a[i] < 0.0 ) before = "+";
      ss << "(x" << before << abs( a[i] ) << ")";
   }
   return ss.str();
}


//======================================================================


int main()
{
   int N = 4;
   double a[] = { 1.0, 2.0, 3.0, 0.0, 1.0 };

   Poly p( N, a );

   cout << p.evaluate( 2.0 ) << endl;
   cout << p.toString() << endl;


   ProdPoly pp( N, a );

   cout << pp.evaluate( 5.0 ) << endl;
   cout << pp.toString() << endl;
}

[WilliamMorris]

ok thanks, I will try my best , if I will not be able to do this code until friday, I will write here my bad code :D, but I hope I can solve it now :D