gcd_extended()

ring_elem PolyRing::gcd_extended	(	const ring_elem	f,
		const ring_elem	g,
		ring_elem &	u,
		ring_elem &	v ) const

Definition at line 1083 of file poly.cpp.

{
  u = from_long(1);
  ring_elem result = copy(f);
 
  if (is_zero(g))
    {
      v = from_long(0);
      return result;
    }
  ring_elem v1 = ZERO_RINGELEM;
  ring_elem v3 = copy(g);
  ring_elem t1, t3;
  ring_elem temp1, temp2, temp3;
  while (!is_zero(v3))
    {
      ring_elem q;
      t3 = remainderAndQuotient(result, v3, q);
 
      // The following is: t1 = u - q*v1
      temp1 = mult(q, v1);
      subtract_to(u, temp1);
      t1 = u;
 
      u = v1;
      result = v3;
      v1 = t1;
      v3 = t3;
    }
 
  // make 'result' monic. (and divide 'u' by this as well)
  if (!is_zero(result))
    {
      Nterm *t = result;
      ring_elem c = K_->invert(t->coeff);
      mult_coeff_to(c, result);
      mult_coeff_to(c, u);
    }
 
  // The following is v = (result - f*u)/g
  temp1 = mult(f, u);
  temp2 = subtract(result, temp1);
  temp3 = remainderAndQuotient(temp2, g, v);
 
  return result;
}

References Nterm::coeff, copy(), from_long(), is_zero(), PolynomialRing::K_, mult(), mult_coeff_to(), remainderAndQuotient(), result(), subtract(), Ring::subtract_to(), and ZERO_RINGELEM.