Polynomial division with rest

[rechim]

I have a project for school and I don't know how to implement Polynomial division with rest(operator / )
Please help sith function "Polinom Polinom::operator /(Polinom & x)"

For example :
2*x^5 + x^4 - 5*x^3 - 8*x +1 / x^2 - 3 = 2*x^3 + x^2 + x + 3 rest -5*x + 10

I know to solve it mathematical, but I don't know how to put it to code.
Please a little help? Thank you!

Polinom.h

#ifndef Polinom_h
#define Polinom_h

class Polinom 
{
	int grad; 
	int *coef;
public :
	Polinom(int g=0); //constructor implicit
	~Polinom (); // destructor implicit
	Polinom (int , int *); //constructor
	Polinom ( const Polinom&);//constructor de copiere

	void afisare (char * ); // afisarea unui polinom   OUTPUT FOR POLYNOM
	int valPolinom (int); // valoarea unui polinom intr-un punct

	Polinom operator + ( Polinom &);// adunarea polinoamelor
	Polinom operator = ( Polinom &);// atribuirea polinoamelor
	Polinom operator - ( Polinom &);// scaderea polinoamelor
	Polinom operator * ( Polinom &);// inmultirea polinoamelor
	Polinom operator / ( Polinom &);// division HERE IS WHERE I NEED HELP D/I = C + R  (D = C * I + R)
};
#endif 

Polinom.cpp

#include <iostream>
#include "polinom.h"
using namespace std;

Polinom::Polinom(int g)
{
	grad = g;
	coef = new int[g+1];
	for (int i=0; i<=g; i++) coef[i]=0;
}

Polinom::~Polinom()
{
	if (coef) delete []coef;
}

Polinom::Polinom(int g , int *c)
{
	grad=g ;
	coef = new int[g + 1]; 
	for( int i=0 ; i <= g ; i++) coef[i] = c[i];
}

Polinom::Polinom(const Polinom& P)
{
	grad = P.grad;
	coef = new int [grad+1];
	for (int i = 0 ; i <= grad ; i++) coef[i] = P.coef[i];
}

void Polinom::afisare(char *sir)
{
	cout << sir;
	for (int i = grad ; i >= 0 ; i--)
	{
		if (i == 1)
		{
			if (coef[i] > 0) cout << "+ " << coef[i] << "x";
			else if (coef[i] < 0)cout << " " << coef[i] << "x";
		}
		else
			if (i == 0)
			{
				if (coef[i] > 0) cout << "+ " << coef[i];
				else if (coef[i] < 0) cout << " " << coef[i];
			}
			else
				if (coef[i] > 0) cout << "+ " << coef[i] << "x^" << i;
				else	
					if (coef[i] < 0) cout << " " << coef[i] << "x^" << i;
	}
	cout << "\n";
}

int Polinom::valPolinom (int x) 
{
	int val = 0;
	int x0=1;
	for ( int i = 0 ; i <= grad ; i++)
	{
		val += x0 * coef[i];
		x0 *= x;
	}
	return val;
}

Polinom Polinom::operator + (Polinom& X)
{
	int gmic = grad < X.grad ? grad : X.grad;
	int gmare = grad > X.grad ? grad : X.grad;
	Polinom s(gmare);
	for ( int i = 0 ; i <= gmic ; i++ ) s.coef[i] = coef[i]+X.coef[i];
	for ( int i = gmic+1 ; i <= gmare ; i++ ) s.coef[i] = coef[i];
	return s;
}

Polinom Polinom::operator - (Polinom& X)
{
	int gmic = grad < X.grad ? grad : X.grad;
	int gmare = grad > X.grad ? grad : X.grad;
	Polinom s(gmare);
	for ( int i = 0 ; i <= gmic ; i++ ) s.coef[i] = coef[i]-X.coef[i];
	for ( int i = gmic+1 ; i <= gmare ; i++ ) s.coef[i] = coef[i];
	return s;
}

Polinom Polinom::operator = (Polinom& X)
{
	delete []coef;
	grad = X.grad;
	coef = new int[grad+1];
	for(int i=0;i<=grad;i++) coef[i]=X.coef[i];
	return *this;
}

