Changeset 7439:cea8d29e100c

Timestamp:

11/10/07 12:52:39 (6 years ago)

Author:

Joel B. Mohler <jbm5@…>

Branch:

default

Message:

Moved the defining poly pointer into the number field element for speed.

Location:

sage/rings/number_field

Files:

• number_field.py (modified) (2 diffs)
• number_field_element.pxd (modified) (2 diffs)
• number_field_element.pyx (modified) (11 diffs)

sage/rings/number_field/number_field.py

@@ -2053 +2053 @@
         """
         return infinity.infinity
-        
+
     def polynomial_ntl(self):
         """
@@ -3623 +3623 @@
         return K
 
+    def absolute_polynomial_ntl(self):
+        """
+        Return defining polynomial of this number field
+        as a pair, an ntl polynomial and a denominator.
+
+        This is used mainly to implement some internal arithmetic.
+
+        EXAMPLES:
+            sage: NumberField(x^2 + (2/3)*x - 9/17,'a').polynomial_ntl()
+            ([-27 34 51], 51)
+        """
+        try:
+            return (self.__abs_polynomial_ntl, self.__abs_denominator_ntl)
+        except AttributeError:
+            self.__abs_denominator_ntl = ntl.ZZ()
+            den = self.absolute_polynomial().denominator()
+            self.__abs_denominator_ntl.set_from_sage_int(ZZ(den))
+            self.__abs_polynomial_ntl = ntl.ZZX((self.absolute_polynomial()*den).list())
+        return (self.__abs_polynomial_ntl, self.__abs_denominator_ntl)
+
     def absolute_polynomial(self):
         r"""

sage/rings/number_field/number_field_element.pxd

@@ -8 +8 @@
 from sage.structure.element cimport FieldElement, RingElement, ModuleElement
 from sage.structure.parent_base cimport ParentWithBase
+from sage.libs.ntl.ntl_ZZX cimport ntl_ZZX
+from sage.libs.ntl.ntl_ZZ cimport ntl_ZZ
 
 cdef class NumberFieldElement(FieldElement):
     cdef ZZX_c __numerator
     cdef ZZ_c __denominator
+    # Pointers to the defining polynomial (with numerator) for the field.
+    # I keep these as pointers for arithmetic speed.
+    cdef ntl_ZZX __fld_numerator
+    cdef ntl_ZZ __fld_denominator
     cdef object __multiplicative_order
     cdef object __pari
@@ -23 +29 @@
     cdef void _ntl_denom_as_mpz(self, mpz_t* z)
 
+    # _parent_poly_c_ is deprecated -- refer to doc-string
     cdef void _parent_poly_c_(self, ZZX_c *num, ZZ_c *den)
     cdef void _invert_c_(self, ZZX_c *num, ZZ_c *den)

sage/rings/number_field/number_field_element.pyx

@@ -126 +126 @@
         x = <NumberFieldElement>PY_NEW_SAME_TYPE(self)
         x._parent = self._parent
+        x.__fld_numerator = self.__fld_numerator
+        x.__fld_denominator = self.__fld_denominator
         return x
 
@@ -176 +178 @@
         """
         sage.rings.field_element.FieldElement.__init__(self, parent)
+        if isinstance(parent, number_field.NumberField_relative):
+            self.__fld_numerator, self.__fld_denominator = parent.absolute_polynomial_ntl()
+        else:
+            self.__fld_numerator, self.__fld_denominator = parent.polynomial_ntl()
 
         cdef ZZ_c coeff
@@ -277 +283 @@
         cdef NumberFieldElement x = <NumberFieldElement>PY_NEW_SAME_TYPE(self)
         x._parent = <ParentWithBase>new_parent
+        x.__fld_numerator, x.__fld_denominator = new_parent.polynomial_ntl()
         x.__denominator = self.__denominator
         cdef ZZX_c result
@@ -738 +745 @@
         cdef ZZX_c temp
         cdef ZZ_c temp1
-        cdef ZZ_c parent_den
-        cdef ZZX_c parent_num
-        self._parent_poly_c_( &parent_num, &parent_den )
         x = self._new()
         _sig_on
         # MulMod doesn't handle non-monic polynomials.
         # Therefore, we handle the non-monic case entirely separately.
-        if ZZX_is_monic( &parent_num ):
+        if ZZX_is_monic( &self.__fld_numerator.x ):
             ZZ_mul(x.__denominator, self.__denominator, _right.__denominator)
-            ZZX_MulMod(x.__numerator, self.__numerator, _right.__numerator, parent_num)
+            ZZX_MulMod(x.__numerator, self.__numerator, _right.__numerator, self.__fld_numerator.x)
         else:
             ZZ_mul(x.__denominator, self.__denominator, _right.__denominator)
             ZZX_mul(x.__numerator, self.__numerator, _right.__numerator)
-            if ZZX_deg(x.__numerator) >= ZZX_deg(parent_num):
-                ZZX_mul_ZZ( x.__numerator, x.__numerator, parent_den )
-                ZZX_mul_ZZ( temp, parent_num, x.__denominator )
-                ZZ_power(temp1,ZZX_LeadCoeff(temp),ZZX_deg(x.__numerator)-ZZX_deg(parent_num)+1)
+            if ZZX_deg(x.__numerator) >= ZZX_deg(self.__fld_numerator.x):
+                ZZX_mul_ZZ( x.__numerator, x.__numerator, self.__fld_denominator.x )
+                ZZX_mul_ZZ( temp, self.__fld_numerator.x, x.__denominator )
+                ZZ_power(temp1,ZZX_LeadCoeff(temp),ZZX_deg(x.__numerator)-ZZX_deg(self.__fld_numerator.x)+1)
                 ZZX_PseudoRem(x.__numerator, x.__numerator, temp)
