division_in_place()

bool DPoly::division_in_place	(	int	level,
		TowerPolynomial &	f,
		const TowerPolynomial	g,
		TowerPolynomial &	result_quot )

Definition at line 1015 of file dpoly.cpp.

{
  assert(g != 0);
  if (f == nullptr || f->deg < g->deg)
    {
      result_quot = nullptr;
      return true;
    }
  int shift = f->deg - g->deg;
  result_quot = alloc_poly_n(shift);
 
  if (level == 0)
    {
      // TODO: this code seems completely wrong!??!!  too?
      long *p = f->arr.ints;
      long *q = g->arr.ints;
      long leadcoeff = q[g->deg];
      long invlead = 1;
      if (leadcoeff != 1)
        {
          ZZp_INVERT(charac, invlead, leadcoeff);
        }
      for (int d = f->deg; shift >= 0; d--, shift--)
        {
          long a = p[d];
          if (a != 0)
            {
              ZZp_MULT(charac, a, invlead);
              result_quot->arr.ints[shift] = a;
              ZZp_NEGATE(charac, a);
              for (int j = 0; j <= g->deg; j++)
                ZZp_APXY(charac, p[shift + j], a, q[j]);
            }
        }
      reset_degree_0(f);
      return true;
    }
  else
    {
      // TODO: this code seems completely wrong!??!!
      TowerPolynomial *p = f->arr.polys;
      TowerPolynomial *q = g->arr.polys;
      TowerPolynomial leadcoeff = q[g->deg];
      TowerPolynomial invlead;
      if (is_one(level - 1, leadcoeff))
        invlead = leadcoeff;
      else
        {
          invlead = invert(level - 1, leadcoeff);
          if (invlead == nullptr) return false;
        }
      for (int d = f->deg; shift >= 0; d--, shift--)
        {
          TowerPolynomial a = p[d];
          if (a != nullptr)
            {
              TowerPolynomial b = mult(level - 1, invlead, a, true);
              result_quot->arr.polys[shift] = copy(level - 1, b);
              for (int j = 0; j <= g->deg; j++)
                {
                  b = mult(level - 1, a, q[j], true);
                  subtract_in_place(level - 1, p[j + shift], b);
                }
            }
        }
      reset_degree_n(level, f);
      return true;
    }
}

References alloc_poly_n(), charac, copy(), invert(), is_one(), mult(), p, reset_degree_0(), reset_degree_n(), subtract_in_place(), ZZp_APXY(), ZZp_INVERT(), ZZp_MULT(), and ZZp_NEGATE().

Referenced by remainder().