Main page

---

PolySolver.cpp

Go to the documentation of this file.

// MathCore = a WYSIWYG equation editor + a powerful math engine     //
// Copyright (C) 2003 by Francesco Montorsi                          //
//                                                                   //
// This library is free software; you can redistribute it and/or     //
// modify it under the terms of the GNU Lesser General Public        //
// License as published by the Free Software Foundation; either      //
// version 2.1 of the License, or (at your option) any later         //
// version.                                                          //
//                                                                   //
// This library is distributed in the hope that it will be useful,   //
// but WITHOUT ANY WARRANTY; without even the implied warranty of    //
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the      //
// GNU Lesser General Public License for more details.               //
//                                                                   //
// You should have received a copy of the GNU Lesser General Public  //
// License along with this program; if not, write to the Free        //
// Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,   //
// MA 02111-1307, USA.                                               //
//                                                                   //
// For any comment, suggestion or feature request, please contact    //
// the administrator of the project at frm@users.sourceforge.net     //
//                                                                   //



// optimization for GCC compiler
#ifdef __GNUG__
#pragma implementation "PolySolver.h"
#endif

// includes
#include "mc/mcprec.h"
#ifdef __BORLANDC__
    #pragma hdrstop
#endif

#ifndef mcPRECOMP
/* #include "mc/PolySolver.h"
 #include "mc/MathAndSystem.h"
 #include "mc/MathOrSystem.h"
 #include "mc/MathLine.h"
 #include "mc/Monomial.h"
 #include "mc/Polynomial.h"
 #include "mc/Fraction.h"
 #include "mc/Radical.h"
 #include "mc/Number.h"
 #include "mc/Symbol.h"
 #include "mc/Bracket.h" */
 #include "mc/mc.h"
#endif




 // a little useful macro
#define mcPOLYSOLVLOG(x)  mcMATHLOG(wxT("mcPolySolver::SolveLineFirstDegree [") + \
         steps.data_GetLast()->io_GetInlinedExpr() + wxT("] - ") x);




// ----------------------------------------
// mcPOLYSOLVER
// ----------------------------------------

mcPolySolver::mcPolySolver()
{
 m_strName = wxT("Polynomial equation solver");
 m_strDesc = 
  wxT("Solves polynomial equations of first degree, ")
  wxT("trying to do the minimum possible number ")
  wxT("of operations.");
 m_nType = mcST_POLYNOMIAL;  
 
 math_ResetCoeffArr();
}

void mcPolySolver::math_ResetCoeffArr()
{
 for (int i=0; i < mcPOLYSOLVER_MAXDEGREE; i++)
  m_pCoeff[i] = mcEmptyElement;
}

void mcPolySolver::math_DeleteCoeffArr()
{
 math_ResetCoeffArr();
 //for (int i=0; i < mcPOLYSOLVER_MAXDEGREE; i++)
  //mcSAFE_DELETE(m_pCoeff[i]);
}

bool mcPolySolver::math_WorksOn(const mcMathOrSystem &m) const
{
 if (m.math_GetMathSystemType().m_tMath1 != mcMSTL1_EQUATIONS)
  return FALSE;

 mcMathType type = m.math_GetMathType();
 if (type.m_tMath1 != mcMTL1_POLYNOMIAL || 
  type.m_tMath2 != mcMTL2_ALGEBRAIC)
  return FALSE;

 // mcPolySolver accepts both parametric and 
 // non-parametric linear systems...
 return TRUE;
}

