division_algorithm() [2/2]

Nterm * PolyRing::division_algorithm ( Nterm * f, Nterm * g, Nterm *& quot ) const

protected

Definition at line 1458 of file poly.cpp.

{
  // This returns the remainder, and sets quot to be the quotient.
 
  // This does standard division by one polynomial.
  // However, it does work for Weyl algebra, skew commutative algebra,
  // This works if the coefficient ring is a field, or ZZ.
 
  ring_elem a = copy(f);
  Nterm *t = a;
  Nterm *b = g;
  Nterm divhead;
  Nterm remhead;
  Nterm *divt = &divhead;
  Nterm *remt = &remhead;
  Nterm *nextterm = new_term();
 
  //  buffer o;
  while (t != nullptr)
    if (M_->divides_partial_order(b->monom, t->monom))
      {
        // o << "t = "; elem_text_out(o,t); o << newline;
        a = t;
        bool cancelled = imp_attempt_to_cancel_lead_term(
            a, g, nextterm->coeff, nextterm->monom);
        t = a;
        //      o << "  new t = "; elem_text_out(o,t); o << newline;
        //      o << "  cancelled = " << (cancelled ? "true" : "false") <<
        //      newline;
        //      o << "  coeff = "; K_->elem_text_out(o,nextterm->coeff); o <<
        //      newline;
        //      emit(o.str());
        if (!K_->is_zero(nextterm->coeff))
          {
            divt->next = nextterm;
            divt = divt->next;
            nextterm = new_term();
          }
        if (!cancelled)
          {
            remt->next = t;
            remt = remt->next;
            t = t->next;
          }
      }
    else
      {
        remt->next = t;
        remt = remt->next;
        t = t->next;
      }
 
  nextterm = nullptr;
  remt->next = nullptr;
  divt->next = nullptr;
  quot = divhead.next;
  return remhead.next;
}

References Nterm::coeff, copy(), imp_attempt_to_cancel_lead_term(), PolynomialRing::K_, PolynomialRing::M_, Nterm::monom, new_term(), and Nterm::next.

Referenced by division_algorithm_with_laurent_variables(), and remainderAndQuotient().