Changeset 7873:d295f1317dda

Timestamp:

12/22/07 19:24:31 (5 years ago)

Author:

Robert Miller <rlmillster@…>

Branch:

default

Tags:

2.9.1.rc2

Message:

Joel Mohler's diff for trac #1558

Location:

sage

Files:

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

sage/libs/ntl/decl.pxi

@@ -10 +10 @@
     ctypedef struct ZZ_c "struct ZZ":
         pass
+
+    ctypedef struct vec_ZZ_c "vec_ZZ":
+        ZZ_c RawGet(long i)
+        ZZ_c *elts()
+        long length()
 
     void del_charstar(char*)
@@ -168 +173 @@
     # really, this is from NTL/ZZX.h
     ctypedef struct ZZX_c "struct ZZX":
-        pass
+        vec_ZZ_c rep
+
+    ctypedef struct pair_ZZX_long_c "pair_ZZX_long":
+        ZZX_c a
+        long b
+
+    ctypedef struct vec_pair_ZZX_long_c "vec_pair_ZZX_long":
+        pair_ZZX_long_c RawGet(long i)
+        long length()
 
     # Some boiler-plate
@@ -199 +212 @@
     void ZZX_XGCD "XGCD"(ZZ_c r, ZZX_c s, ZZX_c t, ZZX_c a, ZZX_c b, long deterministic)
     void ZZX_content "content"(ZZ_c d, ZZX_c f)
+    void ZZX_factor "factor"(ZZ_c c, vec_pair_ZZX_long_c factors, ZZX_c f, long verbose, long bnd)
 
     void ZZX_squarefree_decomposition(ZZX_c*** v, long** e, long* n, ZZX_c* x)

sage/rings/polynomial/polynomial_integer_dense_ntl.pyx

@@ -18 +18 @@
 
 include "../../ext/stdsage.pxi"
-
+include "sage/ext/interrupt.pxi"
+                                                                                                                                    
 from sage.rings.polynomial.polynomial_element cimport Polynomial
 from sage.structure.element cimport ModuleElement, RingElement
@@ -235 +236 @@
             0
         """
-        # todo: this is performing an unnecessary copy. We need
-        # a function that returns a (const!) pointer to the coefficient
-        # of the NTL polynomial.
-        cdef ZZ_c temp = ZZX_coeff(self.__poly, n)
         cdef Integer z = PY_NEW(Integer)
-        ZZ_to_mpz(&z.value, &temp)
-        return z
-
+        if n < 0 or n > ZZX_deg(self.__poly):
+            return z
+        else:
+            # Note that the NTL documentation blesses this direct access of the "rep" member in ZZX.txt.
+            #  Check the "Miscellany" section.
+            ZZ_to_mpz(&z.value, &self.__poly.rep.elts()[n])
+            return z
 
     def __getslice__(self, long i, long j):
@@ -696 +697 @@
         free(e)
         return Factorization(F, unit=c, sort=False)
-    
+
+    def _factor_pari(self):
+        return Polynomial.factor(self) # uses pari for integers over ZZ
+
+    def _factor_ntl(self):
+        """
+        There are ample doc-tests elsewhere that test this functionality.
+        AUTHOR:
+            -- Joel B. Mohler
+        """
+        cdef Polynomial_integer_dense_ntl fac_py
+        cdef ZZ_c content
+        cdef vec_pair_ZZX_long_c factors
+        cdef long i
+        cdef int sig_me = ZZX_deg(self.__poly)
+        if sig_me > 10:
+            _sig_on
+        ZZX_factor(content, factors, self.__poly, 0, 0)
+        if sig_me > 10:
+            _sig_off
+        results = []
+        unit = None
+        if not ZZ_IsOne(content):
+            fac_py = self._new()
+            ZZX_SetCoeff(fac_py.__poly, 0, content)
+            if ZZX_deg(fac_py.__poly) == 0 and ZZ_to_int(fac_py.__poly.rep.elts())==-1:
+                unit = fac_py
+            else:
+                results.append( (fac_py,1) )
+        for i from 0 <= i < factors.length():
+            fac_py = self._new()
+            fac_py.__poly = factors.RawGet(i).a
+            results.append( (fac_py,factors.RawGet(i).b) )
+        return Factorization(results, unit = unit)
+
+    def factor(self):
+        """
+        This function overrides the generic polynomial factorization to 
+        make a somewhat intelligent decision to use Pari or NTL based on 
+        some benchmarking.
+
+        EXAMPLES:
+            sage: R.<x>=ZZ[]
+            sage: f=x^4-1
+            sage: f.factor()
+            (x - 1) * (x + 1) * (x^2 + 1)
+            sage: f=1-x
+            sage: f.factor()
+            (-1) * (x - 1)
+            sage: f.factor().unit()
+            -1
+        """
+        cdef int i
+        cdef int deg = ZZX_deg(self.__poly)
+        # it appears that pari has a window from about degrees 30 and 300 in which it beats NTL.
+        if deg < 30 or deg > 300:
+            return self._factor_ntl()
+        else:
+            return self._factor_pari()
 
     def factor_mod(self, p):