Tag Archives: polynomials

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] != 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;
}

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<...