bool mcPolySolver::math_SolveLine(mcMathLine &p, const mcSymbolProperties *unk,
         mcSystemStepArray &steps)
{
 // no unknowns set by mcSolver::math_PreSolve ?
 mcASSERT(unk != NULL, wxT("we need the main unknown !!"));
 mcLOG(wxT("mcPolySolver:math_SolveLine - The unknown is [%s]."), mcTXTP(unk));

 // first of all, detect the degree of the given line
 mcMATHLOG(wxT("mcPolySolver::SolveLine - I'm detecting the equation degree..."));

 mcIntegerValue degree = p.math_GetMaxDegreeFor(unk);
 if (!degree.isValid() || degree < 0) {
  m_strLastErr = wxT("Cannot retrieve the maximum degree for ") + unk->io_GetInlinedSym();
  return FALSE;
 }

 if (degree > mcPOLYSOLVER_MAXDEGREE) {
  m_strLastErr = wxT("Cannot solve an equation with degree > 10 for the unknown ") + 
      unk->io_GetInlinedSym();
  return FALSE;
 }

 // is this a constant expression ?
 mcASSERT(degree != 0, wxT("The mcPolySolver::math_WorksOn should have returned FALSE !!"));

 // ok, we are ready to start !
 mcMATHLOG(wxT("mcPolySolver::math_SolveLine - The line [%s] has degree [%d] for [%s]."),
    mcTXT(p), degree.GetInt(), mcTXTP(unk));

 bool res = TRUE;
 switch (degree.GetInt()) {
 case 1:
  res = math_SolveLineFirstDegree(p, unk, steps);   
  break;

 case 2:
  res = math_SolveLineSecondDegree(p, unk, steps);
  break;
 }
 
 // cleanup
 math_DeleteCoeffArr();
 steps.data_Check();

 // TRUE if we managed to solve the data...
 return res;
}

void mcPolySolver::math_FindPolyCoeff(const mcMathLine &equ, const mcSymbolProperties *unk, 
           int degree)
{
 // be sure coeff arr is clean
 math_DeleteCoeffArr();

 // search in the left member
 for (int i=0; i < degree; i++) {

  // this works only on the left member...
  m_pCoeff[i] = equ.data_GetLeftMem().math_GetCoeffOf(unk, i);
 }
}

void mcPolySolver::math_GetPolyCoeff(mcMathLine &curr,
          const mcSymbolProperties *unk,
          mcSystemStepArray &steps)
{
 //mcMathMng *curr = math_GetNewStep(p);
 curr.data_Check();

 // STEP #1: move undesidered symbols to the right member
 //          and desired ones to the left
 mcMATHLOG(wxT("mcPolySolver::math_GetPolyCoeff - moving symbols"));
 /*curr.math_MoveNonSymbol(FALSE);
 curr.math_MoveParameters(FALSE);
 curr.math_MoveConstants(FALSE);*/
 curr.math_MoveFreeFrom(unk, FALSE);
 curr.math_MoveSymbol(unk, TRUE);
 steps.data_AddLine(curr);

 // STEP #2: simplify the data...
 mcPOLYSOLVLOG(wxT("simplifying"));
 math_DoCompleteSimplification(mcEXPSIM_NOFLAGS, mcEXPSIM_NOFLAGS, curr, steps); 
 
 // STEP #3: move symbols again
 mcPOLYSOLVLOG(wxT("moving symbols again"));
 //curr = math_GetNewStep(curr);
 curr.math_MoveNonSymbol(FALSE);
 curr.math_MoveParameters(FALSE);
 curr.math_MoveConstants(FALSE);
 curr.math_MoveSymbol(unk, TRUE);
 steps.data_AddLine(curr);

 // STEP #4: simplify the data again...
 mcPOLYSOLVLOG(wxT("simplifying")); 
 math_DoCompleteSimplification(mcEXPSIM_NOFLAGS, mcEXPSIM_NOFLAGS, curr, steps);

 // STEP #5: factorize all the monomials containing the unknown
 mcPOLYSOLVLOG(wxT("factorizing"));
 //curr = math_GetNewStep(curr);
 curr.math_FactoreOut(unk, *mcPolynomialHelpers::smath_pOne, FALSE);
 curr.math_FactoreOutFreeOf(unk, mcEmptyPolynomial, TRUE);
 steps.data_AddLine(curr);

 // STEP #6: simplify the data again...
 mcPOLYSOLVLOG(wxT("simplifying")); 
 math_DoCompleteSimplification(mcEXPSIM_KEEP_FACTORIZATION,mcEXPSIM_KEEP_FACTORIZATION, curr, steps);

 // get copies of the coefficients of the unknown for each degree 
 mcPOLYSOLVLOG(wxT("searching the coefficients of the unknown"));
 math_FindPolyCoeff(curr, unk, 2);
}

