# Polynomial long division in C++

I needed a function to perform polynomial division in C++.

The polynomials are stored in vector< int >: a polynomial is represented by the vector

Input of the function:

• vector< int >& iNumerator : the dividend (paramater by reference!)
• const vector< int >& iDenominator : the divisor

Output:

• If iNumerator is divisible by iDenominator, the function returns true and the division is performed (and iNumerator contains the quotient)
• If iNumerator is not divisble by iDenominator, the function returns false and iNumerator does not change

This piece of code will be part of the package CIVA (CoxIter + Vino).

The code:

/*!	\fn dividePolynomialByPolynomial
* 	\brief Try to make a division
*
* 	\param iNumerator( vector< Type >& ) The dividend ; updated if the remainder is 0
* 	\param iDenominator( const vector< Type > ) The divisor
* 	\return bool: True if iNumerator is divisible by iDenominator. In this case, iNumerator is updated to the quotient
*/
template <typename Type>
bool dividePolynomialByPolynomial( vector< Type >& iNumerator, const vector< Type >& iDenominator )
{
unsigned int dN( iNumerator.size( ) - 1 ), dD( iDenominator.size( ) - 1 );

if( dN < dD || ( dD == 0 && iDenominator != 0 ) )
return false;

vector< Type > iWorking( iNumerator ), iQuotient;

unsigned int i;
Type iTemp;

while( dN >= dD )
{
if( iWorking[ dN ] % iDenominator[ dD ] != 0 )
return false;

iTemp = iWorking[ dN ] / iDenominator[ dD ];
iQuotient.insert( iQuotient.begin( ), iTemp );

for( i = 0; i <= dD; i++ ) 			iWorking[dN - i] -= iTemp * iDenominator[dD - i]; 		 		dN--; 		 		while( iWorking[ dN ] == 0 && dN >= 1 && dN >= dD )
{
iQuotient.insert( iQuotient.begin( ), 0 );
dN--;
}
}

for( i = 0; i <= dN; i++ )
{
if( iWorking[i] != 0 )
return false;
}

iNumerator = iQuotient;

return true;
}


Publié

dans

par

Étiquettes :