X-Git-Url: http://gitweb.michael.orlitzky.com/?a=blobdiff_plain;f=mjo%2Fpolynomial.py;h=9ef2902320318141d4089e3a27ff12e8b94e4de2;hb=852c32e6db3d27310489abd9e23787a1b7d068ad;hp=4fe4b71f03c53cd167f0d86975a9acfb1c28ff96;hpb=04af4ba818603b6147f3914202d30b7054a9b507;p=sage.d.git

diff --git a/mjo/polynomial.py b/mjo/polynomial.py
index 4fe4b71..9ef2902 100644
--- a/mjo/polynomial.py
+++ b/mjo/polynomial.py
@@ -114,6 +114,22 @@ def multidiv(f, gs):
         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
@@ -135,7 +151,6 @@ def multidiv(f, gs):
 
         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())
@@ -146,6 +161,19 @@ def multidiv(f, gs):
         ....:                     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: f = 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)
@@ -155,9 +183,8 @@ def multidiv(f, 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).
@@ -166,13 +193,7 @@ def multidiv(f, gs):
                 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()