Polynomial

WilliamMorris (27)
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?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
 
#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 (10692)
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 
1
2
3
4
5
6
7
8
9
10
 
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 (2127)
OP: you can try overloading the ctor (see below) but like ne555 I'm not quite sure what exactly you're trying to do
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
 
#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 (27)
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 (27)
Or at least it should form with brackets
gunnerfunner (2127)
1
2
3
4
5
6
7
8
9
 
(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 (6980)
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 (2127)
lastchance: I had a bet with myself that sooner or later you'd be on this thread ;)
lastchance (6980)
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 (27)
maybe I could use this function on multiplying polynomials?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
 
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 (27)
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.
Last edited on
lastchance (6980)
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 xN 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) * (Nth order polynomial) = (N+1)th-order polynomial
Say,
(x-c) * (a0 + a1x + ... aNxN) = b0 + b1x + b2x2 + ... bN+1xN+1
where, by considering the ith term,
bi=ai-1-cai (in a for() loop on i)

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


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
 
#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 (27)
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
Topic archived. No new replies allowed.