exprrep.h

很多二维 三维几何计算算法 C++ 类库

class AddSubRep : public BinOpRep {
public:
  /// \name Constructors and Destructor
  //@{
  /// constructor
  AddSubRep(ExprRep* f, ExprRep* s) : BinOpRep(f, s) {
    ffVal = Op(first->ffVal, second->ffVal);
  }
  /// destructor
  ~AddSubRep() {}
  //@}

  CORE_MEMORY(AddSubRep)
protected:
  /// compute sign and MSB
  void computeExactFlags();
  /// compute approximation value
  void computeApproxValue(const extLong&, const extLong&);
  /// return operator in string
  const std::string op() const {
    return Operator::name;
  }
private:
  static Operator Op;
};//AddSubRep class

template <class Operator>
Operator AddSubRep<Operator>::Op;

  /// AddSubRep<Op>::computeExactFlags()
  ///     This function is the heart of Expr class,
  ///     and hence the heart of Core Library!
  /// Here is where we use the root bounds.
template <class Operator>
void AddSubRep<Operator>::computeExactFlags() {
  if (!first->flagsComputed())
    first->computeExactFlags();
  if (!second->flagsComputed())
    second->computeExactFlags();

  int sf = first->sign();
  int ss = second->sign();

  if ((sf == 0) && (ss == 0)) { // the node is zero
    reduceToZero();
    return;
  } else if (sf == 0) { // first operand is zero
    reduceTo(second);
    sign() = Op(ss);
    appValue() = Op(appValue());
    if (rationalReduceFlag && ratFlag() > 0)
      *(ratValue()) = Op(*(ratValue()));
    return;
  } else if (ss == 0) { // second operand is zero
    reduceTo(first);
    return;
  }
  // rational node
  if (rationalReduceFlag) {
    if (first->ratFlag() > 0 && second->ratFlag() > 0) {
      BigRat val=Op(*(first->ratValue()), *(second->ratValue()));
      reduceToBigRat(val);
      ratFlag() = first->ratFlag() + second->ratFlag();
      return;
    } else
      ratFlag() = -1;
  }

  // neither operand is zero
  extLong df    = first->d_e();
  extLong ds    = second->d_e();
  // extLong md    = df < ds ? df : ds;
  // extLong l1    = first->length();
  // extLong l2    = second->length();
  extLong m1    = first->measure();
  extLong m2    = second->measure();

  // length() = df * l2 + ds * l1 + d_e() + md;
  measure() = m1 * ds + m2 * df + d_e();

  // BFMSS[2,5] bound.
  v2p() = core_min(first->v2p() + second->v2m(),
		  first->v2m() + second->v2p());
  v2m() = first->v2m() + second->v2m();
  v5p() = core_min(first->v5p() + second->v5m(),
		  first->v5m() + second->v5p());
  v5m() = first->v5m() + second->v5m();

  if (v2p().isInfty() || v5p().isInfty())
    u25() = CORE_INFTY;
  else
    u25() = EXTLONG_ONE + core_max(first->v2p() + second->v2m()
	    - v2p() + ceilLg5(first->v5p() + second->v5m() - v5p())
            + first->u25() + second->l25(),
                                   first->v2m() + second->v2p() - v2p()
            + ceilLg5(first->v5m() + second->v5p() - v5p())
            + first->l25() + second->u25());
  l25() = first->l25() + second->l25();

  lc() = ds * first->lc() + df * second->lc();
  tc() = measure();

  high() = core_max(first->high(),second->high())+EXTLONG_ONE;
  // The following is a subset of the minimization in computeBound().
  low() = core_min(measure(), (d_e()-EXTLONG_ONE)*high() + lc());

  extLong lf = first->lMSB();
  extLong ls = second->lMSB();
  extLong uf = first->uMSB();
  extLong us = second->uMSB();

  extLong l  = core_max(lf, ls);
  extLong u  = core_max(uf, us);

#ifdef CORE_TRACE
  std::cout << "INSIDE Add/sub Rep: " << std::endl;
#endif

  if (Op(sf, ss) != 0) {     // can't possibly cancel out
#ifdef CORE_TRACE
    std::cout << "Add/sub Rep:  Op(sf, ss) non-zero" << std::endl;
#endif

    uMSB() = u + EXTLONG_ONE;
    lMSB() = l;            // lMSB = core_min(lf, ls)+1 better
    sign() = sf;
  } else {               // might cancel out
#ifdef CORE_TRACE
    std::cout << "Add/sub Rep:  Op(sf, ss) zero" << std::endl;
#endif

    uMSB() = u + EXTLONG_ONE;
    uMSB() = u;
    if (lf >= us + EXTLONG_TWO) {// one is at least 1 order of magnitude larger
#ifdef CORE_TRACE
      std::cout << "Add/sub Rep:  Can't cancel" << std::endl;
#endif

      lMSB() = lf - EXTLONG_ONE;     // can't possibly cancel out
      sign() = sf;
    } else if (ls >= uf + EXTLONG_TWO) {
#ifdef CORE_TRACE
      std::cout << "Add/sub Rep:  Can't cancel" << std::endl;
#endif

      lMSB() = ls - EXTLONG_ONE;
      sign() = Op(ss);
    } else if (ffVal.isOK()) {// begin filter computation
#ifdef CORE_TRACE
      std::cout << "Add/sub Rep:  filter used" << std::endl;
#endif
#ifdef CORE_DEBUG_FILTER
      std::cout << "call filter in " << op() << "Rep" << std::endl;
#endif
      sign() = ffVal.sign();
      lMSB() = ffVal.lMSB();
      uMSB() = ffVal.uMSB();
    } else {			// about the same size, might cancel out
#ifdef CORE_TRACE
      std::cout << "Add/sub Rep:  iteration start" << std::endl;
#endif

      extLong lowBound = computeBound();
      /* Zilin 06/11/2003
       * as BFMSS[2] might be a negative number, lowBound can be negative.
       * In this case, we just set it to 1 since we need at least one bit
       * to get the sign.  In the future, we may need to improve this.
       */
      if (lowBound <= EXTLONG_ZERO)
        lowBound = EXTLONG_ONE;

      if (!progressiveEvalFlag) {
        // convert the absolute error requirement "lowBound" to
        // a relative error requirement "ur", s.t.
        //    |x|*2^(-ur) <= 2^(-lowBound).
        // ==> r >= a + lg(x) >= a + (uMSB + 1);
        //	    extLong  rf = lowBound + (uf + 1);
        //	    extLong  rs = lowBound + (us + 1);
        //	    first->approx(rf, CORE_INFTY);
        //	    second->approx(rs, CORE_INFTY);
        // Chen: considering the uMSB is also an approximate bound.
        // we choose to use absolute precision up-front.
        Real newValue = Op(first->getAppValue(CORE_INFTY,
				lowBound + EXTLONG_ONE),
                           second->getAppValue(CORE_INFTY,
				   lowBound + EXTLONG_ONE));
        if (!newValue.isZeroIn()) { // Op(first, second) != 0
          lMSB() = newValue.lMSB();
          uMSB() = newValue.uMSB();   // chen: to get tighers value.
          sign() = newValue.sign();
        } else if (lowBound.isInfty()) {//check if rootbound is too big
          core_error("AddSubRep:root bound has exceeded the maximum size\n \
            but we still cannot decide zero.\n", __FILE__, __LINE__, false);
        } else {               // Op(first, second) == 0
          lMSB() = CORE_negInfty;
          sign() = 0;
        }
      } else {  // else do progressive evaluation
#ifdef CORE_TRACE
        std::cout << "Add/sub Rep:  progressive eval" << std::endl;
#endif
        // Oct 30, 2002: fixed a bug here!  Old versions used relative
        // precision bounds, but one should absolute precision for addition!
        // Moreover, this is much more efficient.

        // ua is the upper bound on the absolute precision in our iteration
	// Chee, Aug 8, 2004: it is important that ua be strictly
	//     larger than lowBound AND the defaultInitialProgressivePrec,
	//     so that we do at least one iteration of the for-loop. So:
	// i is the variable for iteration.
        extLong i = core_min(defInitialProgressivePrec, lowBound.asLong());
        extLong ua = lowBound.asLong() + EXTLONG_ONE;
        //   NOTE: ua is allowed to be CORE_INFTY
	
#ifdef CORE_DEBUG_BOUND
        std::cout << "DebugBound:" << "ua = " << ua << std::endl;
#endif
        // We initially set the lMSB and sign as if the value is zero:
        lMSB() = CORE_negInfty;
        sign() = 0;

        EscapePrecFlag = 0;	// reset the Escape Flag

        // Now we try to determine the real lMSB and sign,
        // in case it is not really zero:
#ifdef CORE_TRACE
        std::cout << "Upper bound (ua) for iteration is " << ua << std::endl;
	std::cout << "Starting iteration at i = " << i << std::endl;
#endif

        for ( ; i<ua; i*=EXTLONG_TWO) {
          // relative bits = i
	  //
	  // PROBLEM WITH NEXT LINE: you must ensure that
	  // first and second are represented by BigFloats...
	  //
          Real newValue = Op(first->getAppValue(CORE_INFTY, i),
                             second->getAppValue(CORE_INFTY, i));

#ifdef CORE_TRACE
	  if (newValue.getRep().ID() == REAL_BIGFLOAT) 
	  std::cout << "BigFloat! newValue->rep->ID() = "
		  << newValue.getRep().ID() << std::endl;
	  else 
	  std::cout << "ERROR, Not BigFloat! newValue->rep->ID() ="
		  << newValue.getRep().ID() << std::endl;
	  std::cout << "newValue = Op(first,second) = "
		  << newValue << std::endl;
	  std::cout << "first:appVal, appComputed, knownPrec, sign ="
		  << first->appValue() << ","
		  << first->appComputed() << ","
		  << first->knownPrecision() << ","
		  << first->sign() << std::endl;
	  std::cout << "second:appVal, appComputed, knownPrec, sign ="
		  << second->appValue() << ","
		  << second->appComputed() << ","
		  << second->knownPrecision() << ","
		  << second->sign() << std::endl;
#endif
          if (!newValue.isZeroIn()) {   // Op(first, second) != 0
            lMSB() = newValue.lMSB();
            uMSB() = newValue.uMSB();
            sign() = newValue.sign();
#ifdef CORE_DEBUG_BOUND
            std::cout << "DebugBound(Exit Loop): " << "i=" << i << std::endl;
#endif
#ifdef CORE_TRACE
	    std::cout << "Zero is not in, lMSB() = " << lMSB()
		    << ", uMSB() = " << uMSB()
		    << ", sign() = " << sign() << std::endl;
	    std::cout << "newValue = " << newValue << std::endl;
#endif

            break; // assert -- this must happen in the loop if nonzero!
          }
          //8/9/01, Chee: implement escape precision here:
          if (i> EscapePrec) {
            EscapePrecFlag = -i.asLong();//negative means EscapePrec is used
	    core_error("Escape precision triggered at",
            		 __FILE__, __LINE__, false);
            if (EscapePrecWarning)
              std::cout<< "Escape Precision triggered at "
		      << EscapePrec << " bits" << std::endl;
#ifdef CORE_DEBUG
            std::cout << "EscapePrecFlags=" << EscapePrecFlag << std::endl;
            std::cout << "ua =" << ua  << ",lowBound=" << lowBound << std::endl;
#endif
            break;
          }// if
        }// for (long i=1...)

#ifdef CORE_DEBUG_BOUND
        rootBoundHitCounter++;
#endif

        if (sign() == 0 && ua .isInfty()) {
          core_error("AddSubRep: root bound has exceeded the maximum size\n \
            but we still cannot decide zero.\n", __FILE__, __LINE__, true);
        } // if (sign == 0 && ua .isInfty())
      }// else do progressive
    }
  }
  flagsComputed() = true;
}// AddSubRep::computeExactFlags