bool mcPolySolver::math_SolveLineFirstDegree(mcMathLine &p, 
            const mcSymbolProperties *unk,
            mcSystemStepArray &steps)
{
 // okay; we can start with the real resolution of the given data,
 // storing all the steps in the given array... 
 math_GetPolyCoeff(p, unk, steps);

 if (m_pCoeff[1] == mcEmptyMonomial)
  return TRUE;
 //mcPOLYSOLVLOG(wxT("the coeff #0 is [") + wxString(mcTXT(m_pCoeff[0])) + "]");
 mcPOLYSOLVLOG(wxT("the coeff #1 is [") + wxString(mcTXT(m_pCoeff[1])) + wxT("]"));

 // STEP #6: divide everything by the coefficient of the x (if it's not 1)
 if (!m_pCoeff[1].math_isWrappingOnly(1.0)) {
  //curr = math_GetNewStep(curr);
  p.math_SimpleDivideBy(mcPolynomial(m_pCoeff[1]));
  steps.data_AddLine(p);
 }

 // STEP #7: simplify the data again...
 mcPOLYSOLVLOG(wxT("I'm beginning last steps"));
 math_DoCompleteSimplification(mcEXPSIM_NOFLAGS, mcEXPSIM_NOFLAGS, p, steps);
 steps.data_AddKeyLine(p);

 return TRUE;
}


