Changeset 7467:16f7b7ad64c3

Timestamp:

12/01/07 09:09:29 (5 years ago)

Author:

dmharvey@…

Branch:

default

Message:

fixed #1211 (NTL crash in polynomial remainder over ZZ)

Location:

sage

Files:

• libs/ntl/decl.pxi (modified) (1 diff)
• rings/polynomial/polynomial_integer_dense_ntl.pyx (modified) (3 diffs)

sage/libs/ntl/decl.pxi

@@ -174 +174 @@
     ZZX_c* ZZX_construct "Construct<ZZX>"(void *mem)
     void ZZX_destruct "Destruct<ZZX>"(ZZX_c *mem)
+    void ZZX_swap "swap"(ZZX_c x, ZZX_c y)
     void ZZX_delete "Delete<ZZX>"(ZZX_c *mem)
     void ZZX_from_str "_from_str<ZZX>"(ZZX_c* dest, char* s)

sage/rings/polynomial/polynomial_integer_dense_ntl.pyx

@@ -317 +317 @@
     def quo_rem(self, right):
         r"""
-        Returns a tuple (quotient, remainder) where
-            self = quotient*other + remainder.
-
-        If the quotient and remainder are not integral,
-        an exception is raised.
-
+        Attempts to divide self by right, and return a quotient and remainder.
+
+        If right is monic, then it returns (q, r) where
+            self = q * right + r
+        and deg(r) < deg(right).
+
+        If right is not monic, then it returns (q, 0) where q = self/right
+        if right exactly divides self, otherwise it raises an exception.
+        
         EXAMPLES:
             sage: R.<x> = PolynomialRing(ZZ)
@@ -331 +334 @@
             sage: q*g + r == f
             True
+
+            sage: f = x^2
+            sage: f.quo_rem(0)
+            Traceback (most recent call last):
+            ...
+            ArithmeticError: division by zero polynomial
+
+            sage: f = (x^2 + 3) * (2*x - 1)
+            sage: f.quo_rem(2*x - 1)
+            (x^2 + 3, 0)
+
+            sage: f = x^2
+            sage: f.quo_rem(2*x - 1)
+            Traceback (most recent call last):
+            ...
+            ArithmeticError: division not exact in Z[x] (consider coercing to Q[x] first)
+            
         """
         if not isinstance(right, Polynomial_integer_dense_ntl):
@@ -337 +357 @@
             raise TypeError
 
-        # ugggh this isn't pretty. Lots of unnecessary copies.
-        cdef ZZX_c *r, *q
-        ZZX_quo_rem(&self.__poly, &(<Polynomial_integer_dense_ntl>right).__poly, &r, &q)
+        cdef Polynomial_integer_dense_ntl _right = <Polynomial_integer_dense_ntl> right
+
+        if ZZX_IsZero(_right.__poly):
+            raise ArithmeticError, "division by zero polynomial"
+
+        cdef ZZX_c *q, *r
+        cdef Polynomial_integer_dense_ntl qq = self._new()
         cdef Polynomial_integer_dense_ntl rr = self._new()
-        cdef Polynomial_integer_dense_ntl qq = self._new()
-        rr.__poly = r[0]
-        qq.__poly = q[0]
-        ZZX_delete(&r[0])
-        ZZX_delete(&q[0])
-        return (qq, rr)
+        cdef int divisible
+
+        if ZZ_IsOne(ZZX_LeadCoeff(_right.__poly)):
+            # divisor is monic. Just do the division and remainder
+            ZZX_quo_rem(&self.__poly, &_right.__poly, &r, &q)
+            ZZX_swap(qq.__poly, q[0])
+            ZZX_swap(rr.__poly, r[0])
+            ZZX_delete(q)
+            ZZX_delete(r)
+        else:
+            # Non-monic divisor. Check whether it divides exactly.
+            q = ZZX_div(&self.__poly, &_right.__poly, &divisible)
+            if divisible:
+                # exactly divisible
+                ZZX_swap(q[0], qq.__poly)
+                ZZX_delete(q)
+            else:
+                # division failed: clean up and raise exception
+                ZZX_delete(q)
+                raise ArithmeticError, "division not exact in Z[x] (consider coercing to Q[x] first)"
+            
+        return qq, rr
+