template <class Operator>
void AddSubRep<Operator>::computeApproxValue(const extLong& relPrec,
    const extLong& absPrec) {
  // Nov 13, 2002: added the analog of "reduceTo(first)" and "reduceTo(second)"
  //  that is found in computeExactFlags.  This is more efficient, but
  //  it also removes a NaN warning in subsequent logic!
  //  E.g., if first=0, then first->uMSB and first->lMSB are -infty, and
  //  subtracting them creates NaN.  Chee and Zilin.
  if (first->sign() == 0) {
    appValue() = Op(second->getAppValue(relPrec, absPrec));
    return;
  }
  if (second->sign() == 0) {
    appValue() = first->getAppValue(relPrec, absPrec);
    return;
  }
  if (lMSB() < EXTLONG_BIG && lMSB() > EXTLONG_SMALL) {
    extLong rf = first->uMSB()-lMSB()+relPrec+EXTLONG_FOUR;  // 2 better
    if (rf < EXTLONG_ZERO)
      rf = EXTLONG_ZERO;  // from Koji's thesis P63: Proposition 26
    extLong rs = second->uMSB()-lMSB()+relPrec+EXTLONG_FOUR; // 2 better
    if (rs < EXTLONG_ZERO)
      rs = EXTLONG_ZERO;  // from Koji's thesis P63: Proposition 26
    extLong  a  = absPrec + EXTLONG_THREE;                      // 1 better
    appValue() = Op(first->getAppValue(rf, a), second->getAppValue(rs, a));
  } else {
    std::cerr << "lMSB = " << lMSB() << std::endl; // should be in core_error
    core_error("CORE WARNING: a huge lMSB in AddSubRep",
	 	__FILE__, __LINE__, false);
  }
}