Polinom Polinom::operator *(Polinom & x)
{
	Polinom s(grad+x.grad);
	Polinom rez(grad+x.grad);
	for(int i=0; i<=grad;i++)
	{
		for(int j=0;j<=x.grad;j++) s.coef[i+j]=coef[i]*x.coef[j];
		for(int k=0; k<= rez.grad; k++)	rez.coef[k] = rez.coef[k] + s.coef[k];
		for(int l=0; l<= s.grad; l++) s.coef[l]=0;
	}
	return rez;
}

Polinom Polinom::operator /(Polinom & x)//HERE IS WHERE I NEED HELP
{
	//............
}

Test.cpp

#include <iostream>
#include <conio.h>
#include "polinom.h"
using namespace std;

int main ()
{
	int x;
	cout << "Dati punctul in care se calculeaza valoarea polinoamelor : ";cin >> x;
	int a[] = {6,-11,9,6,-7,-1,3,2};
	int grad = 7;
	Polinom A(grad,a);
	A.afisare("A = ");
	cout << "\n";
	cout << "A("<<x<<") = " << A.valPolinom(x);
	cout << "\n";
	_getch();

	int b[] = {0,5,0,-3,13};
	grad = 4;
	Polinom B(grad,b);
	B.afisare("B = ");
	cout << "\n";
	cout << "B("<<x<<") = " << B.valPolinom(x);
	cout << "\n";
	_getch();

	Polinom C(A+B);
	C.afisare("A+B = ");
	cout << "\n";
	_getch();

	C=A-B;
	C.afisare("A-B = ");
	cout << "\n";
	_getch();

	int c[] = {3,-2,0,0,2};
	grad = 4;
	Polinom D(grad,c);
	D.afisare("D = ");
	cout << "\n";
	_getch();

	int d[] = {4,1,-5,6};
	grad = 3;
	Polinom E(grad,d);
	E.afisare("E = ");
	cout << "\n";
	_getch();

	Polinom F(E*D);
	F.afisare("D*E = ");
	cout << "\n";
	_getch();
	
	int m[] = {1,-8,-5,1,2};
	grad = 5;
	Polinom M(grad,m);
	M.afisare("M = ");
	cout << "\n";
	_getch();

	int n[] = {-3,0,1};
	grad = 2;
	Polinom N(grad,n);
	N.afisare("N = ");
	cout << "\n";
	_getch();

	Polinom P(M/N);//IN THIS PLACE I NEED HELP WITH OPERATOR /
	P.afisare("M/N = ");
	cout << "\n";
	_getch();

	return 0;
}

[webJose]

