Changeset 1955:64d44aa1f88d


Ignore:
Timestamp:
11/25/06 11:00:18 (6 years ago)
Author:
Martin Albrecht <malb@…>
Branch:
default
Message:

a tiny speed-up and caching for Givaro

Location:
sage/rings
Files:
2 edited

Legend:

Unmodified
Added
Removed

  • sage/rings/finite_field.py

    r1709 r1955  
    6363 
    6464#_objsFiniteField = {} 
    65 def FiniteField(order, name='a', modulus=None): 
     65def FiniteField(order, name='a', modulus=None, cache=False): 
    6666    """ 
    6767    Return a finite field of given order with generator labeled by the given name. 
    … …  
    7272        modulus -- defining polynomial for field, i.e., generator of the field will 
    7373                   be a root of this polynomial. 
     74        cache -- cache all elements to avoid creation time  (default:False) 
    7475 
    7576    EXAMPLES: 
    … …  
    9495    else: 
    9596        if order < 2**16: 
    96             R = FiniteField_givaro(order, name, modulus)  
     97            R = FiniteField_givaro(order, name, modulus, cache=cache)  
    9798        else: 
    9899            R = FiniteField_ext_pari(order, name, modulus)  

  • sage/rings/finite_field_givaro.pyx

    r1954 r1955  
    4848from sage.libs.pari.gen import gen 
    4949 
     50cdef extern from "stdlib.h": 
     51    ctypedef int size_t  
     52    void free(void *ptr) 
     53    void *malloc(size_t size) 
     54    void *realloc(void *ptr, size_t size) 
     55    size_t strlen(char *s) 
     56    char *strcpy(char *dest, char *src) 
     57 
    5058## cdef extern from 'interrupt.h': 
    5159##     int _sig_on, _sig_off, _sig_check 
    … …  
    5664 
    5765cdef class FiniteField_givaro(FiniteField) #forward declaration 
     66 
     67 
    5868 
    5969cdef extern from "Python.h": 
    … …  
    135145    cdef int repr 
    136146 
    137     def __init__(FiniteField_givaro self, q, name="a",  modulus=None, repr="poly"): 
     147    def __init__(FiniteField_givaro self, q, name="a",  modulus=None, repr="poly", cache=False): 
    138148        """ 
    139149        Finite Field. These are implemented using Zech logs and the 
    … …  
    154164                     'int': repr is element.int_repr() 
    155165                     'poly': repr is element.poly_repr() 
     166            cache -- if True a cache of all elements of this field is 
     167                     created. Thus, arithmetic does not create new 
     168                     elements which speeds calculations up. Also, if 
     169                     many elements are needed during a calculation 
     170                     this cache reduces the memory requirement as at 
     171                     most self.order() elements are created. (default: False) 
    156172 
    157173        OUTPUT: 
    … …  
    236252                self.objectptr = gfq_factorypk(p,k) 
    237253                _sig_off 
    238                 self._array = self.gen_array() 
     254                if cache: 
     255                    self._array = self.gen_array() 
    239256                return 
    240257             
    … …  
    250267            self.objectptr = gfq_factorypkp(p, k,cPoly) 
    251268            _sig_off 
    252             self._array = self.gen_array() 
     269            if cache: 
     270                self._array = self.gen_array() 
    253271            return 
    254272 
    … …  
    256274 
    257275    cdef gen_array(FiniteField_givaro self): 
     276        """ 
     277        Generates an array/list/tuple containing all elements of self indexed by their 
     278        power with respect to the internal generator. 
     279        """ 
    258280        cdef int i 
     281         
    259282        array = list() 
    260         for i from 0 <= i < self.order(): 
     283         
     284        for i from 0 <= i < self.order_c(): 
    261285            array.append( make_FiniteField_givaroElement(self,i) ) 
    262286        return tuple(array) 
    … …  
    265289        """ 
    266290        """ 
    267  
    268291        delete(self.objectptr) 
    269292 
    … …  
    288311        return self.cardinality() 
    289312 
     313    cdef int order_c(FiniteField_givaro self): 
     314        """ 
     315        C equivalent of self.order() 
     316        """ 
     317        return self.objectptr.cardinality() 
     318     
    290319    def __len__(self): 
    291320        """ 
    … …  
    569598         
    570599        if self.degree() == 1: 
    571             return self(primitive_root(self.order())) 
     600            return self(primitive_root(self.order_c())) 
    572601        else: 
    573602            return make_FiniteField_givaroElement(self,self.objectptr.sage_generator()) 
    … …  
    625654        if p<0: 
    626655            raise ArithmeticError, "Cannot serve negative exponent %d"%p 
    627         elif p>=self.order(): 
     656        elif p>=self.order_c(): 
    628657            raise IndexError, "p=%d must be < self.order()"%p 
    629658        _sig_on 
    … …  
    711740        from sage.rings.finite_field import FiniteField_ext_pari 
    712741        from sage.rings.finite_field import FiniteField_prime_modn 
    713         return FiniteField_ext_pari(self.cardinality(),self.variable_name(),self.polynomial()) 
     742        return FiniteField_ext_pari(self.order_c(),self.variable_name(),self.polynomial()) 
    714743         
    715744    def vector_space(FiniteField_givaroElement self): 
    … …  
    894923        return make_FiniteField_givaroElement(self,r) 
    895924 
    896     def _add(FiniteField_givaro self, int r, int l): 
    897         """ 
    898         This is the fastest way to add two Givaro finite field 
    899         elements using SAGE. Given r and l this method calculates s 
    900         such that self.gen()^s = self.gen()^r + self.gen()^l. 
    901  
    902         INPUT: 
    903             r -- int representing an exponent of self.gen() 
    904             l -- int representing an exponent of self.gen() 
    905  
    906         EXAMPLE: 
    907             sage: k.<a> = GF(2**8) 
    908             sage: k._add(int(10),int(20)) 
    909             31 
    910             sage: (a^10+a^20).log_repr() 
    911             '31' 
    912         """ 
    913         cdef int res 
    914         return self.objectptr.add(res, r , l ) 
    915  
    916     def _mul(FiniteField_givaro self, int r, int l): 
    917         """ 
    918         This is the fastest way to multiply two Givaro finite field 
    919         elements using SAGE. Given r and l this method calculates s 
    920         such that self.gen()^s = self.gen()^r * self.gen()^l. 
    921  
    922         INPUT: 
    923             r -- int representing an exponent of self.gen() 
    924             l -- int representing an exponent of self.gen() 
    925  
    926         EXAMPLE: 
    927             sage: k.<a> = GF(2**8) 
    928             sage: k._mul(int(10),int(20)) 
    929             30 
    930             sage: (a^10*a^20).log_repr() 
    931             '30' 
    932  
    933         """ 
    934         cdef int res 
    935         return self.objectptr.mul(res, r , l ) 
    936  
    937     def _div(FiniteField_givaro self, int r, int l): 
    938         """ 
    939         This is the fastest way to divide two Givaro finite field 
    940         elements using SAGE. Given r and l this method calculates s 
    941         such that self.gen()^s = self.gen()^r / self.gen()^l. 
    942  
    943         INPUT: 
    944             r -- int representing an exponent of self.gen() 
    945             l -- int representing an exponent of self.gen() 
    946  
    947         EXAMPLE: 
    948             sage: k.<a> = GF(2**8) 
    949             sage: k._div(int(10),int(20)) 
    950             245 
    951             sage: (a^10/a^20).log_repr() 
    952             '245' 
    953  
    954         """ 
    955         cdef int res 
    956         return self.objectptr.div(res, r , l ) 
    957  
    958     def _sub(FiniteField_givaro self, int r, int l): 
    959         """ 
    960         This is the fastest way to subtract two Givaro finite field 
    961         elements using SAGE. Given r and l this method calculates s 
    962         such that self.gen()^s = self.gen()^r + self.gen()^l. 
    963  
    964         INPUT: 
    965             r -- int representing an exponent of self.gen() 
    966             l -- int representing an exponent of self.gen() 
    967  
    968         EXAMPLE: 
    969             sage: k.<a> = GF(2**8) 
    970             sage: k._sub(int(10),int(20)) 
    971             31 
    972             sage: (a^10-a^20).log_repr() 
    973             '31' 
    974         """ 
    975         cdef int res 
    976         return self.objectptr.sub(res, r , l ) 
     925##     def _add(FiniteField_givaro self, int r, int l): 
     926##         """ 
     927##         This is the fastest way to add two Givaro finite field 
     928##         elements using SAGE. Given r and l this method calculates s 
     929##         such that self.gen()^s = self.gen()^r + self.gen()^l. 
     930 
     931##         INPUT: 
     932##             r -- int representing an exponent of self.gen() 
     933##             l -- int representing an exponent of self.gen() 
     934 
     935##         EXAMPLE: 
     936##             sage: k.<a> = GF(2**8) 
     937##             sage: k._add(int(10),int(20)) 
     938##             31 
     939##             sage: (a^10+a^20).log_repr() 
     940##             '31' 
     941##         """ 
     942##         cdef int res 
     943##         return self.objectptr.add(res, r , l ) 
     944 
     945##     def _mul(FiniteField_givaro self, int r, int l): 
     946##         """ 
     947##         This is the fastest way to multiply two Givaro finite field 
     948##         elements using SAGE. Given r and l this method calculates s 
     949##         such that self.gen()^s = self.gen()^r * self.gen()^l. 
     950 
     951##         INPUT: 
     952##             r -- int representing an exponent of self.gen() 
     953##             l -- int representing an exponent of self.gen() 
     954 
     955##         EXAMPLE: 
     956##             sage: k.<a> = GF(2**8) 
     957##             sage: k._mul(int(10),int(20)) 
     958##             30 
     959##             sage: (a^10*a^20).log_repr() 
     960##             '30' 
     961 
     962##         """ 
     963##         cdef int res 
     964##         return self.objectptr.mul(res, r , l ) 
     965 
     966##     def _div(FiniteField_givaro self, int r, int l): 
     967##         """ 
     968##         This is the fastest way to divide two Givaro finite field 
     969##         elements using SAGE. Given r and l this method calculates s 
     970##         such that self.gen()^s = self.gen()^r / self.gen()^l. 
     971 
     972##         INPUT: 
     973##             r -- int representing an exponent of self.gen() 
     974##             l -- int representing an exponent of self.gen() 
     975 
     976##         EXAMPLE: 
     977##             sage: k.<a> = GF(2**8) 
     978##             sage: k._div(int(10),int(20)) 
     979##             245 
     980##             sage: (a^10/a^20).log_repr() 
     981##             '245' 
     982 
     983##         """ 
     984##         cdef int res 
     985##         return self.objectptr.div(res, r , l ) 
     986 
     987##     def _sub(FiniteField_givaro self, int r, int l): 
     988##         """ 
     989##         This is the fastest way to subtract two Givaro finite field 
     990##         elements using SAGE. Given r and l this method calculates s 
     991##         such that self.gen()^s = self.gen()^r + self.gen()^l. 
     992 
     993##         INPUT: 
     994##             r -- int representing an exponent of self.gen() 
     995##             l -- int representing an exponent of self.gen() 
     996 
     997##         EXAMPLE: 
     998##             sage: k.<a> = GF(2**8) 
     999##             sage: k._sub(int(10),int(20)) 
     1000##             31 
     1001##             sage: (a^10-a^20).log_repr() 
     1002##             '31' 
     1003##         """ 
     1004##         cdef int res 
     1005##         return self.objectptr.sub(res, r , l ) 
    9771006 
    9781007    def __reduce__(FiniteField_givaro self): 
    … …  
    9871016         
    9881017        """ 
     1018        if self._array is None: 
     1019            cache = 0 
     1020        else: 
     1021            cache = 1 
     1022         
    9891023        return sage.rings.finite_field_givaro.unpickle_FiniteField_givaro, \ 
    990                (self.order(),self.variable_name(),map(int,list(self.modulus())),int(self.repr)) 
    991  
    992 def unpickle_FiniteField_givaro(order,variable_name,modulus,rep): 
     1024               (self.order_c(),self.variable_name(),map(int,list(self.modulus())),int(self.repr),cache) 
     1025 
     1026def unpickle_FiniteField_givaro(order,variable_name,modulus,rep,cache): 
    9931027    from sage.rings.arith import is_prime 
    9941028 
    … …  
    10011035     
    10021036    if not is_prime(order): 
    1003         return FiniteField_givaro(order,variable_name,modulus,rep) 
     1037        return FiniteField_givaro(order,variable_name,modulus,rep,cache=cache) 
    10041038    else: 
    1005         return FiniteField_givaro(order) 
     1039        return FiniteField_givaro(order,cache=cache) 
    10061040 
    10071041cdef class FiniteField_givaro_iterator: 
    … …  
    11011135        """ 
    11021136        #copied from finite_field_element.py 
     1137        cdef FiniteField_givaro K 
    11031138        K = (<FiniteField_givaro>self._parent) 
    11041139        if K.characteristic() == 2: 
    11051140            return True 
    1106         n = K.order() - 1 
     1141        n = K.order_c() - 1 
    11071142        a = self**(n / 2) 
    11081143        return bool(a == 1) 
    … …  
    12301265        field = (<FiniteField_givaro>self._parent).objectptr 
    12311266 
    1232         exp = exp % ((<FiniteField_givaro>self._parent).order()-1) 
     1267        exp = exp % int(field.cardinality()-1) 
    12331268         
    12341269        if field.isOne(self.object): 
    … …  
    12481283 
    12491284        return make_FiniteField_givaroElement((<FiniteField_givaro>self._parent),power) 
    1250  
    1251 ##     def add(FiniteField_givaroElement self,FiniteField_givaroElement other): 
    1252 ##         """ 
    1253 ##         """ 
    1254 ##         cdef int r 
    1255 ##         r = (<FiniteField_givaro>self._parent).objectptr.add(r, self.object , other.object ) 
    1256 ##         return make_FiniteField_givaroElement((<FiniteField_givaro>self._parent),r) 
    1257  
    1258 ##     def mul(FiniteField_givaroElement self,FiniteField_givaroElement other): 
    1259 ##         """ 
    1260 ##         """ 
    1261 ##         cdef int r 
    1262 ##         r = (<FiniteField_givaro>self._parent).objectptr.mul(r, self.object , other.object ) 
    1263 ##         return make_FiniteField_givaroElement((<FiniteField_givaro>self._parent),r) 
    1264  
    1265  
    1266 ##     def div(FiniteField_givaroElement self,FiniteField_givaroElement  other): 
    1267 ##         cdef int r 
    1268 ##         r = (<FiniteField_givaro>self._parent).objectptr.div(r, self.object , other.object ) 
    1269 ##         return make_FiniteField_givaroElement((<FiniteField_givaro>self._parent),r) 
    1270  
    1271 ##     def sub(FiniteField_givaroElement self,FiniteField_givaroElement other): 
    1272 ##         cdef int r 
    1273 ##         r = (<FiniteField_givaro>self._parent).objectptr.sub(r, self.object , other.object ) 
    1274 ##         return make_FiniteField_givaroElement((<FiniteField_givaro>self._parent),r) 
    12751285 
    12761286    def __cmp__(self, other): 
    … …  
    13471357    def log(FiniteField_givaroElement self, a): 
    13481358        #copied from finite_field_element.py 
    1349         q = (self.parent()).order() - 1 
     1359        q = (self.parent()).order_c() - 1 
    13501360        return sage.rings.arith.discrete_log_generic(self, a, q) 
    13511361 
    … …  
    14411451            if self.is_zero(): 
    14421452                return ArithmeticError, "Multiplicative order of 0 not defined." 
    1443             n = (parent_object(self)).order() - 1 
     1453            n = (parent_object(self)).order_c() - 1 
    14441454            order = 1 
    14451455            for p, e in sage.rings.arith.factor(n): 
    … …  
    14651475        """ 
    14661476        #copied from finite_field_element.py 
     1477        cdef FiniteField_givaro F 
    14671478        F = parent_object(self) 
    1468         if F.order() > 65536: 
    1469             raise TypeError, "order (=%s) must be at most 65536."%F.order() 
     1479        if F.order_c() > 65536: 
     1480            raise TypeError, "order (=%s) must be at most 65536."%F.order_c() 
    14701481        if self == 0: 
    1471             return '0*Z(%s)'%F.order() 
     1482            return '0*Z(%s)'%F.order_c() 
    14721483        assert F.degree() > 1 
    14731484        g = F.multiplicative_generator() 
    14741485        n = g.log(self) 
    1475         return 'Z(%s)^%s'%(F.order(), n) 
     1486        return 'Z(%s)^%s'%(F.order_c(), n) 
    14761487 
    14771488    def charpoly(FiniteField_givaroElement self): 
    … …  
    15621573        return parent._array[x] 
    15631574 
    1564 cdef gap_to_givaro(x, F): 
     1575cdef gap_to_givaro(x, FiniteField_givaro F): 
    15651576    """ 
    15661577    INPUT: 
    … …  
    15991610    i2 = s.index(")") 
    16001611    q  = eval(s[i1+1:i2].replace('^','**')) 
    1601     if q == F.order(): 
     1612    if q == F.order_c(): 
    16021613        K = F 
    16031614    else: 
Note: See TracChangeset for help on using the changeset viewer.