sage: r.is_zero()
False
+ Example 4 in Section 2.3 of Cox, Little, and O'Shea. This is the
+ same as Example 2, except with the order of ``gs`` reversed::
+
+ sage: R = PolynomialRing(QQ, 'x,y', order='lex')
+ sage: x,y = R.gens()
+ sage: f = x^2*y + x*y^2 + y^2
+ sage: gs = [ y^2 - 1, x*y - 1 ]
+ sage: (qs, r) = multidiv(f, gs)
+ sage: (qs, r)
+ ([x + 1, x], 2*x + 1)
+ sage: r + sum( qs[i]*gs[i] for i in range(len(gs)) ) == f
+ True
+ sage: not any( g.lt().divides(m) for m in r.monomials()
+ ....: for g in gs )
+ True
+
TESTS:
If we get a zero remainder, then the numerator should belong to
sage: x,y,z = R.gens()
sage: s = ZZ.random_element(1,5).abs()
sage: gs = [ R.random_element() for idx in range(s) ]
- sage: f = R.random_element(ZZ.random_element(10).abs())
+ sage: # hack for SageMath Trac #28855
+ sage: f = R(R.random_element(ZZ.random_element(10).abs()))
sage: (qs, r) = multidiv(f,gs)
sage: r != 0 or f in R.ideal(gs)
True
sage: set_random_seed()
sage: R = PolynomialRing(QQ, 'x,y,z')
- sage: x,y,z = R.gens()
sage: s = ZZ.random_element(1,5).abs()
sage: gs = [ R.random_element() for idx in range(s) ]
- sage: f = R.random_element(ZZ.random_element(10).abs())
+ sage: # hack for SageMath Trac #28855
+ sage: f = R(R.random_element(ZZ.random_element(10).abs()))
sage: (qs, r) = multidiv(f,gs)
sage: r + sum( qs[i]*gs[i] for i in range(len(gs)) ) == f
True
....: for g in gs ))
True
+ Exercise 8 in Section 2.4 of Cox, Little, and O'Shea says that we
+ should always get a zero remainder if we divide an element of a
+ monomial ideal by its generators::
+
+ sage: set_random_seed()
+ sage: R = PolynomialRing(QQ,'x,y,z')
+ sage: gs = R.random_element().monomials()
+ sage: I = R.ideal(gs)
+ sage: # hack for SageMath Trac #28855
+ sage: f = R(I.random_element(ZZ.random_element(5).abs()))
+ sage: (qs, r) = multidiv(f, gs)
+ sage: r.is_zero()
+ True
+
"""
R = f.parent()
s = len(gs)
qs = [R.zero()]*s
while p != R.zero():
- i = 0
- division_occurred = false
- while i < s:
+ for i in range(0,s):
+ division_occurred = false
# If gs[i].lt() divides p.lt(), then this remainder will
# be zero and the quotient will be in R (and not the
# fraction ring, which is important).
qs[i] += factor
p -= factor*gs[i]
division_occurred = true
- # Don't increment "i" here because we want to try
- # again with this "denominator" g[i]. We might
- # get another factor out of it, but we know that
- # we can't get another factor out of an *earlier*
- # denominator g[i-k] for some k.
- else:
- i += 1
+ break
if not division_occurred:
r += p.lt()