Your design of the polynomial class (according to Spanish-to-English translation by diccionarios.com, that's the correct word) cannot possibly accommodate the result of dividing two polynomial objects. You need to re-design it.

I would have started with a monomial class, and then I would have constructed the polynomial class as a collection of monomials. But this barely has any impact on the design in regards to division. The real tool you need here is a polynomial root-finder algorithm. In order to divide two polynomials, you need to find all the roots for the dividend and divisor. If they have roots in common, you can simplify.

So, I would have had a monomial class, then a polynomial class as a collection of monomials, then a polypolynomial class that would probably be a collection of polynomials.

[D80DSL3A]

@webJose Why is division impossible with his design? Is it because the coefficients are integers?
I could see that being a reason.

I have a polynomial class designed similarly with a divide() which works fine, but then my coefficients are doubles. This function simply implements the same long division method that works by hand.
Root finding is not necessary.

I don't have an operator/ because 2 polynomials result, the quotient and the remainder which both need to be found. A single operator wouldn't suffice for this.

[rechim]

@ fun2code hmmm take for consideration my example before the code i've posted. practicly, that's what i need to do. it's not big deal.. it's harder when u try to code it.

i was told by professor to use integers for simplifying the problem.

sorry my bad english.

@fun2code can u post the algorithm even if it's with doubles and without operator / ? it might help me. ty

[webJose]

LOL! I had forgotten about polynomial long division. It's been sooo long since I saw this. But still, his/her class cannot hold the result because it cannot contain two polynomials simultaneously.

[rechim]

hmmm but if i return R to main and cout << C directly from operator / ?

[webJose]

Your polynomial class can only describe polynomials of the form a_nxⁿ + a_n-1x^n-1 + ... + a₀. The result of a long division is composed by 3 polynomials: Quotient, remainder and divisor, each of them of the form described above. You need a single class that can hold those at the same time.

[ne555]

Just implement two operators, divide and modulus. However you obtain the other when calculate so a method that returns both will be better (return a pair or polynomials).
Like with integer division and module.

@rechim: at least you could give it a shot. Think in how do you do the division by hand. (division of numbers)

[rechim]

hmmm but it can be possible even with my class that hold one polynom once a time taking in consideration rulles of long division.

i return only C to the main programm, and taking in consideration the mathematical theory i can calculate rest in test.

so if i do D/I this return C
R = D - C*I

operator * works
operator - works

but the implementation of all that stuff it's harder

[rechim]

ne555 (1349) Jun 16, 2011 at 4:44am
Just implement two operators, divide and modulus. However you obtain the other when calculate so a method that returns both will be better (return a pair or polynomials).
Like with integer division and module.

@rechim: at least you could give it a shot. Think in how do you do the division by hand. (division of numbers)

I stand at computer with the division in front of me writed down on paper.i've tryed and coded like 15 times before posting this here.

[webJose]

Well, like I said, I would have taken the route of several classes, not just one: Monomial class, Polynomial class that is composed of a series of monomials (using a collection like std::vector<> or similar), and one more class that can hold either the result of the long division, or something more generic.

You could still create one more class (PolyDivisionResult) with methods that return the quotient, the remainder and the divisor. That would be the simplest approach towards resolution, I would say.

EDIT: And I like your approach towards obtainin the remainder. And yes, I think returning just the quotient from operator/ is an option, but then you need to calculate the remainder, which is not a problem for you because you can do it with operator- and operator* that are working already, BUT it takes processor time. Big applications would not appreciate it.

[rechim]

@webJose it's first year in college... until i get to develop large scale applications i'll learn more.

[ne555]

Although a rational class could be interesting, it is not necessary now. You are not asking for exact division but for the remainder.
A/B = C + R/B you know what the divisor is, there is no need to returned it from the function.

@rechim: your implementation is empty. ¿what is giving you trouble? ¿what was the problem with those tries? ¿did they crash / compile / draw ducks ?

@webJose: Instead of a collection of monomials (¿multiply them?), it could store its roots or its coefficients.

[D80DSL3A]

I can't simply give the function as this is a homework problem. I can try to describe how it works though and will be happy to help.

Here is the function prototype, so it will make sense what is being done:
void Polynomial::divide(const Polynomial &Divisor, Polynomial &q, Polynomial &r)

Here, the polynomials q (quotient) and r (remainder) are passed to the function so they can be assigned by it.
It could be called in main() like so:

Polynomial Pnum( ... );// the numerator
Polynomial Pden( ... );// the denominator (or divisor)
Polynomial Pq, Pr;// the quotient and remainder

// function call
Pnum.divide( Pden, Pq, Pr );// Pq and Pr will contain the results. 

This function could easily be used to make the 2 operators (/ and %) from:

Polynomial operator/(const Polynomial& Pden}
{
      Polynomial Pq, Pr;
      this->divide( Pden, Pq, Pr );
      return Pq;
}

Similarly for the % operator.

I saw that the discussion here is ongoing so I thought I'd post to say I'm working on an explanation of the functions operation.
Here's a start:

Within the function:
1) r is initially a copy of the Divisor numerator. This is what will be subtracted from as each term in q is found. ie. r = *this;

2) Prepare the quotient q. You can see on paper that the # of terms in q = Pnum.Nterms - Pden.Nterms + 1
Allocate an array of this size for q (here Nterms = 1 + order of poly)

3) Local variable Polynomial trial(Divisor); is used as what will be subtracted from r as each term of q is found.

4) Local variable: double DleadCoeff = Divisors leading coefficient. This constant is used to find each term of q.

More to follow...
EDIT: correction to step 1

[rechim]

so i have for example

2*x^5 + x^4 - 5*x^3 - 8*x +1 / x^2 - 3 = 2*x^3 + x^2 + x + 3 rest -5*x + 10

