Changeset 7513:c52f4c723299


Ignore:
Timestamp:
11/16/07 04:41:41 (6 years ago)
Author:
Joel B. Mohler <jbm5@…>
Branch:
default
Message:

Rewrote hash functions for polynomial and fraction field elts to respect '=='

Location:
sage
Files:
14 edited

Legend:

Unmodified
Added
Removed

  • sage/crypto/mq/mpolynomialsystem.py

    r7066 r7513  
    685685            sage: sr = mq.SR(allow_zero_inversions=True) 
    686686            sage: F,s = sr.polynomial_system() 
    687             sage: F.variables()[:10] 
    688             [x101, x100, x103, x102, s002, w100, w101, w102, w103, k100] 
     687            sage: F.variables()[:10]  # this output ordering depends on a hash and so might change if __hash__ changes 
     688            [s000, k101, k100, s003, x102, x103, s002, w103, w102, x100]        # 32-bit 
     689            [k101, k100, s003, x102, x103, s002, w103, w102, x100, x101]        # 64-bit 
    689690        """ 
    690691        V = set() 

  • sage/rings/finite_field_ext_pari.py

    r7155 r7513  
    7979    The following is a native Python set: 
    8080        sage: set(k) 
    81         set([0, 1, 2, 2*a + 1, a + 2, 2*a, 2*a + 2, a, a + 1]) 
     81        set([0, 1, 2, a, a + 1, a + 2, 2*a, 2*a + 1, 2*a + 2]) 
    8282 
    8383    And the following is a SAGE enumerated set: 
    8484        sage: EnumeratedSet(k) 
    85          {0, 1, 2, 2*a + 1, a + 2, 2*a, 2*a + 2, a, a + 1} 
    86  
    87     We can also make a list via comprehension: 
     85        {0, 1, 2, a, a + 1, a + 2, 2*a, 2*a + 1, 2*a + 2} 
     86 
     87        We can also make a list via comprehension: 
    8888        sage: [x for x in k] 
    8989        [0, 1, 2, a, a + 1, a + 2, 2*a, 2*a + 1, 2*a + 2] 
    … …  
    592592            -586939294780423730            # 64-bit 
    593593            sage: hash(GF(9,'a')) 
    594             205387690                      # 32-bit 
    595             -8785304532306495574           # 64-bit 
     594            -417021630                     # 32-bit 
     595            1006006598732398914            # 64-bit 
    596596            sage: hash(GF(9,'b')) 
    597             -74532899                      # 32-bit 
    598             5852897890058287069            # 64-bit 
     597            995034271                      # 32-bit 
     598            8600900932991911071            # 64-bit 
    599599        """ 
    600600        return hash((self.__order, self.variable_name(), self.__modulus)) 

  • sage/rings/finite_field_givaro.pyx

    r7155 r7513  
    798798        EXAMPLES: 
    799799            sage: hash(GF(3^4, 'a')) 
    800             695660592                 # 32-bit 
    801             -4281682415996964816      # 64-bit 
     800            -417021630                # 32-bit 
     801            1006006598732398914       # 64-bit 
    802802        """ 
    803803        if self._hash is None: 

  • sage/rings/fraction_field_element.py

    r6528 r7513  
    9999    def denominator(self): 
    100100        return self.__denominator 
    101          
     101 
     102    def __hash__(self): 
     103        """ 
     104        This function hashes in a special way to ensure that generators of a ring R 
     105        and generators of a fraction field of R have the same hash.  This enables them  
     106        to be used as keys interchangably in a dictionary (since \code{==} will claim them equal).   
     107        This is particularly useful for methods like subs on \code{ParentWithGens} if you  
     108        are passing a dictionary of substitutions. 
     109 
     110        EXAMPLES: 
     111            sage: R.<x>=ZZ[] 
     112            sage: hash(R.0)==hash(FractionField(R).0) 
     113            True 
     114            sage: ((x+1)/(x^2+1)).subs({x:1}) 
     115            1 
     116            sage: d={x:1} 
     117            sage: d[FractionField(R).0] 
     118            1 
     119            sage: R.<x>=QQ[] # this probably has a separate implementation from ZZ[] 
     120            sage: hash(R.0)==hash(FractionField(R).0) 
     121            True 
     122            sage: d={x:1} 
     123            sage: d[FractionField(R).0] 
     124            1 
     125            sage: R.<x,y,z>=ZZ[] # this probably has a separate implementation from ZZ[] 
     126            sage: hash(R.0)==hash(FractionField(R).0) 
     127            True 
     128            sage: d={x:1} 
     129            sage: d[FractionField(R).0] 
     130            1 
     131            sage: R.<x,y,z>=QQ[] # this probably has a separate implementation from ZZ[] 
     132            sage: hash(R.0)==hash(FractionField(R).0) 
     133            True 
     134            sage: ((x+1)/(x^2+1)).subs({x:1}) 
     135            1 
     136            sage: d={x:1} 
     137            sage: d[FractionField(R).0] 
     138            1 
     139            sage: hash(R(1)/R(2))==hash(1/2) 
     140            True 
     141        """ 
     142        # This is same algorithm as used for members of QQ 
     143        #cdef long n, d 
     144        n = hash(self.__numerator) 
     145        d = hash(self.__denominator) 
     146        if d == 1: 
     147            return n 
     148        n = n ^ d 
     149        if n == -1: 
     150            return -2 
     151        return n 
     152 
    102153    def partial_fraction_decomposition(self): 
    103154        """ 

  • sage/rings/ideal.py

    r6646 r7513  
    7777        sage: i = ideal(1,t,t^2) 
    7878        sage: i 
    79         Ideal (t, 1, t^2) of Univariate Polynomial Ring in t over Integer Ring 
     79        Ideal (t^2, 1, t) of Univariate Polynomial Ring in t over Integer Ring 
    8080        sage: ideal(1/2,t,t^2) 
    8181        Principal ideal (1) of Univariate Polynomial Ring in t over Rational Field 

  • sage/rings/polynomial/multi_polynomial.pxd

    r4451 r7513  
    22 
    33cdef class MPolynomial(CommutativeRingElement): 
    4     pass 
     4    cdef long _hash_c(self) 

  • sage/rings/polynomial/multi_polynomial.pyx

    r6606 r7513  
    254254                D[ETuple(tmp)] = a 
    255255            return D 
    256                      
    257              
    258              
     256 
     257    cdef long _hash_c(self): 
     258        """ 
     259        This hash incorporates the variable name in an effort to respect the obvious inclusions  
     260        into multi-variable polynomial rings. 
     261 
     262        The tuple algorithm is borrowed from http://effbot.org/zone/python-hash.htm. 
     263 
     264        EXAMPLES: 
     265            sage: T.<y>=QQ[] 
     266            sage: R.<x>=ZZ[] 
     267            sage: S.<x,y>=ZZ[] 
     268            sage: hash(S.0)==hash(R.0)  # respect inclusions into mpoly rings (with matching base rings) 
     269            True 
     270            sage: hash(S.1)==hash(T.0)  # respect inclusions into mpoly rings (with unmatched base rings) 
     271            True 
     272            sage: hash(S(12))==hash(12)  # respect inclusions of the integers into an mpoly ring 
     273            True 
     274            sage: # the point is to make for more flexible dictionary look ups 
     275            sage: d={S.0:12} 
     276            sage: d[R.0] 
     277            12 
     278            sage: # or, more to the point, make subs in fraction field elements work 
     279            sage: f=x/y 
     280            sage: f.subs({x:1}) 
     281            1/y 
     282        """ 
     283        cdef long result = 0 # store it in a c-int and just let the overflowing additions wrap 
     284        cdef long result_mon 
     285        var_name_hash = [hash(v) for v in self._parent.variable_names()] 
     286        cdef long c_hash 
     287        for m,c in self.dict().iteritems(): 
     288            #  I'm assuming (incorrectly) that hashes of zero indicate that the element is 0. 
     289            # This assumption is not true, but I think it is true enough for the purposes and it  
     290            # it allows us to write fast code that omits terms with 0 coefficients.  This is  
     291            # important if we want to maintain the '==' relationship with sparse polys. 
     292            c_hash = hash(c) 
     293            if c_hash != 0: # this is always going to be true, because we are sparse (correct?) 
     294                # Hash (self[i], gen_a, exp_a, gen_b, exp_b, gen_c, exp_c, ...) as a tuple according to the algorithm. 
     295                # I omit gen,exp pairs where the exponent is zero. 
     296                result_mon = c_hash 
     297                for p in m.nonzero_positions(): 
     298                    result_mon = (1000003 * result_mon) ^ var_name_hash[p] 
     299                    result_mon = (1000003 * result_mon) ^ m[p] 
     300                result += result_mon 
     301        if result == -1: 
     302            return -2 
     303        return result 
     304 
     305    # you may have to replicate this boilerplate code in derived classes if you override  
     306    # __richcmp__.  The python documentation at  http://docs.python.org/api/type-structs.html  
     307    # explains how __richcmp__, __hash__, and __cmp__ are tied together. 
     308    def __hash__(self): 
     309        return self._hash_c() 
    259310 
    260311cdef remove_from_tuple(e, int ind): 

  • sage/rings/polynomial/multi_polynomial_element.py

    r7226 r7513  
    896896        else: 
    897897            return False 
    898  
    899     def __hash__(self): 
    900         #requires base field elements are hashable! 
    901         return hash(tuple(self._MPolynomial_element__element.dict().items())) 
    902898 
    903899    def lm(self): 

  • sage/rings/polynomial/multi_polynomial_ideal.py

    r7138 r7513  
    13081308            sage: I = sage.rings.ideal.Katsura(P,3) # regenerate to prevent caching 
    13091309            sage: I.groebner_basis('toy:buchberger') 
    1310             [-30*c^4 + 100/7*c^3 - 5/14*c^2 - 5/14*c, -2*b^2 - b*c + 1/2*b, -7/125*b - 42/25*c^3 + 79/125*c^2 - 3/125*c, 
    1311             a + 2*b + 2*c - 1, a^2 - a + 2*b^2 + 2*c^2, -5*b*c + 1/2*b - 6*c^2 + 2*c, 2*a*b + 2*b*c - b] 
    1312              
     1310            [a + 2*b + 2*c - 1, -6*b^2 - 8*b*c + 2*b - 6*c^2 + 2*c, 2*a*b + 2*b*c - b, 7/250*b + 21/25*c^3 - 79/250*c^2 + 3/250*c, a^2 - a + 2*b^2 + 2*c^2, -5/3*b*c + 1/6*b - 2*c^2 + 2/3*c, -30*c^4 + 100/7*c^3 - 5/14*c^2 - 5/14*c] 
     1311 
    13131312            sage: I = sage.rings.ideal.Katsura(P,3) # regenerate to prevent caching 
    13141313            sage: I.groebner_basis('toy:buchberger2') 
    1315             [30*c^4 - 100/7*c^3 + 5/14*c^2 + 5/14*c, a + 2*b + 2*c - 1,  
    1316              7/125*b + 42/25*c^3 - 79/125*c^2 + 3/125*c, a^2 - a + 2*b^2 + 2*c^2] 
     1314            [a + 2*b + 2*c - 1, a^2 - a + 2*b^2 + 2*c^2, 30*c^4 - 100/7*c^3 + 5/14*c^2 + 5/14*c, -7/250*b - 21/25*c^3 + 79/250*c^2 - 3/250*c] 
    13171315 
    13181316            sage: I = sage.rings.ideal.Katsura(P,3) # regenerate to prevent caching 

  • sage/rings/polynomial/multi_polynomial_libsingular.pyx

    r7287 r7513  
    14161416        else: 
    14171417            return co.new_MP(parent, res) 
    1418              
     1418 
     1419    # you may have to replicate this boilerplate code in derived classes if you override  
     1420    # __richcmp__.  The python documentation at  http://docs.python.org/api/type-structs.html  
     1421    # explains how __richcmp__, __hash__, and __cmp__ are tied together. 
     1422    def __hash__(self): 
     1423        return self._hash_c() 
     1424 
    14191425    def __richcmp__(left, right, int op): 
    14201426        return (<Element>left)._richcmp(right, op) 
    … …  
    21672173            p = pNext(p) 
    21682174        return pd 
    2169          
     2175 
     2176    cdef long _hash_c(self): 
     2177        """ 
     2178        This hash incorporates the variable name in an effort to respect the obvious inclusions  
     2179        into multi-variable polynomial rings. 
     2180 
     2181        The tuple algorithm is borrowed from http://effbot.org/zone/python-hash.htm. 
     2182 
     2183        EXAMPLES: 
     2184            sage: R.<x>=QQ[] 
     2185            sage: S.<x,y>=QQ[] 
     2186            sage: hash(S(1/2))==hash(1/2)  # respect inclusions of the rationals 
     2187            True 
     2188            sage: hash(S.0)==hash(R.0)  # respect inclusions into mpoly rings 
     2189            True 
     2190            sage: # the point is to make for more flexible dictionary look ups 
     2191            sage: d={S.0:12} 
     2192            sage: d[R.0] 
     2193            12 
     2194        """ 
     2195        cdef poly *p 
     2196        cdef ring *r 
     2197        cdef int n 
     2198        cdef int v 
     2199        r = (<MPolynomialRing_libsingular>self._parent)._ring 
     2200        if r!=currRing: rChangeCurrRing(r) 
     2201        base = (<MPolynomialRing_libsingular>self._parent)._base 
     2202        p = self._poly 
     2203        cdef long result = 0 # store it in a c-int and just let the overflowing additions wrap 
     2204        cdef long result_mon 
     2205        var_name_hash = [hash(vn) for vn in self._parent.variable_names()] 
     2206        cdef long c_hash 
     2207        while p: 
     2208            c_hash = hash(co.si2sa(p_GetCoeff(p, r), r, base)) 
     2209            if c_hash != 0: # this is always going to be true, because we are sparse (correct?) 
     2210                # Hash (self[i], gen_a, exp_a, gen_b, exp_b, gen_c, exp_c, ...) as a tuple according to the algorithm. 
     2211                # I omit gen,exp pairs where the exponent is zero. 
     2212                result_mon = c_hash 
     2213                for v from 1 <= v <= r.N: 
     2214                    n = p_GetExp(p,v,r) 
     2215                    if n!=0: 
     2216                        result_mon = (1000003 * result_mon) ^ var_name_hash[v-1] 
     2217                        result_mon = (1000003 * result_mon) ^ n 
     2218                result += result_mon 
     2219 
     2220            p = pNext(p) 
     2221        if result == -1: 
     2222            return -2 
     2223        return result 
     2224 
    21702225    def __iter__(self): 
    21712226        """ 
    … …  
    28392894    cdef int is_constant_c(self): 
    28402895        return p_IsConstant(self._poly, (<MPolynomialRing_libsingular>self._parent)._ring) 
    2841  
    2842     def __hash__(self): 
    2843         """ 
    2844         """ 
    2845         s = p_String(self._poly, (<MPolynomialRing_libsingular>self._parent)._ring, (<MPolynomialRing_libsingular>self._parent)._ring) 
    2846         return hash(s) 
    28472896 
    28482897    def lm(MPolynomial_libsingular self): 

  • sage/rings/polynomial/polynomial_element.pxd

    r6677 r7513  
    1414    cdef CompiledPolynomialFunction _compiled 
    1515    cdef truncate_c(self, long n) 
     16    cdef long _hash_c(self) 
    1617 
    1718    # UNSAFE, only call from an inplace operator 

  • sage/rings/polynomial/polynomial_element.pyx

    r7286 r7513  
    6262 
    6363from sage.rings.integral_domain import is_IntegralDomain 
     64from sage.structure.parent_gens cimport ParentWithGens 
    6465 
    6566import polynomial_fateman 
    … …  
    481482    def __iter__(self): 
    482483        return iter(self.list()) 
    483          
     484 
     485    # you may have to replicate this boilerplate code in derived classes if you override  
     486    # __richcmp__.  The python documentation at  http://docs.python.org/api/type-structs.html  
     487    # explains how __richcmp__, __hash__, and __cmp__ are tied together. 
    484488    def __hash__(self): 
    485         if self.degree() >= 1: 
    486             return hash(tuple(self.list())) 
    487         else: 
    488             return hash(self[0]) 
    489          
     489        return self._hash_c() 
     490 
     491    cdef long _hash_c(self): 
     492        """ 
     493        This hash incorporates the variable name in an effort to respect the obvious inclusions  
     494        into multi-variable polynomial rings. 
     495 
     496        The tuple algorithm is borrowed from http://effbot.org/zone/python-hash.htm. 
     497 
     498        EXAMPLES: 
     499            sage: R.<x>=ZZ[] 
     500            sage: hash(R(1))==hash(1)  # respect inclusions of the integers 
     501            True 
     502            sage: hash(R.0)==hash(FractionField(R).0)  # respect inclusions into the fraction field 
     503            True 
     504            sage: R.<x>=QQ[] 
     505            sage: hash(R(1/2))==hash(1/2)  # respect inclusions of the rationals 
     506            True 
     507            sage: hash(R.0)==hash(FractionField(R).0)  # respect inclusions into the fraction field 
     508            True 
     509            sage: R.<x>=IntegerModRing(11)[] 
     510            sage: hash(R.0)==hash(FractionField(R).0)  # respect inclusions into the fraction field 
     511            True 
     512        """ 
     513        cdef long result = 0 # store it in a c-int and just let the overflowing additions wrap 
     514        cdef long result_mon 
     515        cdef long c_hash 
     516        cdef long var_name_hash 
     517        cdef int i 
     518        for i from 0<= i <= self.degree(): 
     519            if i == 1: 
     520                # we delay the hashing until now to not waste it one a constant poly 
     521                var_name_hash = hash((<ParentWithGens>self._parent)._names[0]) 
     522            #  I'm assuming (incorrectly) that hashes of zero indicate that the element is 0. 
     523            # This assumption is not true, but I think it is true enough for the purposes and it  
     524            # it allows us to write fast code that omits terms with 0 coefficients.  This is  
     525            # important if we want to maintain the '==' relationship with sparse polys. 
     526            c_hash = hash(self[i]) 
     527            if c_hash != 0: 
     528                if i == 0: 
     529                    result += c_hash 
     530                else: 
     531                    # Hash (self[i], generator, i) as a tuple according to the algorithm. 
     532                    result_mon = c_hash 
     533                    result_mon = (1000003 * result_mon) ^ var_name_hash 
     534                    result_mon = (1000003 * result_mon) ^ i 
     535                    result += result_mon 
     536        if result == -1: 
     537            return -2 
     538        return result 
     539 
    490540    def __float__(self): 
    491541         if self.degree() > 0: 
    … …  
    31983248    def __nonzero__(self): 
    31993249        return len(self.__coeffs) > 0 
    3200      
    3201     def __hash__(self): 
    3202         if len(self.__coeffs) > 1: 
    3203             return hash(tuple(self.__coeffs)) 
    3204         elif len(self.__coeffs) == 1: 
    3205             return hash(self[0]) 
    3206         else: 
    3207             return 0 
    3208          
     3250 
    32093251    cdef void __normalize(self): 
    32103252        x = self.__coeffs 
    … …  
    32143256            del x[n] 
    32153257            n -= 1 
    3216              
     3258 
     3259    # you may have to replicate this boilerplate code in derived classes if you override  
     3260    # __richcmp__.  The python documentation at  http://docs.python.org/api/type-structs.html  
     3261    # explains how __richcmp__, __hash__, and __cmp__ are tied together. 
     3262    def __hash__(self): 
     3263        return self._hash_c() 
     3264 
    32173265    def __richcmp__(left, right, int op): 
    32183266        return (<Element>left)._richcmp(right, op) 

  • sage/rings/polynomial/polynomial_integer_dense_ntl.pyx

    r7284 r7513  
    1818 
    1919include "../../ext/stdsage.pxi" 
    20  
    2120 
    2221from sage.rings.polynomial.polynomial_element cimport Polynomial 
    … …  
    218217               (self.parent(), self.list(), False, self.is_gen()) 
    219218 
    220          
    221219    def __getitem__(self, long n): 
    222220        r""" 

  • sage/rings/polynomial/toy_buchberger.py

    r6606 r7513  
    6666 
    6767    sage: buchberger(I) 
     68    (a + 2*b + 2*c - 1, a^2 + 2*b^2 + 2*c^2 - a) => -2*b^2 - 6*b*c - 6*c^2 + b + 2*c 
     69    G: set([a + 2*b + 2*c - 1, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c]) 
     70    <BLANKLINE> 
     71    (a^2 + 2*b^2 + 2*c^2 - a, a + 2*b + 2*c - 1) => 0 
     72    G: set([a + 2*b + 2*c - 1, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c]) 
     73    <BLANKLINE> 
     74    (a + 2*b + 2*c - 1, 2*a*b + 2*b*c - b) => -5*b*c - 6*c^2 - 63*b + 2*c 
     75    G: set([a + 2*b + 2*c - 1, 2*a*b + 2*b*c - b, -5*b*c - 6*c^2 - 63*b + 2*c, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c]) 
     76    <BLANKLINE> 
     77    (2*a*b + 2*b*c - b, a + 2*b + 2*c - 1) => 0 
     78    G: set([a + 2*b + 2*c - 1, 2*a*b + 2*b*c - b, -5*b*c - 6*c^2 - 63*b + 2*c, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c]) 
     79    <BLANKLINE> 
     80    (2*a*b + 2*b*c - b, -5*b*c - 6*c^2 - 63*b + 2*c) => -22*c^3 + 24*c^2 - 60*b - 62*c 
     81    G: set([a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c]) 
     82    <BLANKLINE> 
     83    (2*a*b + 2*b*c - b, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c) => 0 
     84    G: set([a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c]) 
     85    <BLANKLINE> 
     86    (2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a) => 0 
     87    G: set([a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c]) 
     88    <BLANKLINE> 
     89    (a + 2*b + 2*c - 1, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c) => 0 
     90    G: set([a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c]) 
     91    <BLANKLINE> 
     92    (a^2 + 2*b^2 + 2*c^2 - a, 2*a*b + 2*b*c - b) => 0 
     93    G: set([a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c]) 
     94    <BLANKLINE> 
     95    (-2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c) => 0 
     96    G: set([a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c]) 
     97    <BLANKLINE> 
     98    (a + 2*b + 2*c - 1, -5*b*c - 6*c^2 - 63*b + 2*c) => 0 
     99    G: set([a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c]) 
     100    <BLANKLINE> 
     101    (a^2 + 2*b^2 + 2*c^2 - a, -5*b*c - 6*c^2 - 63*b + 2*c) => 0 
     102    G: set([a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c]) 
     103    <BLANKLINE> 
     104    (-5*b*c - 6*c^2 - 63*b + 2*c, -22*c^3 + 24*c^2 - 60*b - 62*c) => 0 
     105    G: set([a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c]) 
     106    <BLANKLINE> 
     107    (a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c) => 0 
     108    G: set([a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c]) 
     109    <BLANKLINE> 
     110    (a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c) => 0 
     111    G: set([a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c]) 
     112    <BLANKLINE> 
     113    (-2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -22*c^3 + 24*c^2 - 60*b - 62*c) => 0 
     114    G: set([a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c]) 
     115    <BLANKLINE> 
     116    (2*a*b + 2*b*c - b, -22*c^3 + 24*c^2 - 60*b - 62*c) => 0 
     117    G: set([a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c]) 
     118    <BLANKLINE> 
     119    (a^2 + 2*b^2 + 2*c^2 - a, -22*c^3 + 24*c^2 - 60*b - 62*c) => 0 
     120    G: set([a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c]) 
     121    <BLANKLINE> 
     122    15 reductions to zero. 
     123    [a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c] 
     124 
     125    The 'improved' Buchberger algorithm in constrast only performs 3 reductions to zero: 
     126 
     127    sage: buchberger_improved(I) 
    68128    (a^2 + 2*b^2 + 2*c^2 - a, a + 2*b + 2*c - 1) => 2*b^2 + 6*b*c + 6*c^2 - b - 2*c 
    69     G: set([a^2 + 2*b^2 + 2*c^2 - a, 2*b^2 + 6*b*c + 6*c^2 - b - 2*c, a + 2*b + 2*c - 1, 2*a*b + 2*b*c - b]) 
    70     <BLANKLINE> 
    71     (a + 2*b + 2*c - 1, 2*a*b + 2*b*c - b) => -5*b*c - 6*c^2 - 63*b + 2*c 
    72     G: set([a^2 + 2*b^2 + 2*c^2 - a, 2*b^2 + 6*b*c + 6*c^2 - b - 2*c, a + 2*b + 2*c - 1, -5*b*c - 6*c^2 - 63*b + 2*c, 2*a*b + 2*b*c - b]) 
    73     <BLANKLINE> 
    74     (a + 2*b + 2*c - 1, a^2 + 2*b^2 + 2*c^2 - a) => 0 
    75     G: set([a^2 + 2*b^2 + 2*c^2 - a, 2*b^2 + 6*b*c + 6*c^2 - b - 2*c, a + 2*b + 2*c - 1, -5*b*c - 6*c^2 - 63*b + 2*c, 2*a*b + 2*b*c - b]) 
    76     <BLANKLINE> 
    77     (2*a*b + 2*b*c - b, a + 2*b + 2*c - 1) => 0 
    78     G: set([a^2 + 2*b^2 + 2*c^2 - a, 2*b^2 + 6*b*c + 6*c^2 - b - 2*c, a + 2*b + 2*c - 1, -5*b*c - 6*c^2 - 63*b + 2*c, 2*a*b + 2*b*c - b]) 
    79     <BLANKLINE> 
    80     (2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a) => -61*c^3 + 55*c^2 + 53*b + 59*c 
    81     G: set([-5*b*c - 6*c^2 - 63*b + 2*c, -61*c^3 + 55*c^2 + 53*b + 59*c, 2*b^2 + 6*b*c + 6*c^2 - b - 2*c, a^2 + 2*b^2 + 2*c^2 - a, a + 2*b + 2*c - 1, 2*a*b + 2*b*c - b]) 
    82     <BLANKLINE> 
    83     (a^2 + 2*b^2 + 2*c^2 - a, 2*a*b + 2*b*c - b) => 0 
    84     G: set([-5*b*c - 6*c^2 - 63*b + 2*c, -61*c^3 + 55*c^2 + 53*b + 59*c, 2*b^2 + 6*b*c + 6*c^2 - b - 2*c, a^2 + 2*b^2 + 2*c^2 - a, a + 2*b + 2*c - 1, 2*a*b + 2*b*c - b]) 
    85     <BLANKLINE> 
    86     (2*a*b + 2*b*c - b, -5*b*c - 6*c^2 - 63*b + 2*c) => 0 
    87     G: set([-5*b*c - 6*c^2 - 63*b + 2*c, -61*c^3 + 55*c^2 + 53*b + 59*c, 2*b^2 + 6*b*c + 6*c^2 - b - 2*c, a^2 + 2*b^2 + 2*c^2 - a, a + 2*b + 2*c - 1, 2*a*b + 2*b*c - b]) 
    88     <BLANKLINE> 
    89     (2*b^2 + 6*b*c + 6*c^2 - b - 2*c, -5*b*c - 6*c^2 - 63*b + 2*c) => 0 
    90     G: set([-5*b*c - 6*c^2 - 63*b + 2*c, -61*c^3 + 55*c^2 + 53*b + 59*c, 2*b^2 + 6*b*c + 6*c^2 - b - 2*c, a^2 + 2*b^2 + 2*c^2 - a, a + 2*b + 2*c - 1, 2*a*b + 2*b*c - b]) 
    91     <BLANKLINE> 
    92     (2*a*b + 2*b*c - b, 2*b^2 + 6*b*c + 6*c^2 - b - 2*c) => 0 
    93     G: set([-5*b*c - 6*c^2 - 63*b + 2*c, -61*c^3 + 55*c^2 + 53*b + 59*c, 2*b^2 + 6*b*c + 6*c^2 - b - 2*c, a^2 + 2*b^2 + 2*c^2 - a, a + 2*b + 2*c - 1, 2*a*b + 2*b*c - b]) 
    94     <BLANKLINE> 
    95     (a + 2*b + 2*c - 1, -5*b*c - 6*c^2 - 63*b + 2*c) => 0 
    96     G: set([-5*b*c - 6*c^2 - 63*b + 2*c, -61*c^3 + 55*c^2 + 53*b + 59*c, 2*b^2 + 6*b*c + 6*c^2 - b - 2*c, a^2 + 2*b^2 + 2*c^2 - a, a + 2*b + 2*c - 1, 2*a*b + 2*b*c - b]) 
    97     <BLANKLINE> 
    98     (a + 2*b + 2*c - 1, 2*b^2 + 6*b*c + 6*c^2 - b - 2*c) => 0 
    99     G: set([-5*b*c - 6*c^2 - 63*b + 2*c, -61*c^3 + 55*c^2 + 53*b + 59*c, 2*b^2 + 6*b*c + 6*c^2 - b - 2*c, a^2 + 2*b^2 + 2*c^2 - a, a + 2*b + 2*c - 1, 2*a*b + 2*b*c - b]) 
    100     <BLANKLINE> 
    101     (-5*b*c - 6*c^2 - 63*b + 2*c, -61*c^3 + 55*c^2 + 53*b + 59*c) => 0 
    102     G: set([-5*b*c - 6*c^2 - 63*b + 2*c, -61*c^3 + 55*c^2 + 53*b + 59*c, 2*b^2 + 6*b*c + 6*c^2 - b - 2*c, a^2 + 2*b^2 + 2*c^2 - a, a + 2*b + 2*c - 1, 2*a*b + 2*b*c - b]) 
    103     <BLANKLINE> 
    104     (a^2 + 2*b^2 + 2*c^2 - a, -5*b*c - 6*c^2 - 63*b + 2*c) => 0 
    105     G: set([-5*b*c - 6*c^2 - 63*b + 2*c, -61*c^3 + 55*c^2 + 53*b + 59*c, 2*b^2 + 6*b*c + 6*c^2 - b - 2*c, a^2 + 2*b^2 + 2*c^2 - a, a + 2*b + 2*c - 1, 2*a*b + 2*b*c - b]) 
    106     <BLANKLINE> 
    107     (a^2 + 2*b^2 + 2*c^2 - a, 2*b^2 + 6*b*c + 6*c^2 - b - 2*c) => 0 
    108     G: set([-5*b*c - 6*c^2 - 63*b + 2*c, -61*c^3 + 55*c^2 + 53*b + 59*c, 2*b^2 + 6*b*c + 6*c^2 - b - 2*c, a^2 + 2*b^2 + 2*c^2 - a, a + 2*b + 2*c - 1, 2*a*b + 2*b*c - b]) 
    109     <BLANKLINE> 
    110     (a + 2*b + 2*c - 1, -61*c^3 + 55*c^2 + 53*b + 59*c) => 0 
    111     G: set([-5*b*c - 6*c^2 - 63*b + 2*c, -61*c^3 + 55*c^2 + 53*b + 59*c, 2*b^2 + 6*b*c + 6*c^2 - b - 2*c, a^2 + 2*b^2 + 2*c^2 - a, a + 2*b + 2*c - 1, 2*a*b + 2*b*c - b]) 
    112     <BLANKLINE> 
    113     (2*a*b + 2*b*c - b, -61*c^3 + 55*c^2 + 53*b + 59*c) => 0 
    114     G: set([-5*b*c - 6*c^2 - 63*b + 2*c, -61*c^3 + 55*c^2 + 53*b + 59*c, 2*b^2 + 6*b*c + 6*c^2 - b - 2*c, a^2 + 2*b^2 + 2*c^2 - a, a + 2*b + 2*c - 1, 2*a*b + 2*b*c - b]) 
    115     <BLANKLINE> 
    116     (a^2 + 2*b^2 + 2*c^2 - a, -61*c^3 + 55*c^2 + 53*b + 59*c) => 0 
    117     G: set([-5*b*c - 6*c^2 - 63*b + 2*c, -61*c^3 + 55*c^2 + 53*b + 59*c, 2*b^2 + 6*b*c + 6*c^2 - b - 2*c, a^2 + 2*b^2 + 2*c^2 - a, a + 2*b + 2*c - 1, 2*a*b + 2*b*c - b]) 
    118     <BLANKLINE> 
    119     (2*b^2 + 6*b*c + 6*c^2 - b - 2*c, -61*c^3 + 55*c^2 + 53*b + 59*c) => 0 
    120     G: set([-5*b*c - 6*c^2 - 63*b + 2*c, -61*c^3 + 55*c^2 + 53*b + 59*c, 2*b^2 + 6*b*c + 6*c^2 - b - 2*c, a^2 + 2*b^2 + 2*c^2 - a, a + 2*b + 2*c - 1, 2*a*b + 2*b*c - b]) 
    121     <BLANKLINE> 
    122     15 reductions to zero. 
    123     [-5*b*c - 6*c^2 - 63*b + 2*c, -61*c^3 + 55*c^2 + 53*b + 59*c, 2*b^2 + 6*b*c + 6*c^2 - b - 2*c, a^2 + 2*b^2 + 2*c^2 - a, a + 2*b + 2*c - 1, 2*a*b + 2*b*c - b] 
    124  
    125     The 'improved' Buchberger algorithm in constrast only performs 3 reductions to zero: 
    126  
    127     sage: buchberger_improved(I) 
    128     (2*a*b + 2*b*c - b, a + 2*b + 2*c - 1) => -2*b^2 - b*c - 63*b 
    129     G: set([a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - b*c - 63*b, a + 2*b + 2*c - 1, 2*a*b + 2*b*c - b]) 
    130     <BLANKLINE> 
    131     (a^2 + 2*b^2 + 2*c^2 - a, a + 2*b + 2*c - 1) => 5*b*c + 6*c^2 + 63*b - 2*c 
    132     G: set([5*b*c + 6*c^2 + 63*b - 2*c, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - b*c - 63*b, a + 2*b + 2*c - 1, 2*a*b + 2*b*c - b]) 
    133     <BLANKLINE> 
    134     (-2*b^2 - b*c - 63*b, 2*a*b + 2*b*c - b) => 0 
    135     G: set([5*b*c + 6*c^2 + 63*b - 2*c, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - b*c - 63*b, a + 2*b + 2*c - 1, 2*a*b + 2*b*c - b]) 
    136     <BLANKLINE> 
    137     (5*b*c + 6*c^2 + 63*b - 2*c, -2*b^2 - b*c - 63*b) => -11*c^3 + 12*c^2 - 30*b - 31*c 
    138     G: set([-11*c^3 + 12*c^2 - 30*b - 31*c, a^2 + 2*b^2 + 2*c^2 - a, 5*b*c + 6*c^2 + 63*b - 2*c, a + 2*b + 2*c - 1, -2*b^2 - b*c - 63*b, 2*a*b + 2*b*c - b]) 
    139     <BLANKLINE> 
    140     (5*b*c + 6*c^2 + 63*b - 2*c, 2*a*b + 2*b*c - b) => 0 
    141     G: set([-11*c^3 + 12*c^2 - 30*b - 31*c, a^2 + 2*b^2 + 2*c^2 - a, 5*b*c + 6*c^2 + 63*b - 2*c, a + 2*b + 2*c - 1, -2*b^2 - b*c - 63*b, 2*a*b + 2*b*c - b]) 
    142     <BLANKLINE> 
    143     (-11*c^3 + 12*c^2 - 30*b - 31*c, 5*b*c + 6*c^2 + 63*b - 2*c) => 0 
    144     G: set([-11*c^3 + 12*c^2 - 30*b - 31*c, a^2 + 2*b^2 + 2*c^2 - a, 5*b*c + 6*c^2 + 63*b - 2*c, a + 2*b + 2*c - 1, -2*b^2 - b*c - 63*b, 2*a*b + 2*b*c - b]) 
     129    G: set([a + 2*b + 2*c - 1, 2*a*b + 2*b*c - b, 2*b^2 + 6*b*c + 6*c^2 - b - 2*c, a^2 + 2*b^2 + 2*c^2 - a]) 
     130    <BLANKLINE> 
     131    (2*a*b + 2*b*c - b, a + 2*b + 2*c - 1) => 5*b*c + 6*c^2 + 63*b - 2*c 
     132    G: set([a + 2*b + 2*c - 1, 2*a*b + 2*b*c - b, 2*b^2 + 6*b*c + 6*c^2 - b - 2*c, a^2 + 2*b^2 + 2*c^2 - a, 5*b*c + 6*c^2 + 63*b - 2*c]) 
     133    <BLANKLINE> 
     134    (5*b*c + 6*c^2 + 63*b - 2*c, 2*a*b + 2*b*c - b) => 22*c^3 - 24*c^2 + 60*b + 62*c 
     135    G: set([a + 2*b + 2*c - 1, 2*b^2 + 6*b*c + 6*c^2 - b - 2*c, 5*b*c + 6*c^2 + 63*b - 2*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, 22*c^3 - 24*c^2 + 60*b + 62*c]) 
     136    <BLANKLINE> 
     137    (2*b^2 + 6*b*c + 6*c^2 - b - 2*c, 2*a*b + 2*b*c - b) => 0 
     138    G: set([a + 2*b + 2*c - 1, 2*b^2 + 6*b*c + 6*c^2 - b - 2*c, 5*b*c + 6*c^2 + 63*b - 2*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, 22*c^3 - 24*c^2 + 60*b + 62*c]) 
     139    <BLANKLINE> 
     140    (5*b*c + 6*c^2 + 63*b - 2*c, 2*b^2 + 6*b*c + 6*c^2 - b - 2*c) => 0 
     141    G: set([a + 2*b + 2*c - 1, 2*b^2 + 6*b*c + 6*c^2 - b - 2*c, 5*b*c + 6*c^2 + 63*b - 2*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, 22*c^3 - 24*c^2 + 60*b + 62*c]) 
     142    <BLANKLINE> 
     143    (22*c^3 - 24*c^2 + 60*b + 62*c, 5*b*c + 6*c^2 + 63*b - 2*c) => 0 
     144    G: set([a + 2*b + 2*c - 1, 2*b^2 + 6*b*c + 6*c^2 - b - 2*c, 5*b*c + 6*c^2 + 63*b - 2*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, 22*c^3 - 24*c^2 + 60*b + 62*c]) 
    145145    <BLANKLINE> 
    146146    3 reductions to zero. 
    147     [-11*c^3 + 12*c^2 - 30*b - 31*c, a^2 + 2*b^2 + 2*c^2 - a, 5*b*c + 6*c^2 + 63*b - 2*c, a + 2*b + 2*c - 1, -2*b^2 - b*c - 63*b, 2*a*b + 2*b*c - b] 
     147    [a + 2*b + 2*c - 1, 2*b^2 + 6*b*c + 6*c^2 - b - 2*c, 5*b*c + 6*c^2 + 63*b - 2*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, 22*c^3 - 24*c^2 + 60*b + 62*c] 
    148148 
    149149AUTHOR: 
Note: See TracChangeset for help on using the changeset viewer.