/// \typedef AddRep
/// \brief AddRep for easy of use
typedef AddSubRep<Add> AddRep;

/// \typedef SubRep
/// \brief SuRep for easy of use
typedef AddSubRep<Sub> SubRep;

/// \class MultRep
/// \brief multiplication operator node
class MultRep : public BinOpRep {
public:
  /// \name Constructors and Destructor
  //@{
  /// constructor
  MultRep(ExprRep* f, ExprRep* s) : BinOpRep(f, s) {
    ffVal = first->ffVal * second->ffVal;
  }
  /// destructor
  ~MultRep() {}
  //@}

  CORE_MEMORY(MultRep)
protected:
  /// compute sign and MSB
  void computeExactFlags();
  /// compute approximation value
  void computeApproxValue(const extLong&, const extLong&);
  /// return operator in string
  const std::string op() const {
    return "*";
  }
};

/// \class DivRep
/// \brief division operator node
class DivRep : public BinOpRep {
public:
  /// \name Constructors and Destructor
  //@{
  /// constructor
  DivRep(ExprRep* f, ExprRep* s) : BinOpRep(f, s) {
    ffVal = first->ffVal / second->ffVal;
  }
  /// destructor
  ~DivRep() {}
  //@}

  CORE_MEMORY(DivRep)
protected:
  /// compute sign and MSB
  void computeExactFlags();
  /// compute approximation value
  void computeApproxValue(const extLong&, const extLong&);
  /// return operator in string
  const std::string op() const {
    return "/";
  }
};

// inline functions
inline int ExprRep::getExactSign() {
  if (!nodeInfo)
    initNodeInfo();

  if (!flagsComputed()) {
    degreeBound();
#ifdef CORE_DEBUG
    dagSize();
    fullClearFlag();
#endif
    computeExactFlags();
  }
  return sign();
}

// Chee, 7/17/02: degreeBound() function is now
// taken out of "computeExactFlags()
inline int ExprRep::getSign() {
  if (ffVal.isOK())
    return ffVal.sign();
  else
    return getExactSign();
}

// you need force to approximate before call these functions!!
inline BigInt ExprRep::BigIntValue() {
  return getAppValue().BigIntValue();
}

inline BigRat ExprRep::BigRatValue() {
  return getAppValue().BigRatValue();
}

inline BigFloat ExprRep::BigFloatValue() {
  return getAppValue().BigFloatValue();
}

CORE_END_NAMESPACE
#endif // _CORE_EXPRREP_H_