i writed down dome diagrams on paper :

i 0 1 2 3 4 5
D 1 -8 0 -5 1 2
Aux1 0 0 0 -6 0 2
R1 1 -8 0 1 1 0
Aux2 0 0 -3 0 1
R2 1 -8 3 1 0
Aux3 0 -3 0 1
R3 1 -5 3 0
Aux4 -9 0 3
R4 10 -5 0

0 1 2 3
C 3 1 1 2

So step 1 from top to bottom
D(5)/ I(3) = C(3)
Aux(1) = C(3)*I
D-Aux1 = R1
R1(4)/I(3) = C(2)
Aux2 = C(2)*I
R1-Aux2=R2
[....]
and so on

this are an.....a0
C[]={3,1,1,2} coef for C
R4[]={10,-5} coef for R

how do i code it?

[rechim]

@fun2code ty . i think that will resolve the singural caracter of class

EDIT : those 4 steps you talk about are simple to say, but hard to code (from my vision) I know the rules for division for 2 polynoms, but don't know how to implement it

LATER EDIT : http://www.sosmath.com/algebra/factor/fac01/fac01.html - mathematical algorithm it's imple to understand

[D80DSL3A]

Yes, it's a bit tricky. That link leads to a nice clear explanation of the process.

After those 4 steps comes the loop in which the division is carried out. I will give that code, see if you can figure out how to adapt it for your problem:

for(int i = q.Nterms-1; i >= 0; i--)// for each term in quotient (from highest to lowest, like on paper)
{
	q.pCoeffs[i] = r.pCoeffs[r.Nterms-1]/DleadCoeff;// quotient term found ( C )
	trial = Divisor;
	trial *= q.pCoeffs[i];// trial multiplied by the quotient term just found above. ( Aux )
	r.Nterms--;// remainder shrinks by 1 term
	for(int j=0; j< trial.Nterms-1; j++)// find next remainder ( R -= Aux )
		r.pCoeffs[i+j] -= trial.pCoeffs[j];// only the leading terms of remainder are affected
}

This loop leaves r as the final remainder and all terms of q have been found so that's the end of the function!

EDIT: In terms of your class quantities: Nterms = grad+1 and pCoeffs = coef

[rechim]

fun2code (535) Jun 16, 2011 at 6:29am
Yes, it's a bit tricky.

After those 4 steps comes the loop in which the division is carried out. I will give that code, see if you can figure out how to adapt it for your problem:


for(int i = q.Nterms-1; i >= 0; i--)// for each term in quotient (from highest to lowest, like on paper)
{
q.pCoeffs[i] = r.pCoeffs[r.Nterms-1]/DleadCoeff;// quotient term found
trial = Divisor;
trial *= q.pCoeffs[i];// trial multiplied by the quotient term just found above.
r.Nterms--;// remainder shrinks by 1 term
for(int j=0; j< trial.Nterms-1; j++)// find next remainder
r.pCoeffs[i+j] -= trial.pCoeffs[j];// only the leading terms of remainder are affected
}


This loop leaves r as the final remainder and all terms of q have been found so that's the end of the function!

i have some questions about it:
q.Nterms = length ?
DleadCoeff = divisor coeff for higher power?


EDIT : the code it's for this function right?( void Polynomial::divide(const Polynomial &Divisor, Polynomial &q, Polynomial &r) )

And it's directly this for? no others variables or code lines above?
If i see the complete function void Polynomial::divide(...) maybe i know how to adapt it :)

[D80DSL3A]

Yes there is code above. That code is described in my steps 1-4 in previous post.

q.Nterms = length ?

Yes. See step 2

DleadCoeff = divisor coeff for higher power?

Yes. divisors lead coeff (highest power) See step 4

That is the code from the function following the setup of local variables I described earlier.
I added to the code comments a bit to try and clarify what each line is doing.
It's doing exactly what you described with:

C(2) = R1(4)/I(3)
Aux2 = C(2)*I
R2 = R1-Aux2
[....]
and so on

The only other code above that loop is to handle the special case when the divisor is higher order than the numerator. In this case q = 0 and r = numerator

[rechim]

ok.Thank you! i'll try to put them to place. I'll post the solution when it's ready