bool mcPolySolver::math_SolveLineSecondDegree(mcMathLine &curr, 
             const mcSymbolProperties *unk,
             mcSystemStepArray &steps)
{
 //mcMathMng *curr = math_GetNewStep(p);
 curr.data_Check();

 curr.math_FactoreOut(unk, *mcPolynomialHelpers::smath_pOne, FALSE);
 curr.math_FactoreOutFreeOf(unk, mcEmptyPolynomial, TRUE);

 // we need to have the coefficients of the unknown:
 //
 //               a*x^2 + b*x + c
 //
 mcPOLYSOLVLOG(wxT("searching the coefficients of the unknown"));
 math_FindPolyCoeff(curr, unk, 3);
 mcASSERT(m_pCoeff[2] != mcEmptyMonomial, wxT("This is not a 2nd degree equation !"));

 // we will call "a" the coeff of the x^2
 // wxT("b") the coeff of x^1 and "c" the coeff of x^0
 mcMonomial a(m_pCoeff[2]), b(m_pCoeff[1]), c(m_pCoeff[0]);
 mcPOLYSOLVLOG(wxT("the coeff #2 is [") + wxString(mcTXT(a)) + wxT("]"));

 // classify this type of 2nd degree equ
 int type = 3;  // complete by default (a,b,c != 0)
 if (b == mcEmptyMonomial && c == mcEmptyMonomial) type=0;
 if (b == mcEmptyMonomial && c != mcEmptyMonomial) type=1;
 if (b != mcEmptyMonomial && c == mcEmptyMonomial) type=2;

 switch (type) {
 case 0:
  {
   // the equation is in the form    ax^2 = 0
   // (both b and c coefficients does not exist)
   
   // we've got two coincident solutions
   curr.data_GetLeftMem().data_DeleteAll();
   curr.data_GetLeftMem().math_WrapSymbol(unk);
   steps.data_AddKeyLine(curr);

   return TRUE;
  }

 case 1:
  {
   // the equation is in the form    ax^2 + c = 0
   // (the b coefficient does not exist)
   
   // just move c to the right member   
   curr.math_MoveFreeFrom(unk, FALSE);   
   steps.data_AddLine(curr);

   // divide everything by a
   mcPOLYSOLVLOG(wxT("dividing")); 
   curr.math_DivideBy(mcPolynomial(a), NULL);
   steps.data_AddLine(curr);

   // simplify
   mcPOLYSOLVLOG(wxT("simplifying"));
   math_DoCompleteSimplification(mcEXPSIM_NOFLAGS, mcEXPSIM_NOFLAGS, curr, steps);

   // extract the square root
   curr.math_SimpleRaiseTo(mcPolynomial(mcFraction(mcNumber(1), mcNumber(2))));

   // simplify
   mcPOLYSOLVLOG(wxT("simplifying"));
   math_DoCompleteSimplification(mcEXPSIM_NOFLAGS, mcEXPSIM_NOFLAGS, curr, steps);


   // now, extract the roots into two different equations:
   //
   //          x = SQRT(c/a)    OR     x = -SQRT(c/a)
   //
   mcPOLYSOLVLOG(wxT("creating the OR system with the two solutions")); 
   mcPolynomial tmp(curr.data_GetRightMem());
   mcPolynomial left(unk);
   
   //mcMathLine equ1(left, tmp);
   //tmp.math_ChangeAllSigns();
   //mcMathLine equ2((const mcPolynomial &)left, tmp);
   math_SplitInTwoEquations(left, tmp, left, -mcPolynomial(tmp), steps);
   
   // add the final step
   //mcMathOrSystem *last = steps.data_GetLast();
   //steps.data_AddFinalSys(new mcMathOrSystem(equ1, equ2));
   math_DoCompleteSimplification(mcEXPSIM_NOFLAGS, mcEXPSIM_NOFLAGS, curr, steps);

   return TRUE;
  }
  
 case 2:
  {
   // the equation is in the form    ax^2 + bx = 0
   // (the c coefficient does not exist)

   // one solution is always zero...
   curr.math_FactoreOutAll(FALSE);
   mcASSERT(curr.math_isFactorized(), wxT("Something wrong"));
   steps.data_AddLine(curr);

   // remove from curr the "x" factor"
   mcArrayEntry idx = curr.data_GetLeftMem().
    math_GetIndexOf(0, mcMonomial(mcSymbol(unk)), TRUE);
   curr.data_GetLeftMem().math_Remove(
    curr.data_GetLeftMem().math_GetMonomialIdxFromEntry(idx), FALSE);

   // now, we can split the equations in two parts...
   mcMathLine solved(unk, mcRealValue(0.0)); // the solved one (x=0)   
   math_SplitInTwoEquations(solved, curr, steps);
   
   // we'll now proceed with resolution with a step array...
   mcSystemStepArray semisteps1, semisteps2;

   // the first equation is already solved; it is "x=0"
   semisteps1.data_AddLine(solved);
   
   // apply 1st degree solver on the second equation
   mcPOLYSOLVLOG(wxT("final solving of second equation")); 
   if (!math_SolveLineFirstDegree(curr, unk, semisteps2))
    return FALSE;
   mcMATHLOG(wxT("\n\n%s\n\n"), mcTXT(semisteps2));
   
   // now, merge the two step arrays into the original one...
   steps.math_AppendCombinationOf(semisteps1, semisteps2, mcLO_OR);

   return TRUE;
  }
  
 case 3:
  {
   // the equation is in the form    ax^2 + bx + c = 0
   mcPOLYSOLVLOG(wxT("the coeff #1 is [") + wxString(mcTXT(b)) + wxT("]"));
   mcPOLYSOLVLOG(wxT("the coeff #0 is [") + wxString(mcTXT(c)) + wxT("]"));
   
   // STEP #1: multiply by 4a
   mcPOLYSOLVLOG(wxT("multiplying by 4a"));
   mcPolynomial tmp(4);
   tmp *= a;
   curr *= tmp;
   steps.data_AddKeyLine(curr);
   
   // STEP #1b: simplify the data again...
   mcPOLYSOLVLOG(wxT("simplifying"));
   math_DoCompleteSimplification(mcEXPSIM_NOFLAGS,mcEXPSIM_NOFLAGS, curr, steps);
   
   // STEP #2: add & subtract b^2 to the left member
   mcPOLYSOLVLOG(wxT("adding and subtracting b^2"));
   //curr = math_GetNewStep(curr);
   curr.data_GetLeftMem() += mcPolynomial(b)^2;
   curr.data_GetLeftMem() -= mcPolynomial(b)^2;
   steps.data_AddKeyLine(curr);
   
   // STEP #3: pick up as a quadratic binomial the three terms:
   //
   //              4a^2x^2+4abx+b^2 = (2ax+b)^2
   //
   mcPOLYSOLVLOG(wxT("picking up the quadratic"));
   //curr = math_GetNewStep(curr);
   
   mcPolynomial &l = curr.data_GetLeftMem();
   mcSymbol sym((mcSymbolProperties *)unk);
   
   mcArrayEntry idx1 = l.math_GetIndexOf(0, mcMonomial(b)^2, TRUE);
   l.math_Remove(l.math_GetMonomialIdxFromEntry(idx1), TRUE);
   
   mcMonomial square(a^2);
   square *= mcNumber(4);
   square *= mcMonomial(sym^mcPolynomial(mcNumber(2)));
   mcArrayEntry idx2 = l.math_GetIndexOf(0, square, TRUE);
   l.math_Remove(l.math_GetMonomialIdxFromEntry(idx2), TRUE);
   
   mcMonomial product(a*b);
   product *= mcNumber(4);
   product *= sym;
   mcArrayEntry idx3 = l.math_GetIndexOf(0, product, TRUE);
   l.math_Remove(l.math_GetMonomialIdxFromEntry(idx3), TRUE);
   
   // build a bracket containing 2ax+b as contents 
   mcPolynomial contents(2);
   contents *= a;
   contents *= sym;
   contents += b;
   mcBracket br(contents);
   br ^= mcPolynomial(mcNumber(2));  // and 2 as exponent
   curr.math_MoveAll(FALSE);
   curr.data_GetLeftMem() += mcPolynomial(br);
   steps.data_AddKeyLine(curr);
  
   // apply simplification
   mcPOLYSOLVLOG(wxT("simplifying"));
   math_DoCompleteSimplification(mcEXPSIM_KEEP_FACTORIZATION, mcEXPSIM_KEEP_FACTORIZATION, curr, steps);
   
   // STEP #4: extract the square root creating two mcMathLines joined by an OR op:
   // 
   //                             (2ax+b)^2 = b^2 - 4ac
   //
   //               2ax+b = SQRT(b^2 - 4ac)  OR  2ax+b = -SQRT(b^2 - 4ac)
   //
   mcPOLYSOLVLOG(wxT("applying the square root"));
   //curr = math_GetNewStep(curr);
   curr.math_SimpleRaiseTo(mcPolynomial(mcFraction(mcNumber(1), mcNumber(2))));
   
   
   mcMathLine equ1(curr), equ2(curr);
   equ2.data_GetRightMem().math_ChangeAllSigns();
   mcMathOrSystem *step = new mcMathOrSystem();
   
   // *we* must own equ1 and equ2, so give a copy to mcMathOrSystem
   step->data_AddLineToNewAndSystem(new mcMathLine(equ1)); 
   step->data_AddLineToNewAndSystem(new mcMathLine(equ2));
   steps.data_AddSys(step);
   
   // we'll now proceed with resolution with two step array...
   mcSystemStepArray semisteps1, semisteps2;
   
   // apply 1st degree solver on the first equation
   mcPOLYSOLVLOG(wxT("final solving of first equation")); 
   if (!math_SolveLineFirstDegree(equ1, unk, semisteps1))
    return FALSE;
   mcMATHLOG(wxT("\n\n%s\n\n"), mcTXT(semisteps1));
   
   // apply 1st degree solver on the second equation
   mcPOLYSOLVLOG(wxT("final solving of second equation")); 
   if (!math_SolveLineFirstDegree(equ2, unk, semisteps2))
    return FALSE;
   mcMATHLOG(wxT("\n\n%s\n\n"), mcTXT(semisteps2));
   
   // now, merge the two step arrays into the original one...
   steps.math_AppendCombinationOf(semisteps1, semisteps2, mcLO_OR);
   
   // completed !
   return TRUE;
  }
 }

 return TRUE;
}

---

Documentation generated with Doxygen on Sun Feb 6 17:10:48 2005 Visit MathStudio home page for more info

[ Top ]