mjo/polynomial.py: add two more examples from exercises in the text.

[sage.d.git] / mjo / polynomial.py

diff --git a/mjo/polynomial.py b/mjo/polynomial.py
index c3fbf56a475f7f1ee75fecc4c6d63fae16196f68..4fe4b71f03c53cd167f0d86975a9acfb1c28ff96 100644 (file)
--- a/mjo/polynomial.py
+++ b/mjo/polynomial.py
@@ -75,6 +75,45 @@ def multidiv(f, gs):
         ....:          for g in gs )
         True
 
+    A solution ``g`` to Exercise 6 in Section 2.3 of Cox, Little, and
+    O'Shea that lives in the ideal generated by ``f1`` and ``f2`` but
+    which has nonzero remainder after division::
+
+        sage: R = PolynomialRing(QQ, 'x,y', order='deglex')
+        sage: x,y = R.gens()
+        sage: f1 = 2*x*y^2 - x
+        sage: f2 = 3*x^2*y - y - 1
+        sage: I = R.ideal(f1,f2)
+        sage: g = 2*y*f2
+        sage: g in I
+        True
+        sage: (qs,r) = multidiv(g,[f1,f2])
+        sage: r.is_zero()
+        False
+
+    Two solutions ``g`` to Exercise 7 in Section 2.3 of Cox, Little, and
+    O'Shea that live in the ideal generated by ``f1``, ``f2``, and ``f3``
+    but which have nonzero remainders after division::
+
+        sage: R = PolynomialRing(QQ, 'x,y,z', order='deglex')
+        sage: x,y,z = R.gens()
+        sage: f1 = x^4*y^2 - z
+        sage: f2 = x^3*y^3 - 1
+        sage: f3 = x^2*y^4 - 2*z
+        sage: I = R.ideal(f1,f2,f3)
+        sage: g = x^2*f3
+        sage: g in I
+        True
+        sage: (qs, r) = multidiv(g, [f1,f2,f3])
+        sage: r.is_zero()
+        False
+        sage: g = x*f2
+        sage: g in I
+        True
+        sage: (qs, r) = multidiv(g, [f1,f2,f3])
+        sage: r.is_zero()
+        False
+
     TESTS:
 
     If we get a zero remainder, then the numerator should belong to
@@ -116,8 +155,9 @@ def multidiv(f, gs):
     qs = [R.zero()]*s
 
     while p != R.zero():
-        for i in range(0,s):
-            division_occurred = false
+        i = 0
+        division_occurred = false
+        while i < s:
             # 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).
@@ -126,7 +166,13 @@ def multidiv(f, gs):
                 qs[i] += factor
                 p -= factor*gs[i]
                 division_occurred = true
-                break
+                # 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
 
         if not division_occurred:
             r += p.lt()