Content
- 1. Realization
- 2. Conclusion
As you know, the solution of the cubic equation has been known since the 16th century. However, even today, engineers can face a problem in solving it. This complexity is due to the need to extract the root from complex numbers. The most convenient solution is the Vieta trigonometric formula , which is much less known compared to Cardano's formula. To draw attention to the topic, I wrote a small library in C ++ .
Realization
The library contains 3 families of classes: polynomial equation, polynomial equation roots and polynomial equation root. The classes of reduced equations of the 1st, 2nd and 3rd degrees LinerNormalEquation, QuadraticNormalEquation and CubicNormalEquation are inherited from the AbstractPolynomialEquation common interface. In this example, I limited myself to considering only the given equations. Their main methods roots() - returns a pointer to the class that stores the solution of the equation, root(int n) - returns the n-th root of the equation and value(...) - returns the value of the equation when the given argument is substituted into it. The decomposed() function returns the factorization of the current polynomial. The Fundamental Theorem of Algebra states that any polynomial can be factorized with a degree not exceeding 2. Therefore, an equation of the third degree can be factored either into 3 factors of the first degree, or into 1 of the first and 1 of the second degree.
Interface
class AbstractPolynomialEquation
{
public:
virtual ~AbstractPolynomialEquation() { deleteRoots(); }
virtual int equationType() const = 0;
virtual std::list<double> coefficients() const = 0;
virtual double value( const double &x ) const = 0;
virtual std::complex<double> value( const std::complex<double> &x ) const = 0;
virtual std::complex<double> value( const std::unique_ptr<AbstractPolynomialRoot> &x ) {
if(x->isReal())
return std::complex<double>( value( x->real() ) );
return value( x->toComplex() );
}
virtual const AbstractPolynomialEquationRoots *roots() const = 0;
const std::unique_ptr<AbstractPolynomialRoot> root(int number) const { return roots()->root(number); }
virtual std::list<std::unique_ptr<AbstractPolynomialEquation>> decomposed() const = 0;
virtual bool isNormal() const = 0;
friend std::ostream &operator<< (std::ostream &out, const AbstractPolynomialEquation &equation) {
out << equation.toString() + " = 0.";
return out;
}
protected:
virtual std::string toString() const = 0;
mutable AbstractPolynomialEquationRoots *myroots = nullptr;
void deleteRoots() const {
if(myroots) {
delete myroots;
myroots = nullptr;
}
}
};
Linear Equation
class LinerNormalEquation : public AbstractPolynomialEquation
{
public:
explicit LinerNormalEquation(const double &coef0);
void setCoef0(const double &coef0);
LinerNormalEquation operator+( const double &val );
LinerNormalEquation operator-( const double &val );
LinerNormalEquation operator+( const LinerNormalEquation &eq );
double operator-( const LinerNormalEquation &eq ) const;
virtual int equationType() const override {return LINER;}
virtual std::list<double> coefficients() const override { std::list<double> list; list.push_back( my0 ); list.push_back( 1 ); return list; }
virtual double value( const double &x ) const override { return x + my0; }
virtual std::complex<double> value( const std::complex<double> &x ) const override { return x + my0; }
virtual const AbstractPolynomialEquationRoots *roots() const override;
virtual std::list<std::unique_ptr<AbstractPolynomialEquation>> decomposed() const override;
virtual bool isNormal() const override {return true;}
protected:
virtual std::string toString() const override;
private:
double my0;
};
Implementation
LinerNormalEquation::LinerNormalEquation(const double &coef0)
{
my0 = coef0;
}
void PolynomialEquation::LinerNormalEquation::setCoef0(const double &coef0)
{
my0 = coef0;
deleteRoots();
}
LinerNormalEquation LinerNormalEquation::operator+(const double &val)
{
return LinerNormalEquation( this->my0 + val );
}
LinerNormalEquation LinerNormalEquation::operator-(const double &val)
{
return LinerNormalEquation( this->my0 - val );
}
LinerNormalEquation LinerNormalEquation::operator+(const LinerNormalEquation &eq)
{
return LinerNormalEquation( (this->my0 + eq.my0)/2 );
}
double LinerNormalEquation::operator-(const LinerNormalEquation &eq) const
{
return this->my0 - eq.my0;
}
const AbstractPolynomialEquationRoots *PolynomialEquation::LinerNormalEquation::roots() const
{
if(!myroots)
myroots = new LinerEquationRoot( -my0 );
return myroots;
}
std::list<std::unique_ptr<AbstractPolynomialEquation> > LinerNormalEquation::decomposed() const
{
std::list<std::unique_ptr<AbstractPolynomialEquation> > root;
root.push_back( std::make_unique<LinerNormalEquation>( this->my0 ) );
return root;
}
std::string LinerNormalEquation::toString() const
{
return std::string("x") + ( my0 > 0 ? std::string("+") : std::string() ) + ( my0 == 0 ? std::string() : std::to_string( my0 ) );
}
Quadratic equation
class QuadraticNormalEquation : public AbstractPolynomialEquation
{
public:
QuadraticNormalEquation( double coef1, double coef0);
virtual ~QuadraticNormalEquation() {}
void setCoef0(const double &coef0);
void setCoef1(const double &coef1);
QuadraticNormalEquation operator+( const double &val );
QuadraticNormalEquation operator-( const double &val );
QuadraticNormalEquation operator+( const QuadraticNormalEquation &eq );
QuadraticNormalEquation operator+( const LinerNormalEquation &eq );
QuadraticNormalEquation operator-( const LinerNormalEquation &eq );
double discriminant() const;
virtual int equationType() const override { return QUADRATIC; }
virtual std::list<double> coefficients() const override { std::list<double> list; list.push_back( my0 ); list.push_back( my1 ); list.push_back( 1 ); return list; }
virtual double value( const double &x ) const override { return (x + my1)*x + my0; }
virtual std::complex<double> value( const std::complex<double> &x ) const override { return (x + my1)*x + my0; }
virtual const AbstractPolynomialEquationRoots *roots() const override;
virtual std::list< std::unique_ptr<AbstractPolynomialEquation> > decomposed() const override;
virtual bool isNormal() const override {return true;}
protected:
virtual std::string toString() const override;
private:
double my0;
double my1;
};
Implementation
QuadraticNormalEquation::QuadraticNormalEquation( double coef1, double coef0)
: my0(coef0), my1(coef1)
{
}
void QuadraticNormalEquation::setCoef0(const double &coef0)
{
my0 = coef0;
deleteRoots();
}
void QuadraticNormalEquation::setCoef1(const double &coef1)
{
my1 = coef1;
deleteRoots();
}
QuadraticNormalEquation QuadraticNormalEquation::operator+( const double &val )
{
return QuadraticNormalEquation( this->my1, this->my0 + val );
}
QuadraticNormalEquation QuadraticNormalEquation::operator-( const double &val )
{
return QuadraticNormalEquation( this->my1, this->my0 - val );
}
QuadraticNormalEquation QuadraticNormalEquation::operator+(const QuadraticNormalEquation &eq)
{
return QuadraticNormalEquation( (this->my1+eq.my1)/2, (this->my0+eq.my0)/2 );
}
QuadraticNormalEquation QuadraticNormalEquation::operator-(const LinerNormalEquation &eq)
{
return QuadraticNormalEquation( this->my1 - 1, this->my0 - eq.coefficients().front() );
}
QuadraticNormalEquation QuadraticNormalEquation::operator+(const LinerNormalEquation &eq)
{
return QuadraticNormalEquation( this->my1 + 1, this->my0 + eq.coefficients().front() );
}
double QuadraticNormalEquation::discriminant() const
{
return my1*my1 - 4*my0;
}
const AbstractPolynomialEquationRoots *QuadraticNormalEquation::roots() const
{
if(!myroots) {
auto d = discriminant();
myroots = new QuadraticImageEquationRoots( -my1/2, sqrt(-d)/2 );
}
return myroots;
}
std::list<std::unique_ptr<AbstractPolynomialEquation> > QuadraticNormalEquation::decomposed() const
{
std::list<std::unique_ptr<AbstractPolynomialEquation> > eqs;
if( this->roots()->rootsType() == QUADRAT_REAL ) {
eqs.push_back( std::make_unique<LinerNormalEquation>( -this->roots()->root( 1 )->real() ) );
eqs.push_back( std::make_unique<LinerNormalEquation>( -this->roots()->root( 2 )->real() ) );
}
else if( this->roots()->rootsType() == QUADRAT_IMAGE ) {
eqs.push_back( std::make_unique<QuadraticNormalEquation>( *this ) );
}
return eqs;
}
std::string QuadraticNormalEquation::toString() const
{
return std::string("x^2")
+ ( my1 > 0 ? std::string("+") : std::string("") ) + ( my1==0 ? std::string("") : std::to_string( my1 ) + std::string("*x") )
+ ( my0 > 0 ? std::string("+") : std::string("") ) + ( my0==0 ? std::string("") : std::to_string( my0 ) );
}
cubic equation
class CubicNormalEquation : public AbstractPolynomialEquation
{
public:
CubicNormalEquation(double coef2, double coef1, double coef0);
void setCoef0(const double &coef0);
void setCoef1(const double &coef1);
void setCoef2(const double &coef2);
CubicNormalEquation operator+( const CubicNormalEquation &eq );
CubicNormalEquation operator+( const LinerNormalEquation &eq );
CubicNormalEquation operator-( const LinerNormalEquation &eq );
CubicNormalEquation operator+( const QuadraticNormalEquation &eq );
CubicNormalEquation operator-( const QuadraticNormalEquation &eq );
double discriminant() const;
double qu() const;
double re() const;
double fi() const;
virtual int equationType() const override {return CUBIC;}
virtual std::list<double> coefficients() const override { std::list<double> list; list.push_back( my0 ); list.push_back( my1 ); list.push_back( my2 ); list.push_back( 1 ); return list; }
virtual double value( const double &x ) const override { return ( (x + my2)*x + my1 ) * x + my0; }
virtual std::complex<double> value( const std::complex<double> &x ) const override { return ( (x + my2)*x + my1 ) * x + my0; }
virtual const AbstractPolynomialEquationRoots *roots() const override;
virtual std::list<std::unique_ptr<AbstractPolynomialEquation>> decomposed() const override;
virtual bool isNormal() const override {return true;}
protected:
virtual std::string toString() const override;
private:
double my0;
double my1;
double my2;
};
Implementation
CubicNormalEquation::CubicNormalEquation( double coef2, double coef1, double coef0 )
: my0(coef0), my1(coef1), my2(coef2)
{
}
void CubicNormalEquation::setCoef0(const double &coef0)
{
my0 = coef0;
deleteRoots();
}
void CubicNormalEquation::setCoef1(const double &coef1)
{
my1 = coef1;
deleteRoots();
}
void CubicNormalEquation::setCoef2(const double &coef2)
{
my2 = coef2;
deleteRoots();
}
CubicNormalEquation CubicNormalEquation::operator+(const CubicNormalEquation &eq)
{
return CubicNormalEquation( (this->my2+eq.my2)/2, (this->my1+eq.my1)/2, (this->my0+eq.my0)/2 );
}
CubicNormalEquation CubicNormalEquation::operator+( const LinerNormalEquation &eq )
{
auto coef = eq.coefficients();
return CubicNormalEquation( this->my2, this->my1 + 1, this->my0 + coef.front() );
}
CubicNormalEquation CubicNormalEquation::operator-( const LinerNormalEquation &eq )
{
auto coef = eq.coefficients();
return CubicNormalEquation( this->my2, this->my1 - 1, this->my0 - coef.front() );
}
CubicNormalEquation CubicNormalEquation::operator+( const QuadraticNormalEquation &eq )
{
auto coef = eq.coefficients();
return CubicNormalEquation( this->my2 + 1, this->my1 + *next( coef.begin() ), this->my0 + coef.front() );
}
CubicNormalEquation CubicNormalEquation::operator-( const QuadraticNormalEquation &eq )
{
auto coef = eq.coefficients();
return CubicNormalEquation( this->my2 - 1, this->my1 - *next( coef.begin() ), this->my0 - coef.front() );
}
double CubicNormalEquation::discriminant() const //
{
auto q = qu();
auto r = re();
return q*q*q - r*r;
}
double CubicNormalEquation::qu() const
{
return (my2*my2 - my1*3) / 9;
}
double CubicNormalEquation::re() const
{
return (my2 * (my2*my2*2 - my1*9) + 27*my0) / 54;
}
double CubicNormalEquation::fi() const
{
auto q = qu();
auto q_cub = q*q*q;
auto r = re();
auto s = q*q*q - r*r;
if( s > 0 )
return acos( r/sqrt(q_cub) ) / 3;
else {
if( q > 0 ) {
return acosh( fabs( r )/sqrt( q_cub ) ) / 3;
} else {
return asinh( fabs( r )/sqrt( -q_cub ) ) / 3;
}
}
}
const AbstractPolynomialEquationRoots *CubicNormalEquation::roots() const
{
if(!myroots) {
auto r = re();
auto q = qu();
auto a_3 = my2 / 3;
auto s = q*q*q - r*r;
if(r==0 && q==0) {
auto x1 = - a_3;
myroots = new CubicRealEquationRoots( x1, x1, x1 );
return myroots;
}
if( s == 0 ) {
auto x1 = -2 * cbrt(r) - a_3;
auto x23 = cbrt(r) - a_3;
myroots = new CubicRealEquationRoots( x1, x23, x23 );
return myroots;
}
auto f = fi();
if( s > 0 ) {
auto q_sqrt = sqrt( q );
auto x1 = - 2 * q_sqrt * cos( f ) - a_3;
auto x2 = - 2 * q_sqrt * cos( f + 2.0 * M_PI / 3 ) - a_3;
auto x3 = - 2 * q_sqrt * cos( f - 2.0 * M_PI / 3 ) - a_3;
myroots = new CubicRealEquationRoots( x1, x2, x3 );
} else {
if( q == 0) {
auto x = - cbrt( my0 - a_3*a_3*a_3 ) - a_3;
auto re = -( my2 + x )/2;
auto im = sqrt( fabs( (my2 - 3*x)*(my2 + x) - 4*my1 ) )/2;
myroots = new CubicImageEquationRoots( x, re, im );
return myroots;
}
if( q > 0 ) {
auto q_sqrt = sqrt( q );
auto x = - q_sqrt * 2.0 * sgn(r) * cosh( f ) - a_3;
auto re = q_sqrt * sgn(r) * cosh( f ) - a_3;
auto im = SQRT_3 * q_sqrt * sinh( f );
myroots = new CubicImageEquationRoots( x, re, im );
} else {
auto q_sqrt = sqrt( -q );
auto x = - q_sqrt * 2.0 * sgn(r) * sinh( f ) - a_3;
auto re = q_sqrt * sgn(r) * sinh( f ) - a_3;
auto im = SQRT_3 * q_sqrt * cosh( f );
myroots = new CubicImageEquationRoots( x, re, im );
}
}
}
return myroots;
}
std::list<std::unique_ptr<AbstractPolynomialEquation> > CubicNormalEquation::decomposed() const
{
std::list<std::unique_ptr<AbstractPolynomialEquation> > eqs;
eqs.push_back( std::make_unique<LinerNormalEquation>( -this->roots()->root( 1 )->real() ) );
if( roots()->rootsType() == CUB_REAL ) {
eqs.push_back( std::make_unique<LinerNormalEquation>( -this->roots()->root( 2 )->real() ) );
eqs.push_back( std::make_unique<LinerNormalEquation>( -this->roots()->root( 3 )->real() ) );
}
else if( roots()->rootsType() == CUB_IMAGE ) {
eqs.push_back( std::make_unique<QuadraticNormalEquation>( -2.0*this->roots()->root( 2 )->real(), fabs( this->roots()->root( 2 )->toComplex() ) ) );
}
return eqs;
}
std::string CubicNormalEquation::toString() const
{
return std::string("x^3")
+ ( my2 > 0 ? std::string("+") : std::string() ) + ( my2==0 ? std::string() : ( std::to_string( my2 ) + std::string("*x^2") ) )
+ ( my1 > 0 ? std::string("+") : std::string() ) + ( my1==0 ? std::string() : ( std::to_string( my1 ) + std::string("*x") ) )
+ ( my0 > 0 ? std::string("+") : std::string() ) + ( my0==0 ? std::string() : std::to_string( my0 ) );
}
Solution keeper classes for equations LinerEquationRoot, QuadraticRealEquationRoots, QuadraticImageEquationRoots. CubicRealEquationRoots, CubicImageEquationRoots are inherited from the AbstractPolynomialEquationRoots common interface and are classified in two ways. The first is the degree of the equation, the second is the characteristic of the roots of the equation. A linear equation is a trivial case - it has one real root. Quadratic and cubic equations can have complex roots. Such roots always exist in pairs x 1 = R + i M and x 2 = R – i M. Therefore, they are stored as real and imaginary parts. Real roots are stored as their own values.
Interface
class AbstractPolynomialEquationRoots
{
public:
virtual ~AbstractPolynomialEquationRoots() { /*std::cout << "delete AbstractPolynomialEquationRoots";*/ }
virtual int rootsType() const = 0;
virtual std::unique_ptr<AbstractPolynomialRoot> root(int number) const = 0;
friend std::ostream &operator<< (std::ostream &out, const AbstractPolynomialEquationRoots *root) {
out << root->toString();
return out;
}
protected:
virtual std::string toString() const = 0;
};
Linear Equation Roots
class LinerEquationRoot : public AbstractPolynomialEquationRoots
{
public:
explicit LinerEquationRoot(const double &root);
virtual ~LinerEquationRoot() {}
virtual int rootsType() const override {return LINE;}
virtual std::unique_ptr<AbstractPolynomialRoot> root(int number) const override {
return number == 1 ? std::make_unique<RealPolynomialRoot>(myx1) : nullptr;
}
protected:
virtual std::string toString() const override;
private:
double myx1;
};
Implementation
LinerEquationRoot::LinerEquationRoot(const double &root)
: myx1(root)
{
}
std::string LinerEquationRoot::toString() const
{
return "x = " + std::to_string(myx1) + ".";
}
The roots of a quadratic equation
class QuadraticRealEquationRoots : public AbstractPolynomialEquationRoots
{
public:
QuadraticRealEquationRoots(const double &root1, const double &root2);
virtual ~QuadraticRealEquationRoots() {}
virtual int rootsType() const override {return QUADRAT_REAL;}
virtual std::unique_ptr<AbstractPolynomialRoot> root(int number) const override;
protected:
virtual std::string toString() const override;
private:
double myx1;
double myx2;
};
class QuadraticImageEquationRoots : public AbstractPolynomialEquationRoots
{
public:
QuadraticImageEquationRoots( double real, double image);
virtual ~QuadraticImageEquationRoots() {}
virtual int rootsType() const override {return QUADRAT_IMAGE;}
virtual std::unique_ptr<AbstractPolynomialRoot> root(int number) const override;
protected:
virtual std::string toString() const override;
private:
double myre;
double myim;
};
Implementation
QuadraticRealEquationRoots::QuadraticRealEquationRoots(const double &root1, const double &root2)
: myx1( root1 ), myx2( root2 )
{
}
std::unique_ptr<AbstractPolynomialRoot> QuadraticRealEquationRoots::root(int number) const
{
switch (number) {
case 1:
return std::make_unique<RealPolynomialRoot>(myx1);
case 2:
return std::make_unique<RealPolynomialRoot>(myx2);
default:
return nullptr;
}
}
std::string QuadraticRealEquationRoots::toString() const
{
return "x1 = " + std::to_string( myx1 ) + "; x2 = " + std::to_string( myx2 ) + ".";
}
QuadraticImageEquationRoots::QuadraticImageEquationRoots(double real, double image)
: myre( real ), myim( image )
{
}
std::unique_ptr<AbstractPolynomialRoot> QuadraticImageEquationRoots::root(int number) const
{
switch (number) {
case 1:
return std::make_unique<ImagePolynomialRoot>(myre, myim);
case 2:
return std::make_unique<ImagePolynomialRoot>(myre, -myim);
default:
return nullptr;
}
}
std::string QuadraticImageEquationRoots::toString() const
{
return "x1 = " + std::to_string( myre ) + " + j" + std::to_string( myim )
+ "; x2 = " + std::to_string( myre ) + " - j" + std::to_string( myim ) + ".";
}
The roots of the cubic equation
class CubicRealEquationRoots : public AbstractPolynomialEquationRoots
{
public:
CubicRealEquationRoots(const double &root1, const double &root2, const double &root3);
virtual ~CubicRealEquationRoots() {}
virtual int rootsType() const override {return CUB_REAL;}
virtual std::unique_ptr<AbstractPolynomialRoot> root(int number) const override;
protected:
virtual std::string toString() const override;
private:
double myx1;
double myx2;
double myx3;
};
class CubicImageEquationRoots : public AbstractPolynomialEquationRoots
{
public:
CubicImageEquationRoots(const double &root, const double &real, const double &image);
virtual ~CubicImageEquationRoots() {}
virtual int rootsType() const override {return CUB_IMAGE;}
virtual std::unique_ptr<AbstractPolynomialRoot> root(int number) const override;
protected:
virtual std::string toString() const override;
private:
double myx1;
double myre;
double myim;
};
Implementation
CubicRealEquationRoots::CubicRealEquationRoots(const double &root1, const double &root2, const double &root3)
: myx1( root1 ), myx2( root2 ), myx3( root3 )
{
}
std::unique_ptr<AbstractPolynomialRoot> CubicRealEquationRoots::root(int number) const
{
switch (number) {
case 1:
return std::make_unique<RealPolynomialRoot>(myx1);
case 2:
return std::make_unique<RealPolynomialRoot>(myx2);
case 3:
return std::make_unique<RealPolynomialRoot>(myx3);
default:
return nullptr;
}
}
std::string CubicRealEquationRoots::toString() const
{
return "x1 = " + std::to_string( myx1 )
+ "; x2 = " + std::to_string( myx2 )
+ "; x3 = " + std::to_string( myx3 );
}
CubicImageEquationRoots::CubicImageEquationRoots(const double &root, const double &real, const double &image)
: myx1( root ), myre( real ), myim( image )
{
}
//-----------------------------------------------------------
std::unique_ptr<AbstractPolynomialRoot> CubicImageEquationRoots::root(int number) const
{
switch (number) {
case 1:
return std::make_unique<RealPolynomialRoot>(myx1);
case 2:
return std::make_unique<ImagePolynomialRoot>(myre, myim);
case 3:
return std::make_unique<ImagePolynomialRoot>(myre, -myim);
default:
return nullptr;
}
}
std::string CubicImageEquationRoots::toString() const
{
return "x1 = " + std::to_string( myx1 )
+ "; x2 = " + (myre == 0 ? std::string() : std::to_string( myre ) + std::string(" + ")) + "j" + std::to_string( myim )
+ "; x3 = " + (myre == 0 ? std::string() : std::to_string( myre ) + std::string(" ")) + "- j" + std::to_string( myim )
+ ".";
}
To access the values of the roots, RealPolynomialRoot and ImagePolynomialRoot objects are created, inherited from AbstractPolynomialRoot. The root is returned as a unique_ptr smart pointer
Interface
class AbstractPolynomialRoot
{
public:
virtual std::complex<double> toComplex() const = 0;
virtual double real() const = 0;
virtual double image() const = 0;
virtual bool isReal() const = 0;
};
Real root
class RealPolynomialRoot : public AbstractPolynomialRoot
{
public:
explicit RealPolynomialRoot( const double &x )
: myx(x) {}
virtual std::complex<double> toComplex() const override { return std::complex<double>(myx, 0); }
virtual double real() const override { return myx; }
virtual double image() const override { return 0; }
virtual bool isReal() const override { return true; }
private:
double myx;
};
imaginary root
class ImagePolynomialRoot : public AbstractPolynomialRoot
{
public:
ImagePolynomialRoot( const double &r, const double &i )
: myr(r), myi(i) {}
virtual std::complex<double> toComplex() const override { return std::complex<double>(myr, myi); }
virtual double real() const override { return myr; }
virtual double image() const override { return myi; }
virtual bool isReal() const override { return false; }
private:
double myr, myi;
};
Conclusion
Despite the apparent simplicity, the formulas for solving polynomial equations are very complex expressions. In addition to solving an equation of the third degree, the Ferrari solution for equations of the fourth degree is known. In other cases, numerical methods have to be used. At the same time, special methods are needed to find complex roots. I plan to write future articles on these topics.
