Changeset 6389:cb2145e73391


Ignore:
Timestamp:
09/18/07 02:48:27 (6 years ago)
Author:
Robert Bradshaw <robertwb@…>
Branch:
default
Message:

quadratic number field element work

Files:
3 edited

Legend:

Unmodified
Added
Removed

  • sage/rings/number_field/number_field.py

    r6381 r6389  
    182182from sage.structure.parent_gens import ParentWithGens 
    183183import number_field_element 
     184import number_field_element_quadratic 
    184185from number_field_ideal import convert_from_zk_basis, is_NumberFieldIdeal 
    185186 
    … …  
    15111512                return self.__disc 
    15121513            except AttributeError: 
    1513                 self.__disc = QQ(str(self.pari_polynomial().nfdisc())) 
     1514                self.__disc = ZZ(str(self.pari_polynomial().nfdisc())) 
    15141515                return self.__disc 
    15151516        else: 
    … …  
    36823683        """ 
    36833684        NumberField_absolute.__init__(self, polynomial, name=name, check=check) 
     3685        self._element_class = number_field_element_quadratic.NumberFieldElement_quadratic 
     3686        c, b, a = [rational.Rational(t) for t in self.defining_polynomial().list()] 
     3687        # set the generator 
     3688        parts = -b/(2*a), ((b*b-4*a*c)/self.discriminant()).sqrt()/(2*a) 
     3689        self._NumberField_generic__gen = self._element_class(self, parts) 
    36843690         
    36853691    def __reduce__(self): 

  • sage/rings/number_field/number_field_element_quadratic.pyx

    r6388 r6389  
    1717Optimized Quadratic Number Field Elements 
    1818 
     19NO TESTS => BROKEN! 
     20 
    1921AUTHORS:  
    2022    -- Robert Bradshaw (2007-09): Initial version 
    … …  
    2729    object PY_NEW_SAME_TYPE(object o) 
    2830    bint PY_TYPE_CHECK_EXACT(object o, object type) 
     31     
     32cdef extern from *: 
     33    # TODO: move to cdefs.pxi 
     34    void mpz_addmul (mpz_t rop, mpz_t op1, mpz_t op2) 
     35    void mpz_submul (mpz_t rop, mpz_t op1, mpz_t op2) 
    2936 
    3037cdef object QQ, ZZ 
    … …  
    3340 
    3441 
     42cdef mpz_to_str(mpz_t z): 
     43    cdef Integer zz = PY_NEW(Integer) 
     44    mpz_set(zz.value, z) 
     45    return str(zz) 
     46 
    3547 
    3648cdef class NumberFieldElement_quadratic(NumberFieldElement_absolute): 
    3749    # (a + b sqrt(disc)) / denom  
    3850    def __init__(self, parent, f): 
    39         NumberFieldElement_absolute.__init__(self, parent, f) # this is heavy, can I avoid it for f in Rational, tuple? 
    4051        self.disc = parent.discriminant() 
    4152        cdef Integer a, b, denom 
    … …  
    4657        cdef NumberFieldElement_quadratic gen 
    4758         
    48         if PY_TYPE_CHECK_EXACT(f, Rational): 
     59        if PY_TYPE_CHECK(f, NumberFieldElement_quadratic): 
     60            mpz_set(self.a, (<NumberFieldElement_quadratic>f).a) 
     61            mpz_set(self.b, (<NumberFieldElement_quadratic>f).b) 
     62            mpz_set(self.denom, (<NumberFieldElement_quadratic>f).denom) 
     63             
     64        elif PY_TYPE_CHECK_EXACT(f, Rational): 
     65            NumberFieldElement_absolute.__init__(self, parent, None) 
    4966            mpz_set(self.a, mpq_numref((<Rational>f).value)) 
    5067            mpz_set_ui(self.b, 0) 
    … …  
    5269             
    5370        elif PY_TYPE_CHECK_EXACT(f, tuple) and len(f) == 2: 
     71            NumberFieldElement_absolute.__init__(self, parent, None) 
    5472            ad, bd = f 
    5573            mpz_set(self.a, a.value) 
    … …  
    6280 
    6381        elif PY_TYPE_CHECK_EXACT(f, tuple) and len(f) == 3: 
     82            NumberFieldElement_absolute.__init__(self, parent, None) 
    6483            a, b, denom = f 
    6584            mpz_set(self.a, a.value) 
    … …  
    6988             
    7089        else: 
     90            NumberFieldElement_absolute.__init__(self, parent, f) # this is heavy, can I avoid it for f in Rational, tuple? 
    7191            # poly in gen (which may not be sqrt(d)) 
    7292            self._ntl_coeff_as_mpz(&self.a, 0) 
    … …  
    85105                mpz_set_ui(self.denom, 1) 
    86106 
    87     def __new__(self): 
     107    def __new__(self, parent=None, f=None): 
    88108        mpz_init(self.a) 
    89109        mpz_init(self.b) 
    … …  
    97117    def parts(self): 
    98118        cdef Rational ad = <Rational>PY_NEW(Rational), bd = <Rational>PY_NEW(Rational) 
    99         mpz_set(mpq_numref(ad.value), self.a) 
    100         mpz_set(mpq_denref(ad.value), self.denom) 
    101         mpz_set(mpq_numref(bd.value), self.b) 
    102         mpz_set(mpq_denref(bd.value), self.denom) 
     119        if mpz_cmp_ui(self.a, 0) == 0: 
     120            mpq_set_ui(ad.value, 0, 1) 
     121        else: 
     122            mpz_set(mpq_numref(ad.value), self.a) 
     123            mpz_set(mpq_denref(ad.value), self.denom) 
     124        if mpz_cmp_ui(self.b, 0) == 0: 
     125            mpq_set_ui(bd.value, 0, 1) 
     126        else: 
     127            mpz_set(mpq_numref(bd.value), self.b) 
     128            mpz_set(mpq_denref(bd.value), self.denom) 
    103129        return ad, bd 
    104130         
    … …  
    114140        cdef mpz_t gcd 
    115141        mpz_init(gcd) 
    116         mpz_gcd(gcd, self.a, self.b) 
    117         mpz_gcd(gcd, gcd, self.denom) 
     142        mpz_gcd(gcd, self.a, self.denom) 
     143        mpz_gcd(gcd, gcd, self.b) 
    118144        if mpz_cmp_si(gcd, 1): # != 0 (i.e. it is not 1) 
    119145            mpz_divexact(self.a, self.a, gcd) 
    … …  
    124150    cdef ModuleElement _add_c_impl(self, ModuleElement other_m): 
    125151        cdef NumberFieldElement_quadratic other = <NumberFieldElement_quadratic>other_m 
    126         cdef NumberFieldElement_quadratic res = <NumberFieldElement_quadratic>self._new_c() 
    127         res.disc = self.disc 
    128         mpz_add(res.a, self.a, other.a) 
    129         mpz_add(res.b, self.b, other.b) 
    130         mpz_set(res.denom, self.denom) 
     152        cdef NumberFieldElement_quadratic res = <NumberFieldElement_quadratic>self._new() 
     153        cdef mpz_t gcd, tmp 
     154        res.disc = self.disc 
     155        if mpz_cmp(self.denom, other.denom) == 0: 
     156            mpz_add(res.a, self.a, other.a) 
     157            mpz_add(res.b, self.b, other.b) 
     158            mpz_set(res.denom, self.denom) 
     159        else: 
     160            mpz_init(gcd) 
     161            mpz_gcd(gcd, self.denom, other.denom) 
     162            if mpz_cmp_ui(gcd, 1) == 0: 
     163                mpz_mul(res.a, self.a, other.denom) 
     164                mpz_addmul(res.a, self.denom, other.a) 
     165                mpz_mul(res.b, self.b, other.denom) 
     166                mpz_addmul(res.b, self.denom, other.b) 
     167                mpz_mul(res.denom, self.denom, other.denom) 
     168            else: 
     169                mpz_init(tmp) 
     170                mpz_divexact(tmp, other.denom, gcd) 
     171                mpz_mul(res.a, self.a, tmp) 
     172                mpz_mul(res.b, self.b, tmp) 
     173                mpz_divexact(tmp, self.denom, gcd) 
     174                mpz_addmul(res.a, other.a, tmp) 
     175                mpz_addmul(res.b, other.b, tmp) 
     176                mpz_mul(res.denom, other.denom, tmp) 
     177                mpz_clear(tmp) 
     178            mpz_clear(gcd) 
    131179        res._reduce_c_() 
    132180        return res 
    … …  
    134182    cdef ModuleElement _sub_c_impl(self, ModuleElement other_m): 
    135183        cdef NumberFieldElement_quadratic other = <NumberFieldElement_quadratic>other_m 
    136         cdef NumberFieldElement_quadratic res = <NumberFieldElement_quadratic>self._new_c() 
    137         res.disc = self.disc 
    138         mpz_sub(res.a, self.a, other.a) 
    139         mpz_sub(res.b, self.b, other.b) 
    140         mpz_set(res.denom, self.denom) 
     184        cdef NumberFieldElement_quadratic res = <NumberFieldElement_quadratic>self._new() 
     185        cdef mpz_t gcd, tmp 
     186        res.disc = self.disc 
     187        if mpz_cmp(self.denom, other.denom) == 0: 
     188            mpz_sub(res.a, self.a, other.a) 
     189            mpz_sub(res.b, self.b, other.b) 
     190            mpz_set(res.denom, self.denom) 
     191        else: 
     192            mpz_init(gcd) 
     193            mpz_gcd(gcd, self.denom, other.denom) 
     194            if mpz_cmp_ui(gcd, 1) == 0: 
     195                mpz_mul(res.a, self.a, other.denom) 
     196                mpz_submul(res.a, self.denom, other.a) 
     197                mpz_mul(res.b, self.b, other.denom) 
     198                mpz_submul(res.b, self.denom, other.b) 
     199                mpz_mul(res.denom, self.denom, other.denom) 
     200            else: 
     201                mpz_init(tmp) 
     202                mpz_divexact(tmp, other.denom, gcd) 
     203                mpz_mul(res.a, self.a, tmp) 
     204                mpz_mul(res.b, self.b, tmp) 
     205                mpz_divexact(tmp, self.denom, gcd) 
     206                mpz_submul(res.a, other.a, tmp) 
     207                mpz_submul(res.b, other.b, tmp) 
     208                mpz_mul(res.denom, other.denom, tmp) 
     209                mpz_clear(tmp) 
     210            mpz_clear(gcd) 
    141211        res._reduce_c_() 
    142212        return res 
    143213         
    144214    def __neg__(self): 
    145         cdef NumberFieldElement_quadratic res = <NumberFieldElement_quadratic>self._new_c() 
     215        cdef NumberFieldElement_quadratic res = <NumberFieldElement_quadratic>self._new() 
    146216        res.disc = self.disc 
    147217        mpz_neg(res.a, self.a) 
    … …  
    152222    cdef RingElement _mul_c_impl(self, RingElement other_m): 
    153223        cdef NumberFieldElement_quadratic other = <NumberFieldElement_quadratic>other_m 
    154         cdef NumberFieldElement_quadratic res = <NumberFieldElement_quadratic>self._new_c() 
     224        cdef NumberFieldElement_quadratic res = <NumberFieldElement_quadratic>self._new() 
    155225        res.disc = self.disc 
    156226        cdef mpz_t tmp 
    157         mpz_init(tmp) 
    158227         
    159228        if mpz_size(self.a) + mpz_size(self.b) < 8: # could I use a macro instead? 
    160229            # Do it the traditional way 
    161             mpz_mul(res.a, self.a, other.a) 
    162             mpz_mul(tmp, self.b, other.b) 
    163             mpz_mul(tmp, tmp, self.disc.value) 
    164             mpz_add(res.a, res.a, tmp) 
     230            mpz_mul(res.a, self.b, other.b) 
     231            mpz_mul(res.a, res.a, self.disc.value) 
     232            mpz_addmul(res.a, self.a, other.a) 
    165233             
    166234            mpz_mul(res.b, self.a, other.b) 
    167             mpz_mul(tmp, self.a, other.b) 
    168             mpz_add(res.b, res.b, tmp) 
     235            mpz_addmul(res.b, self.b, other.a) 
    169236             
    170237        else: 
    171238            # Karatsuba 
    172239            _sig_on 
    173             mpz_add(res.a, self.a, other.a) # using res.a as tmp 
    174             mpz_add(tmp, self.b, other.b) 
    175             mpz_mul(res.b, res.a, tmp) # res.b = (self.a + other.a)(self.b + other.b) 
     240            mpz_init(tmp) 
     241            mpz_add(res.a, self.a, self.b) # using res.a as tmp 
     242            mpz_add(tmp, other.a, other.b) 
     243            mpz_mul(res.b, res.a, tmp) # res.b = (self.a + self.b)(other.a + other.b) 
    176244             
    177245            mpz_mul(res.a, self.a, other.a) 
    … …  
    180248            mpz_sub(res.b, res.b, tmp) 
    181249            mpz_mul(tmp, tmp, self.disc.value) 
    182             mpz_add(res.a, tmp, tmp) 
     250            mpz_add(res.a, res.a, tmp) 
     251            mpz_clear(tmp) 
    183252            _sig_off 
    184253         
    185         mpz_clear(tmp) 
    186254         
    187255        mpz_mul(res.denom, self.denom, other.denom) 
    … …  
    192260    cdef ModuleElement _rmul_c_impl(self, RingElement _c): 
    193261        cdef Rational c = <Rational>_c 
    194         cdef NumberFieldElement_quadratic res = <NumberFieldElement_quadratic>self._new_c() 
     262        cdef NumberFieldElement_quadratic res = <NumberFieldElement_quadratic>self._new() 
    195263        res.disc = self.disc 
    196264        mpz_mul(res.a, self.a, mpq_numref(c.value)) 
    … …  
    202270    cdef ModuleElement _lmul_c_impl(self, RingElement _c): 
    203271        cdef Rational c = <Rational>_c 
    204         cdef NumberFieldElement_quadratic res = <NumberFieldElement_quadratic>self._new_c() 
     272        cdef NumberFieldElement_quadratic res = <NumberFieldElement_quadratic>self._new() 
    205273        res.disc = self.disc 
    206274        mpz_mul(res.a, self.a, mpq_numref(c.value)) 
    … …  
    214282         
    215283    def __invert__(self): 
    216         cdef NumberFieldElement_quadratic res = <NumberFieldElement_quadratic>self._new_c() 
     284        cdef NumberFieldElement_quadratic res = <NumberFieldElement_quadratic>self._new() 
    217285        res.disc = self.disc 
    218286        cdef mpz_t tmp, gcd 
    … …  
    236304        # need to multiply the leftover g back in 
    237305        mpz_mul(res.denom, res.denom, gcd) 
    238              
    239         mpz_mul(res.denom, res.denom, self.denom) 
     306         
     307        mpz_mul(res.a, res.a, self.denom) 
     308        mpz_mul(res.b, res.b, self.denom) 
    240309 
    241310        mpz_clear(tmp) 
    … …  
    246315         
    247316    cdef NumberFieldElement conjugate_c(self): 
    248         cdef NumberFieldElement_quadratic res = <NumberFieldElement_quadratic>self._new_c() 
     317        cdef NumberFieldElement_quadratic res = <NumberFieldElement_quadratic>self._new() 
    249318        res.disc = self.disc 
    250319        mpz_set(res.a, self.a) 
    … …  
    290359        cdef NumberFieldElement_quadratic gen = self._parent.gen() # should this be cached?  
    291360        cdef Rational const = <Rational>PY_NEW(Rational), lin = <Rational>PY_NEW(Rational) 
     361        ad, bd = self.parts() 
    292362        if gen.is_sqrt_disc(): 
    293363            # gen = sqrt(disc) 
    294             ad, bd = self.parts() 
    295364            return [ad,bd] 
    296365        else: 

  • setup.py

    r6388 r6389  
    589589              sources = ['sage/rings/number_field/number_field_element_quadratic.pyx'], 
    590590              libraries=['gmp'], 
    591               language = 'c++'), \  # Needs c++ because it has c++ members in class struct (?) 
    592  
     591              language = 'c++'), \ 
     592                    # Needs c++ because it has c++ members in class struct 
     593   
    593594    Extension('sage.rings.number_field.number_field_base', 
    594595              sources = ['sage/rings/number_field/number_field_base.pyx']), \ 
Note: See TracChangeset for help on using the changeset viewer.