-                ZZ_mul(x.__denominator, x.__denominator, parent_den)
+                ZZ_mul(x.__denominator, x.__denominator, self.__fld_denominator.x)
                 ZZ_mul(x.__denominator, x.__denominator, temp1)
         _sig_off
@@ -796 +800 @@
         cdef ZZX_c inv_num
         cdef ZZ_c inv_den
-        cdef ZZ_c parent_den
-        cdef ZZX_c parent_num
         cdef ZZX_c temp
         cdef ZZ_c temp1
         if not _right:
             raise ZeroDivisionError, "Number field element division by zero"
-        self._parent_poly_c_( &parent_num, &parent_den )
         x = self._new()
         _sig_on
         _right._invert_c_(&inv_num, &inv_den)
-        if ZZX_is_monic( &parent_num ):
+        if ZZX_is_monic( &self.__fld_numerator.x ):
             ZZ_mul(x.__denominator, self.__denominator, inv_den)
-            ZZX_MulMod(x.__numerator, self.__numerator, inv_num, parent_num)
+            ZZX_MulMod(x.__numerator, self.__numerator, inv_num, self.__fld_numerator.x)
         else:
             ZZ_mul(x.__denominator, self.__denominator, inv_den)
             ZZX_mul(x.__numerator, self.__numerator, inv_num)
-            if ZZX_deg(x.__numerator) >= ZZX_deg(parent_num):
-                ZZX_mul_ZZ( x.__numerator, x.__numerator, parent_den )
-                ZZX_mul_ZZ( temp, parent_num, x.__denominator )
-                ZZ_power(temp1,ZZX_LeadCoeff(temp),ZZX_deg(x.__numerator)-ZZX_deg(parent_num)+1)
+            if ZZX_deg(x.__numerator) >= ZZX_deg(self.__fld_numerator.x):
+                ZZX_mul_ZZ( x.__numerator, x.__numerator, self.__fld_denominator.x )
+                ZZX_mul_ZZ( temp, self.__fld_numerator.x, x.__denominator )
+                ZZ_power(temp1,ZZX_LeadCoeff(temp),ZZX_deg(x.__numerator)-ZZX_deg(self.__fld_numerator.x)+1)
                 ZZX_PseudoRem(x.__numerator, x.__numerator, temp)
-                ZZ_mul(x.__denominator, x.__denominator, parent_den)
+                ZZ_mul(x.__denominator, x.__denominator, self.__fld_denominator.x)
                 ZZ_mul(x.__denominator, x.__denominator, temp1)
         x._reduce_c_()
@@ -923 +924 @@
 
     cdef void _parent_poly_c_(self, ZZX_c *num, ZZ_c *den):
+        """
+        I believe this function should be removed since I've put the pointer 
+        __fld_numerator and __fld_denominator in the element class.  I'm not 
+        going to remove it quite yet, but feel free to remove it if you agree 
+        with me that it should go.
+        """
         raise NotImplementedError, "NumberFieldElement subclasses must override _parent_poly_c_()"
 
@@ -939 +946 @@
             Check __invert__ for doc-tests that rely on this functionality.
         """
-        cdef ZZ_c parent_den
-        cdef ZZX_c parent_num
-        self._parent_poly_c_( &parent_num, &parent_den )
-
         cdef ZZX_c t # unneeded except to be there
         cdef ZZX_c a, b
-        ZZX_mul_ZZ( a, self.__numerator, parent_den )
-        ZZX_mul_ZZ( b, parent_num, self.__denominator )
+        ZZX_mul_ZZ( a, self.__numerator, self.__fld_denominator.x )
+        ZZX_mul_ZZ( b, self.__fld_numerator.x, self.__denominator )
         ZZX_XGCD( den[0], num[0],  t, a, b, 1 )
-        ZZX_mul_ZZ( num[0], num[0], parent_den )
+        ZZX_mul_ZZ( num[0], num[0], self.__fld_denominator.x )
         ZZX_mul_ZZ( num[0], num[0], self.__denominator )
 
@@ -1629 +1632 @@
         
     cdef void _parent_poly_c_(self, ZZX_c *num, ZZ_c *den):
+        """
+        I believe this function should be removed since I've put the pointer 
+        __fld_numerator and __fld_denominator in the element class.  I'm not 
+        going to remove it quite yet, but feel free to remove it if you agree 
+        with me that it should go.
+        """
         cdef ntl_ZZX _num
         cdef ntl_ZZ _den
@@ -1743 +1752 @@
 
     cdef void _parent_poly_c_(self, ZZX_c *num, ZZ_c *den):
+        """
+        I believe this function should be removed since I've put the pointer 
+        __fld_numerator and __fld_denominator in the element class.  I'm not 
+        going to remove it quite yet, but feel free to remove it if you agree 
+        with me that it should go.
+        """
         f = self.number_field().absolute_polynomial()
         _ntl_poly(f, num, den)
@@ -1840 +1855 @@
         """
         cdef OrderElement_absolute x
-        x = <NumberFieldElement>PY_NEW_SAME_TYPE(self)
+        x = <OrderElement_absolute>PY_NEW_SAME_TYPE(self)
         x._parent = self._parent
         x._number_field = self._parent.number_field()
+        x.__fld_numerator = self.__fld_numerator
+        x.__fld_denominator = self.__fld_denominator
         return x
 
@@ -1883 +1900 @@
         """
         cdef OrderElement_relative x
-        x = <NumberFieldElement>PY_NEW_SAME_TYPE(self)
+        x = <OrderElement_relative>PY_NEW_SAME_TYPE(self)
         x._parent = self._parent
         x._number_field = self._parent.number_field()
+        x.__fld_numerator = self.__fld_numerator
+        x.__fld_denominator = self.__fld_denominator
         return x