Polynomial division

[Erasmus]

Hello. Me and my groupmates in programming class are having difficulty in the division operation of 2 single variable polynomials. can anyone help us by giving us an example snippet, or atleast the logic? Here's our work so far:

poly.cpp

#include "poly.h"

//Constructors and Destructors
poly :: poly() {
//default constructor sets degree to 0 and the coeff to 0
degree = 0;
coeff = new double[1];
coeff[degree] = 0.0;
}

poly :: poly(double *c, int d) {
//copy constructor copies c[] to allocated coeff[] and sets degree to d
coeff = new double[d+1];
for(int i=0; i<=d; i++) {
coeff[i] = c[i];
}
degree = d;
}

poly:: ~poly() { // Destructor
delete [] coeff;
}

//Assignment operator
poly& poly :: operator=(const poly &p) {
if(this == &p){
return *this;
} // If the contents of &p is itself return a copy
else {
delete [] coeff;
degree = p.degree;
coeff = new double[degree+1];
for(int i=0; i<=degree; i++){
coeff[i] = p.coeff[i];
}
} // if it is not a copy of its contents, create a new coeff
return *this;
}

//polynomial operations
poly operator+(const poly p,const poly q) {
poly r, a=p, b=q;

if(p.degree > q.degree) {
r.set_degree(a.degree);
b.set_degree(a.degree);
}
else {
r.set_degree(b.degree);
a.set_degree(b.degree);
}

for(int i=0; i<=r.degree; i++){
r.coeff[i] = a.coeff[i] + b.coeff[i];
}
return r; // If the 1st polynomial is larger, take the degree of the 1st as
//argument to set degree of 2nd to match degree of first
}
poly operator-(const poly p,const poly q) {
poly r, a=p, b=q;

if(p.degree > q.degree) {
r.set_degree(a.degree);
b.set_degree(a.degree);
}
else {
r.set_degree(b.degree);
a.set_degree(b.degree);
}

for(int i=0; i<=r.degree; i++){
r.coeff[i] = a.coeff[i] - b.coeff[i];
}
return r; // If the 1st polynomial is larger, take the degree of the 1st as
//argument to set degree of 2nd to match degree of first
}
poly operator*(const poly p,const poly q) {
poly r;
r.set_degree(p.degree + q.degree); // add both polynomials
for(int i=0; i<=p.degree; i++) {
for(int j=0; j<=q.degree; j++) {
r.coeff[i+j] = p.coeff[i] * q.coeff[j] + r.coeff[i+j];
}
}
return r; // let i = p and j = q, each iteration of i represents a
// multiplication of all terms in poly 1 with the 1st term of poly 2, which is
//represented by j iterations.
}

/*
poly operator/(const poly p,const poly q) {
poly r; //result
int rdeg = p.degree-q.degree; //degree of result
r.set_degree(rdeg+1);

poly a=p, b=q;



return r;
}
poly operator%(const poly p,const poly q) {
poly r;
return r;
}
*/

[jsmith]

You have to think about how to do long division of polynomials, and then implement that algorithm.

Given: a = 2x^3 + 5x^2 - x - 4 and b = x - 1, then a / b is performed as follows:


Step 1:

2x^2
____________________
x - 1 / 2x^3 + 5x^2 - x - 4
- ( 2x^3 - 2x^2 )
--------------
7x^2

Step 2:


2x^2 + 7x
____________________
x - 1 / 2x^3 + 5x^2 - x - 4
- ( 2x^3 - 2x^2 )
--------------
7x^2 - x
- ( 7x^2 - 7x )
-------------
6x


Step 3:


2x^2 + 7x + 6
____________________
x - 1 / 2x^3 + 5x^2 - x - 4
- ( 2x^3 - 2x^2 )
--------------
7x^2 - x
- ( 7x^2 - 7x )
-------------
6x - 4
- ( 6x - 6 )
----------
2


Quotient = 2x^2 + 7x + 6
Remainder = 2



EDIT: so to do this, you need to be able to multiply polynomials and subtract them.

[smilodon]

You can always do this using deconvolution.

[QWERTYman]

Synthetic division.

http://www.wtamu.edu/academic/anns/mps/math/mathlab/col_algebra/col_alg_tut37_syndiv.htm