Changeset 8432:eee6353af42a


Ignore:
Timestamp:
11/11/07 14:27:50 (6 years ago)
Author:
David Roe <roed@…>
Branch:
default
Message:

Lots of changes to the PowComputer? class, added PowComputer? versions for p-adic extensions.

Location:
sage/rings/padics
Files:
4 edited

Legend:

Unmodified
Added
Removed

  • sage/rings/padics/pow_computer.pxd

    r7016 r8432  
    11include "../../ext/cdefs.pxi" 
    2 include "../../libs/ntl/decl.pxi" 
    32 
    4 cimport sage.structure.sage_object 
    53from sage.structure.sage_object cimport SageObject 
    6 cimport sage.rings.integer 
    74from sage.rings.integer cimport Integer 
    85 
    … …  
    1512    cdef unsigned long prec_cap 
    1613 
     14    cdef mpz_t temp_m 
     15 
    1716    cdef Integer pow_Integer(self, unsigned long n) 
    18     cdef mpz_t* pow_mpz_top(self) 
    19     cdef mpz_t* pow_mpz_t(self, unsigned long n) 
     17    cdef mpz_t* pow_mpz_t_top(self) 
    2018    cdef mpz_t* pow_mpz_t_tmp(self, unsigned long n) 
    21     cdef ZZ_c pow_ZZ(self, unsigned long n) 
    2219 
    2320cdef class PowComputer_base(PowComputer_class): 
    2421    cdef mpz_t* small_powers 
    2522    cdef mpz_t top_power 
    26     cdef mpz_t temp 
    2723    cdef object __weakref__ 

  • sage/rings/padics/pow_computer.pyx

    r7016 r8432  
    4343        self._initialized = 1 
    4444 
     45    def __cmp__(self, other): 
     46        """ 
     47        Compares self to other 
     48 
     49        EXAMPLES: 
     50        sage: P = PowComputer(3, 4, 9) 
     51        sage: P == 7 
     52        False 
     53        sage: Q = PowComputer(3, 6, 9) 
     54        sage: P == Q 
     55        False 
     56        sage: Q = PowComputer(3, 4, 9) 
     57        sage: P == Q 
     58        True 
     59        sage: P is Q 
     60        True 
     61        """ 
     62        a = cmp(type(self), type(other)) 
     63        cdef PowComputer_class o 
     64        if a == 0: 
     65            o = <PowComputer_class>other 
     66            if self.prime < o.prime: 
     67                return -1 
     68            elif self.prime > o.prime: 
     69                return 1 
     70            elif self.prec_cap < o.prec_cap: 
     71                return -1 
     72            elif self.prec_cap > o.prec_cap: 
     73                return 1 
     74            elif self.cache_limit < o.cache_limit: 
     75                return -1 
     76            elif self.cache_limit > o.cache_limit: 
     77                return 1 
     78            elif self.in_field < o.in_field: 
     79                return -1 
     80            elif self.in_field > o.in_field: 
     81                return 1 
     82            else: 
     83                return 0 
     84        else: 
     85            return cmp(type(self), type(other)) 
     86 
    4587    cdef Integer pow_Integer(self, unsigned long n): 
     88        """ 
     89        Returns self.prime^n 
     90        """ 
    4691        cdef Integer ans = PY_NEW(Integer) 
    47         _sig_on 
    48         mpz_pow_ui(ans.value, self.prime.value, n) 
    49         _sig_off 
    50         return ans 
    51  
    52     cdef mpz_t* pow_mpz_t(self, unsigned long n): 
     92        mpz_set(ans.value, self.pow_mpz_t_tmp(n)[0]) 
     93        return ans 
     94 
     95    def pow_Integer_Integer(self, n): 
     96        """ 
     97        Tests the pow_Integer function. 
     98 
     99        EXAMPLES: 
     100        sage: PC = PowComputer(3, 5, 10) 
     101        sage: PC.pow_Integer_Integer(4) 
     102        81 
     103        sage: PC.pow_Integer_Integer(6) 
     104        729 
     105        sage: PC.pow_Integer_Integer(0) 
     106        1 
     107        sage: PC.pow_Integer_Integer(10) 
     108        59049 
     109        sage: PC = PowComputer_ext_maker(3, 5, 10, False, ntl.ZZ_pX([-9,0,1], 3^10), "big") 
     110        sage: PC.pow_Integer_Integer(4) 
     111        81 
     112        sage: PC.pow_Integer_Integer(6) 
     113        729 
     114        sage: PC.pow_Integer_Integer(0) 
     115        1 
     116        sage: PC.pow_Integer_Integer(10) 
     117        59049 
     118        """ 
     119        cdef Integer _n = Integer(n) 
     120        cdef Integer ans 
     121        if _n < 0: 
     122            if mpz_fits_ulong_p((<Integer>-_n).value) == 0: 
     123                raise ValueError, "result too big" 
     124            return ~self.pow_Integer(mpz_get_ui((<Integer>-_n).value)) 
     125        else: 
     126            if mpz_fits_ulong_p(_n.value) == 0: 
     127                raise ValueError, "result too big" 
     128            return self.pow_Integer(mpz_get_ui(_n.value)) 
     129 
     130    cdef mpz_t* pow_mpz_t_tmp(self, unsigned long n): 
     131        """ 
     132        Provides fast access to an mpz_t* pointing to self.prime^n. 
     133 
     134        The location pointed to depends on the underlying representation. 
     135        In no circumstances should you mpz_clear the result. 
     136        The value pointed to may be an internal temporary variable for the class. 
     137        In particular, you should not try to refer to the results of two 
     138        pow_mpz_t_tmp calls at the same time, because the second 
     139        call may overwrite the memory pointed to by the first. 
     140 
     141        See pow_mpz_t_tmp_demo for an example of this phenomenon. 
     142        """ 
     143        ## READ THE DOCSTRING 
    53144        raise NotImplementedError 
    54145 
    55     cdef mpz_t* pow_mpz_t_tmp(self, unsigned long n): 
     146    def pow_mpz_t_tmp_demo(self, m, n): 
     147        """ 
     148        This function demonstrates a danger in using pow_mpz_t_tmp. 
     149 
     150        EXAMPLES: 
     151        sage: PC = PowComputer(5, 5, 10) 
     152 
     153        When you cal pow_mpz_t_tmp with an input that is not stored 
     154        (ie n > self.cache_limit and n != self.prec_cap), 
     155        it stores the result in self.temp_m and returns a pointer 
     156        to that mpz_t.  So if you try to use the results of two 
     157        calls at once, things will break. 
     158        sage: PC.pow_mpz_t_tmp_demo(6, 8) 
     159        244140625 
     160        sage: 5^6*5^8 
     161        6103515625 
     162        sage: 5^6*5^6 
     163        244140625 
     164 
     165        Note that this does not occur if you try a stored value, 
     166        because the result of one of the calls points to that 
     167        stored value. 
     168        sage: PC.pow_mpz_t_tmp_demo(6, 10) 
     169        152587890625 
     170        sage: 5^6*5^10 
     171        152587890625         
     172        """ 
     173        m = Integer(m) 
     174        n = Integer(n) 
     175        if m < 0 or n < 0: 
     176            raise ValueError, "m, n must be non-negative" 
     177        cdef Integer ans = PY_NEW(Integer) 
     178        mpz_mul(ans.value, self.pow_mpz_t_tmp(mpz_get_ui((<Integer>m).value))[0], self.pow_mpz_t_tmp(mpz_get_ui((<Integer>n).value))[0]) 
     179        return ans 
     180 
     181    def pow_mpz_t_tmp_test(self, n): 
     182        """ 
     183        Tests the pow_Integer function. 
     184 
     185        EXAMPLES: 
     186        sage: PC = PowComputer(3, 5, 10) 
     187        sage: PC.pow_mpz_t_tmp_test(4) 
     188        81 
     189        sage: PC.pow_mpz_t_tmp_test(6) 
     190        729 
     191        sage: PC.pow_mpz_t_tmp_test(0) 
     192        1 
     193        sage: PC.pow_mpz_t_tmp_test(10) 
     194        59049 
     195        sage: PC = PowComputer_ext_maker(3, 5, 10, False, ntl.ZZ_pX([-9,0,1], 3^10), "big") 
     196        sage: PC.pow_mpz_t_tmp_test(4) 
     197        81 
     198        sage: PC.pow_mpz_t_tmp_test(6) 
     199        729 
     200        sage: PC.pow_mpz_t_tmp_test(0) 
     201        1 
     202        sage: PC.pow_mpz_t_tmp_test(10) 
     203        59049 
     204        """ 
     205        cdef Integer _n = Integer(n) 
     206        cdef Integer ans = PY_NEW(Integer) 
     207        mpz_set(ans.value, self.pow_mpz_t_tmp(mpz_get_ui(_n.value))[0]) 
     208        return ans 
     209 
     210    cdef mpz_t* pow_mpz_t_top(self): 
    56211        raise NotImplementedError 
    57212 
    58     cdef ZZ_c pow_ZZ(self, unsigned long n): 
    59         raise NotImplementedError 
    60  
    61     cdef mpz_t* pow_mpz_top(self): 
    62         raise NotImplementedError 
     213    def pow_mpz_t_top_test(self): 
     214        """ 
     215        Tests the pow_mpz_t_top function. 
     216 
     217        EXAMPLES: 
     218        sage: PC = PowComputer(3, 5, 10) 
     219        sage: PC.pow_mpz_t_top_test() 
     220        59049 
     221        sage: PC = PowComputer_ext_maker(3, 5, 10, False, ntl.ZZ_pX([-9,0,1], 3^10), "big") 
     222        sage: PC.pow_mpz_t_top_test() 
     223        59049 
     224        """ 
     225        cdef Integer ans = PY_NEW(Integer) 
     226        mpz_set(ans.value, self.pow_mpz_t_top()[0]) 
     227        return ans         
     228 
     229    def __repr__(self): 
     230        """ 
     231        Returns a string representation of self. 
     232 
     233        EXAMPLES: 
     234        sage: PC = PowComputer(3, 5, 10); PC 
     235        PowComputer for 3 
     236        """ 
     237        return "PowComputer for %s"%(self.prime) 
    63238 
    64239    def _prime(self): 
    … …  
    75250    def _in_field(self): 
    76251        """ 
    77         For use by p-adic rings and fields.  Feel free to ignore if you're using a PowComputer otherwise. 
     252        Returns whether or not self is attached to a field. 
     253 
     254        EXAMPLES: 
     255        sage: P = PowComputer(3, 5, 10) 
     256        sage: P._in_field() 
     257        False 
    78258        """ 
    79259        return self.in_field 
    80260 
     261    def _cache_limit(self): 
     262        """ 
     263        Returns the limit to which powers of prime are computed. 
     264 
     265        EXAMPLES: 
     266        sage: P = PowComputer(3, 5, 10) 
     267        sage: P._cache_limit() 
     268        5 
     269        """ 
     270        cdef Integer ans 
     271        ans = PY_NEW(Integer) 
     272        mpz_set_ui(ans.value, self.cache_limit) 
     273        return ans 
     274 
     275    def _prec_cap(self): 
     276        """ 
     277        Returns prec_cap, a single value that for which self._prime()^prec_cap is stored 
     278 
     279        EXAMPLES: 
     280        sage: P = PowComputer(3, 5, 10) 
     281        sage: P._prec_cap() 
     282        10 
     283        """ 
     284        cdef Integer ans 
     285        ans = PY_NEW(Integer) 
     286        mpz_set_ui(ans.value, self.prec_cap) 
     287        return ans 
     288 
     289    def _top_power(self): 
     290        """ 
     291        Returns self._prime()^self._prec_cap() 
     292 
     293        EXAMPLES: 
     294        sage: P = PowComputer(3, 4, 6) 
     295        sage: P._top_power() 
     296        729 
     297        """ 
     298        cdef Integer ans 
     299        ans = PY_NEW(Integer) 
     300        mpz_set(ans.value, self.pow_mpz_t_top()[0]) 
     301        return ans 
     302 
    81303    def __call__(self, n): 
     304        """ 
     305        Returns self.prime^n. 
     306 
     307        EXAMPLES: 
     308        sage: P = PowComputer(3, 4, 6) 
     309        sage: P(3) 
     310        27 
     311        sage: P(6) 
     312        729 
     313        sage: P(5) 
     314        243 
     315        sage: P(7) 
     316        2187 
     317        sage: P(0) 
     318        1 
     319        sage: P(-2) 
     320        1/9 
     321        """ 
    82322        cdef Integer z, _n 
    83323        cdef mpz_t tmp 
    … …  
    88328        else: 
    89329            _n = <Integer>n 
    90         if mpz_cmp_ui(_n.value, 0) >= 0: 
    91             return self.pow_Integer(mpz_get_ui(_n.value)) 
    92         else: 
     330        if _n < 0: 
    93331            return self.prime.__pow__(_n) 
     332        if mpz_fits_ulong_p(_n.value) == 0: 
     333            raise ValueError, "n too big" 
     334        return self.pow_Integer(mpz_get_ui(_n.value)) 
    94335 
    95336cdef class PowComputer_base(PowComputer_class): 
    … …  
    102343            raise MemoryError, "out of memory allocating power storing" 
    103344        mpz_init(self.top_power) 
    104         mpz_init(self.temp) 
     345        mpz_init(self.temp_m) 
    105346         
    106347    def __init__(self, Integer prime, unsigned long cache_limit, unsigned long prec_cap, bint in_field): 
    … …  
    121362 
    122363    def __dealloc__(self): 
     364        """ 
     365        sage: P = PowComputer(5, 7, 10) 
     366        sage: del P 
     367        sage: PowComputer(5, 7, 10) 
     368        PowComputer for 5 
     369        """ 
    123370        cdef Py_ssize_t i 
    124371        if (<PowComputer_class>self)._initialized: 
    … …  
    127374            sage_free(self.small_powers) 
    128375            mpz_clear(self.top_power) 
    129             mpz_clear(self.temp) 
     376            mpz_clear(self.temp_m) 
    130377     
    131     def __cmp__(self, other): 
    132         if isinstance(other, PowComputer_base): 
    133             if self.prime < (<PowComputer_class>other).prime: 
    134                 return -1 
    135             elif self.prime > (<PowComputer_class>other).prime: 
    136                 return 1 
    137             elif self.prec_cap < (<PowComputer_base>other).prec_cap: 
    138                 return -1 
    139             elif self.prec_cap > (<PowComputer_base>other).prec_cap: 
    140                 return 1 
    141             elif self.cache_limit < (<PowComputer_base>other).cache_limit: 
    142                 return -1 
    143             elif self.cache_limit > (<PowComputer_base>other).cache_limit: 
    144                 return 1 
    145             elif self.in_field < (<PowComputer_class>other).in_field: 
    146                 return -1 
    147             elif self.in_field > (<PowComputer_class>other).in_field: 
    148                 return 1 
    149             else: 
    150                 return 0 
    151         else: 
    152             return cmp(type(self), type(other)) 
    153378 
    154379    def __reduce__(self): 
    … …  
    161386        return PowComputer, (self.prime, self.cache_limit, self.prec_cap, self.in_field) 
    162387 
    163     def _cache_limit(self): 
    164         """ 
    165         Returns the limit to which powers of prime are computed. 
    166         """ 
    167         cdef Integer ans 
    168         ans = PY_NEW(Integer) 
    169         mpz_set_ui(ans.value, self.cache_limit) 
    170         return ans 
    171  
    172     def _top_power(self): 
    173         """ 
    174         Returns self._prime()^self._prec_cap() 
    175         """ 
    176         cdef Integer ans 
    177         ans = PY_NEW(Integer) 
    178         mpz_set(ans.value, self.top_power) 
    179         return ans 
    180  
    181     def _prec_cap(self): 
    182         """ 
    183         Returns prec_cap, a single value that for which self._prime()^prec_cap is stored 
    184         """ 
    185         cdef Integer ans 
    186         ans = PY_NEW(Integer) 
    187         mpz_set_ui(ans.value, self.prec_cap) 
    188         return ans 
    189  
    190     cdef Integer pow_Integer(self, unsigned long n): 
    191         cdef Integer ans = PY_NEW(Integer) 
    192         if n <= self.cache_limit: 
    193             mpz_set(ans.value, self.small_powers[n]) 
    194         elif n == self.prec_cap: 
    195             mpz_set(ans.value, self.top_power) 
    196         else: 
    197             mpz_pow_ui(ans.value, self.prime.value, n) 
    198         return ans 
    199  
    200     cdef mpz_t* pow_mpz_top(self): 
     388    cdef mpz_t* pow_mpz_t_top(self): 
    201389        return &self.top_power 
    202390 
    203     cdef mpz_t* pow_mpz_t(self, unsigned long n): 
    204         #################### WARNING ###################### 
    205         ## If you use this function, you MAY need to     ## 
    206         ## call mpz_clear on the returned value after    ## 
    207         ## you are finished with it.  You need to do     ## 
    208         ## so if and only if (n > self.cache_limit and   ## 
    209         ## n != self.prec_cap).  So your code should     ## 
    210         ## look something like the following:            ## 
    211         ##                                               ## 
    212         ## cdef PowComputer_base ppow                    ## 
    213         ## ppow = PowComputer(5, 10, 1000)               ## 
    214         ## cdef unsigned long n = get_long_somehow()     ## 
    215         ## cdef mpz_t foo = ppow.pow_mpz_t(n)[0]         ## 
    216         ## # Do stuff with foo                           ## 
    217         ## # Now done with foo                           ## 
    218         ## if n > ppow.cache_limit and n != ppow.prec_cap## 
    219         ##     mpz_clear(foo)                            ## 
    220         ################################################### 
     391    cdef mpz_t* pow_mpz_t_tmp(self, unsigned long n): 
    221392        if n <= self.cache_limit: 
    222393            return &(self.small_powers[n]) 
    223394        if n == self.prec_cap: 
    224395            return &(self.top_power) 
    225         cdef mpz_t ans 
    226         mpz_init(ans) 
    227         mpz_pow_ui(ans, self.prime.value, n) 
    228         return &ans 
    229  
    230     cdef mpz_t* pow_mpz_t_tmp(self, unsigned long n): 
    231         ## Solves the problem noted in the above warning by storing the returned mpz_t in a temporary variable 
    232         ## Each call to this function overwrites that temporary variable. 
    233         if n <= self.cache_limit: 
    234             return &(self.small_powers[n]) 
    235         if n == self.prec_cap: 
    236             return &(self.top_power) 
    237         mpz_pow_ui(self.temp, self.prime.value, n) 
    238         return &(self.temp) 
     396        mpz_pow_ui(self.temp_m, self.prime.value, n) 
     397        return &(self.temp_m) 
    239398         
    240  
    241     cdef ZZ_c pow_ZZ(self, unsigned long n): 
    242         ## You always need to call ZZ_destruct on the return value of this function 
    243         cdef ZZ_c ans 
    244         cdef mpz_t temp 
    245         ZZ_construct(&ans) 
    246         if n <= self.cache_limit: 
    247             mpz_to_ZZ(&ans, &(self.small_powers[n])) 
    248         elif n == self.prec_cap: 
    249             mpz_to_ZZ(&ans, &self.top_power) 
    250         else: 
    251             mpz_init(temp) 
    252             mpz_pow_ui(temp, self.prime.value, n) 
    253             mpz_to_ZZ(&ans, &temp) 
    254             mpz_clear(temp) 
    255         return ans 
    256  
    257  
    258399pow_comp_cache = {} 
    259400cdef PowComputer_base PowComputer_c(Integer m, Integer cache_limit, Integer prec_cap, in_field): 
    … …  
    286427    EXAMPLES: 
    287428    sage: PC = PowComputer(3, 5, 10) 
     429    sage: PC 
     430    PowComputer for 3 
    288431    sage: PC(4) 
    289432    81 

  • sage/rings/padics/pow_computer_ext.pxd

    r7014 r8432  
    1 include "../../libs/ntl/decl.pxi"" 
     1include "../../ext/cdefs.pxi" 
     2include "../../libs/ntl/decl.pxi" 
    23 
    34from sage.rings.padics.pow_computer cimport PowComputer_class 
     5from sage.libs.ntl.ntl_ZZ_pContext cimport ntl_ZZ_pContext_class 
    46 
    57cdef class PowComputer_ext(PowComputer_class): 
    68    cdef ZZ_c* small_powers 
    7     cdef unsigned long cache_limit 
    89    cdef ZZ_c top_power 
    9     cdef unsigned long prec_cap 
     10    cdef ZZ_c temp_z 
     11 
     12    # the following three should be set by the subclasses 
     13    cdef long ram_prec_cap # = prec_cap * e 
     14    cdef long deg 
     15    cdef long e 
     16    cdef long f 
     17 
     18    cdef ZZ_c* pow_ZZ_tmp(self, unsigned long n) 
     19    cdef ZZ_c* pow_ZZ_top(self) 
     20 
     21    cdef void cleanup_ext(self) 
    1022 
    1123cdef class PowComputer_ZZ_pX(PowComputer_ext): 
    12     cdef ntl_ZZ_pContext get_context(self, unsigned long n) 
    13     cdef ntl_ZZ_pContext get_top_context(self) 
    14     cdef void restore_context(self, unsigned long n) 
     24    cdef ntl_ZZ_pContext_class get_context(self, unsigned long n) 
     25    cdef ntl_ZZ_pContext_class get_top_context(self) 
     26    cdef restore_context(self, unsigned long n) 
    1527    cdef void restore_top_context(self) 
    16     cdef ZZ_pX_Modulus_c get_modulus(self, unsigned long n) 
    17     cdef ZZ_pX_Modulus_c get_top_modulus(self) 
     28    cdef ZZ_pX_Modulus_c* get_modulus(self, unsigned long n) 
     29    cdef ZZ_pX_Modulus_c* get_top_modulus(self) 
    1830 
    1931cdef class PowComputer_ZZ_pX_FM(PowComputer_ZZ_pX): 
    20     cdef ZZ_pX_c poly 
    21     cdef ntl_ZZ_pContext c 
     32    #cdef ZZ_pX_c poly 
     33    cdef ntl_ZZ_pContext_class c 
    2234    cdef ZZ_pX_Modulus_c mod 
    2335 
     36    cdef void cleanup_ZZ_pX_FM(self) 
     37 
    2438cdef class PowComputer_ZZ_pX_FM_Eis(PowComputer_ZZ_pX_FM): 
     39    cdef int low_length 
     40    cdef int high_length 
     41    cdef ZZ_pX_Multiplier_c* low_shifter 
     42    cdef ZZ_pX_Multiplier_c* high_shifter 
     43 
     44    cdef void cleanup_ZZ_pX_FM_Eis(self) 
     45 
     46cdef class PowComputer_ZZ_pX_small(PowComputer_ZZ_pX): 
     47    cdef object c # using a python list so that we can store ntl_ZZ_pContext_class objects 
     48    cdef ZZ_pX_Modulus_c *mod 
     49 
     50    cdef void cleanup_ZZ_pX_small(self) 
     51 
     52cdef class PowComputer_ZZ_pX_small_Eis(PowComputer_ZZ_pX_small): 
    2553    pass 
    2654 
    27 #cdef class PowComputer_ZZ_pX_small(PowComputer_ZZ_pX): 
    28 #    cdef ZZ_pX_c *poly 
    29 #    cdef ntl_ZZ_pContext *c 
    30 #    cdef ZZ_pX_Modulus_c *mod 
    31 # 
    32 #cdef class PowComputer_ZZ_pX_small_Eis(PowComputer_ZZ_pX_small): 
    33 #    pass 
    34 # 
    35 #cdef class PowComputer_ZZ_pX_big(PowComputer_ZZ_pX): 
    36 #    cdef ZZX_c poly 
    37 #    cdef context_dict #currently using a dict, optimize for speed later 
    38 #    cdef modulus_dict #currently using a dict, optimize for speed later 
    39 # 
    40 #cdef class PowComputer_ZZ_pX_big_Eis(PowComputer_ZZ_pX_big): 
    41 #    pass 
    42 # 
     55cdef class PowComputer_ZZ_pX_big(PowComputer_ZZ_pX): 
     56    cdef object context_list # using a python list so that we can store ntl_ZZ_pContext_class objects 
     57    cdef ZZ_pX_Modulus_c *modulus_list 
     58 
     59    cdef ntl_ZZ_pContext_class top_context 
     60    cdef ZZ_pX_Modulus_c top_mod 
     61 
     62    cdef object context_dict #currently using a dict, optimize for speed later 
     63    cdef object modulus_dict #currently using a dict, optimize for speed later 
     64 
     65    cdef void cleanup_ZZ_pX_big(self) 
     66 
     67cdef class PowComputer_ZZ_pX_big_Eis(PowComputer_ZZ_pX_big): 
     68    pass 
     69 
    4370#cdef class PowComputer_ZZ_pEX(PowComputer_ext): 
    4471#    cdef ntl_ZZ_pEContext get_context(self, unsigned long n) 

  • sage/rings/padics/pow_computer_ext.pyx

    r7017 r8432  
    1 from sage.rings.integer cimport Integer 
    2  
    31""" 
    42AUTHOR: 
    … …  
    1513#***************************************************************************** 
    1614 
    17  
    18  
    19 import weakref 
    20 from sage.rings.infinity import infinity 
    21 from sage.libs.ntl.ntl_ZZ_pContext import ntl_ZZ_pContext, ntl_ZZ_pContext_class 
    22 from sage.libs.ntl.ntl_ZZ import ntl_ZZ 
    23  
    24 #from sage.rings.integer import Integer 
    25  
    2615include "../../ext/gmp.pxi" 
    2716include "../../ext/interrupt.pxi" 
    2817include "../../ext/stdsage.pxi" 
     18include "../../ext/python_list.pxi" 
     19include "../../ext/python_dict.pxi" 
     20 
     21import weakref 
     22from sage.misc.misc import cputime 
     23from sage.rings.infinity import infinity 
     24from sage.libs.ntl.ntl_ZZ_pContext cimport ntl_ZZ_pContext_factory 
     25from sage.libs.ntl.ntl_ZZ_pContext import ZZ_pContext_factory 
     26from sage.libs.ntl.ntl_ZZ cimport ntl_ZZ 
     27from sage.libs.ntl.ntl_ZZ_pX cimport ntl_ZZ_pX, ntl_ZZ_pX_Modulus 
     28from sage.rings.integer cimport Integer 
    2929 
    3030cdef class PowComputer_ext(PowComputer_class): 
    3131    def __new__(self, Integer prime, unsigned long cache_limit, unsigned long prec_cap, bint in_field, poly): 
    32         (<PowComputer_class>self)._initialized = 0 
     32        """ 
     33        Constructs the storage for powers of prime as ZZ_c's. 
     34 
     35        EXAMPLES: 
     36        sage: PC = PowComputer_ext_maker(5, 10, 10, False, ntl.ZZ_pX([-5, 0, 1], 5^10), "small") #indirect doctest 
     37        """ 
     38        self._initialized = 0 
    3339        _sig_on 
    3440        self.small_powers = <ZZ_c *>sage_malloc(sizeof(ZZ_c) * (cache_limit + 1)) 
    … …  
    4147        cdef Integer x 
    4248 
    43         self.cache_limit = cache_limit 
    44         self.prec_cap = prec_cap 
    45  
    4649        ZZ_construct(self.small_powers) 
    47         ZZ_conv_int(self.small_powers[0], 1) 
     50        ZZ_conv_from_int(self.small_powers[0], 1) 
    4851 
    4952        if cache_limit > 0: 
    … …  
    5457        for i from 2 <= i <= cache_limit: 
    5558            ZZ_construct(&(self.small_powers[i])) 
    56             mul_ZZ(self.small_powers[i], self.small_powers[i-1], self.small_powers[1]) 
     59            ZZ_mul(self.small_powers[i], self.small_powers[i-1], self.small_powers[1]) 
    5760        mpz_to_ZZ(&self.top_power, &prime.value) 
    58         power_ZZ(self.top_power, self.top_power, prec_cap) 
     61        ZZ_power(self.top_power, self.top_power, prec_cap) 
    5962        _sig_off 
    60  
     63        mpz_init(self.temp_m) 
     64        ZZ_construct(&self.temp_z) 
    6165 
    6266    def __init__(self, Integer prime, unsigned long cache_limit, unsigned long prec_cap, bint in_field, poly): 
    63         PowComputer_class.__init__(self, prime, in_field) 
     67        """ 
     68        Initializes prime, cache_limit, prec_cap, in_field. 
     69 
     70        EXAMPLES: 
     71        sage: PC = PowComputer_ext_maker(5, 10, 10, False, ntl.ZZ_pX([-5, 0, 1], 5^10), "small") #indirect doctest 
     72        """ 
     73        PowComputer_class.__init__(self, prime, cache_limit, prec_cap, in_field) 
    6474 
    6575    def __dealloc__(self): 
     76        """ 
     77        Frees allocated memory. 
     78 
     79        EXAMPLES: 
     80        sage: PC = PowComputer_ext_maker(5, 5, 10, False, ntl.ZZ_pX([-5,0,1],5^10), "FM") 
     81        sage: del PC # indirect doctest 
     82        """ 
     83        if (<PowComputer_class>self)._initialized: 
     84            self.cleanup_ext() 
     85 
     86    def __repr__(self): 
     87        """ 
     88        Returns a string representation of self. 
     89 
     90        EXAMPLES: 
     91        sage: PC = PowComputer_ext_maker(5, 10, 10, False, ntl.ZZ_pX([-5, 0, 1], 5^10), "small") 
     92        sage: PC # indirect doctest 
     93        PowComputer_ext for 5, with polynomial [9765620 0 1] 
     94        """ 
     95        return "PowComputer_ext for %s, with polynomial %s"%(self.prime, self.polynomial()) 
     96 
     97    cdef void cleanup_ext(self): 
     98        """ 
     99        Frees memory allocated in PowComputer_ext. 
     100 
     101        EXAMPLES: 
     102        sage: PC = PowComputer_ext_maker(5, 5, 10, False, ntl.ZZ_pX([-5,0,1],5^10), "FM") 
     103        sage: del PC # indirect doctest 
     104        """ 
    66105        cdef Py_ssize_t i 
    67         if (<PowComputer_class>self)._initialized: 
    68             for i from 0 <= i <= self.cache_limit: 
    69                 ZZ_destruct(&(self.small_powers[i])) 
    70             sage_free(self.small_powers) 
    71             ZZ_destruct(&self.top_power) 
     106        for i from 0 <= i <= self.cache_limit: 
     107            ZZ_destruct(&(self.small_powers[i])) 
     108        sage_free(self.small_powers) 
     109        ZZ_destruct(&self.top_power) 
     110        mpz_clear(self.temp_m) 
     111        ZZ_destruct(&self.temp_z) 
    72112     
    73     def _cache_limit(self): 
    74         """ 
    75         Returns the limit to which powers of prime are computed. 
    76         """ 
    77         cdef Integer ans 
    78         ans = PY_NEW(Integer) 
    79         mpz_set_ui(ans.value, self.cache_limit) 
     113    cdef mpz_t* pow_mpz_t_tmp(self, unsigned long n): 
     114        """ 
     115        Provides fast access to an mpz_t* pointing to self.prime^n. 
     116 
     117        The location pointed to depends on the underlying representation. 
     118        In no circumstances should you mpz_clear the result. 
     119        The value pointed to may be an internal temporary variable for the class. 
     120        In particular, you should not try to refer to the results of two 
     121        pow_mpz_t_tmp calls at the same time, because the second 
     122        call may overwrite the memory pointed to by the first. 
     123 
     124        In the case of PowComputer_exts, the mpz_t pointed to will always 
     125        be a temporary variable. 
     126 
     127        See pow_mpz_t_tmp_demo for an example of this phenomenon. 
     128 
     129        EXAMPLES: 
     130        sage: PC = PowComputer_ext_maker(5, 10, 10, False, ntl.ZZ_pX([-5, 0, 1], 5^10), "small") 
     131        sage: PC.pow_mpz_t_tmp_test(4) #indirect doctest 
     132        625 
     133        """ 
     134        # READ THE DOCSTRING 
     135        if n <= self.cache_limit: 
     136            ZZ_to_mpz(&self.temp_m, &(self.small_powers[n])) 
     137        elif n == self.prec_cap: 
     138            ZZ_to_mpz(&self.temp_m, &self.top_power) 
     139        else: 
     140            mpz_pow_ui(self.temp_m, self.prime.value, n) 
     141        return &self.temp_m 
     142 
     143    cdef ZZ_c* pow_ZZ_tmp(self, unsigned long n): 
     144        """ 
     145        Provides fast access to a ZZ_c* pointing to self.prime^n. 
     146 
     147        The location pointed to depends on the underlying representation. 
     148        In no circumstances should you ZZ_destruct the result. 
     149        The value pointed to may be an internal temporary variable for the class. 
     150        In particular, you should not try to refer to the results of two 
     151        pow_ZZ_tmp calls at the same time, because the second 
     152        call may overwrite the memory pointed to by the first. 
     153 
     154        See pow_ZZ_tmp_demo for an example of this phenomenon. 
     155 
     156        EXAMPLES: 
     157        sage: PC = PowComputer_ext_maker(5, 10, 10, False, ntl.ZZ_pX([-5, 0, 1], 5^10), "small") 
     158        sage: PC.pow_mpz_t_tmp_test(4) #indirect doctest 
     159        625 
     160        """ 
     161        if n <= self.cache_limit: 
     162            return &(self.small_powers[n]) 
     163        if n == self.prec_cap: 
     164            return &self.top_power 
     165        ZZ_power(self.temp_z, self.small_powers[1], n) 
     166        return &self.temp_z 
     167 
     168    def pow_ZZ_tmp_test(self, n): 
     169        """ 
     170        Tests the pow_ZZ_tmp function 
     171 
     172        EXAMPLES: 
     173        sage: PC = PowComputer_ext_maker(5, 6, 6, False, ntl.ZZ_pX([-5,0,1],5^6),"small") 
     174        sage: PC.pow_ZZ_tmp_test(4) 
     175        625 
     176        sage: PC.pow_ZZ_tmp_test(7) 
     177        78125 
     178        """ 
     179        cdef Integer _n = Integer(n) 
     180        if _n < 0: raise ValueError 
     181        cdef ntl_ZZ ans = PY_NEW(ntl_ZZ) 
     182        ans.x = self.pow_ZZ_tmp(mpz_get_ui(_n.value))[0] 
    80183        return ans 
    81184 
    82     def _top_power(self): 
    83         """ 
    84         Returns self._prime()^self._prec_cap() 
    85         """ 
    86         cdef Integer ans 
    87         ans = PY_NEW(Integer) 
    88         mpz_set(ans.value, self.top_power) 
     185    def pow_ZZ_tmp_demo(self, m, n): 
     186        """ 
     187        This function demonstrates a danger in using pow_ZZ_tmp. 
     188 
     189        EXAMPLES: 
     190        sage: PC = PowComputer_ext_maker(5, 5, 10, False, ntl.ZZ_pX([-5,0,1],5^10), "big") 
     191 
     192        When you cal pow_ZZ_tmp with an input that is not stored 
     193        (ie n > self.cache_limit and n != self.prec_cap), 
     194        it stores the result in self.temp_z and returns a pointer 
     195        to that ZZ_c.  So if you try to use the results of two 
     196        calls at once, things will break. 
     197        sage: PC.pow_ZZ_tmp_demo(6, 8) 
     198        244140625 
     199        sage: 5^6*5^8 
     200        6103515625 
     201        sage: 5^6*5^6 
     202        244140625 
     203 
     204        Note that this does not occur if you try a stored value, 
     205        because the result of one of the calls points to that 
     206        stored value. 
     207        sage: PC.pow_ZZ_tmp_demo(6, 10) 
     208        152587890625 
     209        sage: 5^6*5^10 
     210        152587890625         
     211        """ 
     212        m = Integer(m) 
     213        n = Integer(n) 
     214        if m < 0 or n < 0: 
     215            raise ValueError, "m, n must be non-negative" 
     216        cdef ntl_ZZ ans = PY_NEW(ntl_ZZ) 
     217        ZZ_mul(ans.x, self.pow_ZZ_tmp(mpz_get_ui((<Integer>m).value))[0], self.pow_ZZ_tmp(mpz_get_ui((<Integer>n).value))[0]) 
    89218        return ans 
    90219 
    91     def _prec_cap(self): 
    92         """ 
    93         Returns prec_cap, a single value that for which self._prime()^prec_cap is stored 
    94         """ 
    95         cdef Integer ans 
    96         ans = PY_NEW(Integer) 
    97         mpz_set_ui(ans.value, self.prec_cap) 
     220 
     221    cdef mpz_t* pow_mpz_t_top(self): 
     222        """ 
     223        Returns self.prime^self.prec_cap as an mpz_t*. 
     224 
     225        EXAMPLES: 
     226        sage: PC = PowComputer_ext_maker(5, 6, 6, False, ntl.ZZ_pX([-5,0,1],5^6),"small") 
     227        sage: PC.pow_mpz_t_top_test() #indirect doctest 
     228        15625 
     229        """ 
     230        ZZ_to_mpz(&self.temp_m, &self.top_power) 
     231        return &self.temp_m 
     232 
     233    cdef ZZ_c* pow_ZZ_top(self): 
     234        """ 
     235        Returns self.prime^self.prec_cap as a ZZ_c. 
     236 
     237        EXAMPLES: 
     238        sage: PC = PowComputer_ext_maker(5, 6, 6, False, ntl.ZZ_pX([-5,0,1],5^6),"small") 
     239        sage: PC.pow_ZZ_top_test() #indirect doctest 
     240        15625 
     241        """ 
     242        return &self.top_power 
     243 
     244    def pow_ZZ_top_test(self): 
     245        """ 
     246        Tests the pow_ZZ_top function. 
     247 
     248        EXAMPLES: 
     249        sage: PC = PowComputer_ext_maker(5, 6, 6, False, ntl.ZZ_pX([-5,0,1],5^6),"small") 
     250        sage: PC.pow_ZZ_top_test() 
     251        15625 
     252        """ 
     253        cdef ntl_ZZ ans = PY_NEW(ntl_ZZ) 
     254        ans.x = self.pow_ZZ_top()[0] 
    98255        return ans 
    99256 
    100     cdef Integer pow_Integer(self, unsigned long n): 
    101         cdef Integer ans = PY_NEW(Integer) 
    102         if n <= self.cache_limit: 
    103             ZZ_to_mpz(&ans.value, &(self.small_powers[n])) 
    104         elif n == self.prec_cap: 
    105             ZZ_to_mpz(&ans.value, &self.top_power) 
    106         else: 
    107             mpz_pow_ui(ans.value, self.prime.value, n) 
     257cdef class PowComputer_ZZ_pX(PowComputer_ext): 
     258    def __new__(self, Integer prime, unsigned long cache_limit, unsigned long prec_cap, bint in_field, poly): 
     259        if not PY_TYPE_CHECK(poly, ntl_ZZ_pX): 
     260            raise TypeError 
     261        self.deg = ZZ_pX_deg((<ntl_ZZ_pX>poly).x) 
     262        PowComputer_ext.__init__(self, prime, cache_limit, prec_cap, in_field, poly) 
     263 
     264    def polynomial(self): 
     265        """ 
     266        Returns the polynomial (with coefficient precision prec_cap) associated to this PowComputer. 
     267 
     268        The polynomial is output as an ntl_ZZ_pX. 
     269 
     270        EXAMPLES: 
     271        sage: PC = PowComputer_ext_maker(5, 5, 10, False, ntl.ZZ_pX([-5,0,1],5^10), "FM") 
     272        sage: PC.polynomial() 
     273        [9765620 0 1] 
     274        """ 
     275        self.restore_top_context() 
     276        cdef ntl_ZZ_pX r = PY_NEW(ntl_ZZ_pX) 
     277        r.c = self.get_top_context() 
     278        r.x = (self.get_top_modulus()[0]).val() 
     279        return r 
     280 
     281    cdef ntl_ZZ_pContext_class get_context(self, unsigned long n): 
     282        """ 
     283        Returns a ZZ_pContext for self.prime^n. 
     284 
     285        EXAMPLES: 
     286        sage: PC = PowComputer_ext_maker(5, 10, 10, False, ntl.ZZ_pX([-5, 0, 1], 5^10), "FM") 
     287        sage: PC.get_context_test(15) #indirect doctest 
     288        NTL modulus 30517578125 
     289        """ 
     290        cdef ntl_ZZ pn = PY_NEW(ntl_ZZ) 
     291        pn.x = self.pow_ZZ_tmp(n)[0] 
     292        cdef ntl_ZZ_pContext_class context = (<ntl_ZZ_pContext_factory>ZZ_pContext_factory).make_c(pn) 
     293        return context 
     294 
     295    def get_context_test(self, n): 
     296        """ 
     297        Returns a ZZ_pContext for self.prime^n. 
     298 
     299        EXAMPLES: 
     300        sage: PC = PowComputer_ext_maker(5, 10, 10, False, ntl.ZZ_pX([-5, 0, 1], 5^10), "FM") 
     301        sage: PC.get_context_test(15) 
     302        NTL modulus 30517578125 
     303        """ 
     304        cdef Integer _n = Integer(n) 
     305        if _n < 1: raise ValueError 
     306        return self.get_context(mpz_get_ui(_n.value)) 
     307 
     308    def speed_test(self, n, runs): 
     309        """ 
     310        Runs a speed test. 
     311 
     312        INPUT: 
     313        n -- input to a function to be tested (the function needs to be set in the source code). 
     314        runs -- The number of runs of that function 
     315        OUTPUT: 
     316        The time in seconds that it takes to call the function on n, runs times. 
     317 
     318        sage: PC = PowComputer_ext_maker(5, 10, 10, False, ntl.ZZ_pX([-5, 0, 1], 5^10), "small") 
     319        sage: PC.speed_test(10, 10^6) # random 
     320        0.0090679999999991878  
     321        """ 
     322        cdef Py_ssize_t i, end, _n 
     323        end = mpz_get_ui((<Integer>Integer(runs)).value) 
     324        _n = mpz_get_ui((<Integer>Integer(n)).value) 
     325        t = cputime() 
     326        for i from 0 <= i < end: 
     327            # Put the function you want speed tested here. 
     328            self.get_modulus(_n) 
     329        return cputime(t) 
     330     
     331    cdef ntl_ZZ_pContext_class get_top_context(self): 
     332        """ 
     333        Returns a ZZ_pContext for self.prime^self.prec_cap 
     334 
     335        sage: PC = PowComputer_ext_maker(5, 5, 10, False, ntl.ZZ_pX([-5,0,1],5^10), "FM") 
     336        sage: PC.get_top_context_test() #indirect doctest 
     337        NTL modulus 9765625 
     338        """ 
     339        return self.get_context(self.prec_cap) 
     340 
     341    def get_top_context_test(self): 
     342        """ 
     343        Returns a ZZ_pContext for self.prime^self.prec_cap 
     344         
     345        sage: PC = PowComputer_ext_maker(5, 5, 10, False, ntl.ZZ_pX([-5,0,1],5^10), "FM") 
     346        sage: PC.get_top_context_test() 
     347        NTL modulus 9765625 
     348        """ 
     349        return self.get_top_context() 
     350         
     351    cdef restore_context(self, unsigned long n): 
     352        """ 
     353        Restores the contest corresponding to self.prime^n 
     354 
     355        EXAMPLES: 
     356        sage: PC = PowComputer_ext_maker(5, 5, 10, False, ntl.ZZ_pX([-5,0,1],5^10), "FM") 
     357        sage: PC.restore_context_test(4) #indirect doctest 
     358        """ 
     359        self.get_context(n).restore_c() 
     360 
     361    def restore_context_test(self, n): 
     362        """ 
     363        Restores the contest corresponding to self.prime^n 
     364 
     365        EXAMPLES: 
     366        sage: PC = PowComputer_ext_maker(5, 5, 10, False, ntl.ZZ_pX([-5,0,1],5^10), "FM") 
     367        sage: PC.restore_context_test(4) 
     368        """ 
     369        cdef Integer _n = Integer(n) 
     370        if _n < 0: raise ValueError 
     371        self.restore_context(mpz_get_ui(_n.value)) 
     372 
     373    cdef void restore_top_context(self): 
     374        """ 
     375        Restores the context corresponding to self.prime^self.prec_cap 
     376 
     377        EXAMPLES: 
     378        sage: PC = PowComputer_ext_maker(5, 5, 10, False, ntl.ZZ_pX([-5,0,1],5^10), "FM") 
     379        sage: PC.restore_top_context_test()         
     380        """ 
     381        (<ntl_ZZ_pContext_class>self.get_top_context()).restore_c() 
     382 
     383    def restore_top_context_test(self): 
     384        """ 
     385        Restores the context corresponding to self.prime^self.prec_cap 
     386 
     387        EXAMPLES: 
     388        sage: PC = PowComputer_ext_maker(5, 5, 10, False, ntl.ZZ_pX([-5,0,1],5^10), "FM") 
     389        sage: PC.restore_top_context_test() 
     390        """ 
     391        self.restore_top_context() 
     392     
     393    cdef ZZ_pX_Modulus_c* get_modulus(self, unsigned long n): 
     394        """ 
     395        Returns the modulus corresponding to self.polynomial() (mod self.prime^n) 
     396 
     397        EXAMPLES: 
     398        sage: A = PowComputer_ext_maker(5, 10, 1000, False, ntl.ZZ_pX([-5,0,1],5^1000), "big") 
     399        sage: a = ntl.ZZ_pX([4,2],5^2) 
     400        sage: b = ntl.ZZ_pX([6,3],5^2) 
     401        sage: A.get_modulus_test(a, b, 2) # indirect doctest 
     402        [4 24] 
     403        """ 
     404        raise NotImplementedError 
     405 
     406    def get_modulus_test(self, ntl_ZZ_pX a, ntl_ZZ_pX b, Integer n): 
     407        """ 
     408        Multiplies a and b modulo the modulus corresponding to self.polynomial() (mod self.prime^n). 
     409 
     410        EXAMPLES: 
     411        sage: A = PowComputer_ext_maker(5, 10, 1000, False, ntl.ZZ_pX([-5,0,1],5^1000), "big") 
     412        sage: a = ntl.ZZ_pX([4,2],5^2) 
     413        sage: b = ntl.ZZ_pX([6,3],5^2) 
     414        sage: A.get_modulus_test(a, b, 2) 
     415        [4 24] 
     416        sage: a * b 
     417        [24 24 6] 
     418        sage: mod(6 * 5 + 24, 25) 
     419        4 
     420        """ 
     421        cdef ntl_ZZ_pX r = (<ntl_ZZ_pX>a)._new() 
     422        ZZ_pX_MulMod_pre(r.x, a.x, b.x, self.get_modulus(mpz_get_ui(n.value))[0]) 
     423        return r 
     424 
     425    cdef ZZ_pX_Modulus_c* get_top_modulus(self): 
     426        """ 
     427        Returns the modulus corresponding to self.polynomial() (mod self.prime^self.prec_cap) 
     428 
     429        EXAMPLES: 
     430        sage: A = PowComputer_ext_maker(5, 3, 10, False, ntl.ZZ_pX([-5,0,1],5^10), "FM") 
     431        sage: a = ntl.ZZ_pX([129223,1231],5^10) 
     432        sage: b = ntl.ZZ_pX([289741,323],5^10) 
     433        sage: A.get_top_modulus_test(a, b) #indirect doctest 
     434        [1783058 7785200]          
     435        """ 
     436        raise NotImplementedError 
     437 
     438    def get_top_modulus_test(self, ntl_ZZ_pX a, ntl_ZZ_pX b): 
     439        """ 
     440        Multiplies a and b modulo the modulus corresponding to self.polynomial() (mod self.prime^self.prec_cap) 
     441 
     442        EXAMPLES: 
     443        sage: A = PowComputer_ext_maker(5, 3, 10, False, ntl.ZZ_pX([-5,0,1],5^10), "FM") 
     444        sage: a = ntl.ZZ_pX([129223,1231],5^10) 
     445        sage: b = ntl.ZZ_pX([289741,323],5^10) 
     446        sage: A.get_top_modulus_test(a, b)  
     447        [1783058 7785200] 
     448        sage: a*b 
     449        [9560618 7785200 397613] 
     450        sage: mod(397613 * 5 + 9560618, 5^10) 
     451        1783058 
     452        """ 
     453        cdef ntl_ZZ_pX ans = a._new() 
     454        ZZ_pX_MulMod_pre(ans.x, a.x, b.x, self.get_top_modulus()[0]) 
    108455        return ans 
    109456 
    110     cdef mpz_t pow_mpz_t(self, unsigned long n): 
    111         ## You always need to call mpz_clear on the return value of this function 
    112         cdef mpz_t ans 
    113         mpz_init(ans) 
    114         if n <= self.cache_limit: 
    115             ZZ_to_mpz(&ans, &(self.small_powers[n])) 
    116         elif n == self.prec_cap: 
    117             ZZ_to_mpz(&ans, &self.top_power) 
    118         else: 
    119             mpz_pow_ui(ans, self.prime.value, n) 
    120         return ans 
    121  
    122     cdef ZZ_c pow_ZZ(self, unsigned long n): 
    123         #################### WARNING ###################### 
    124         ## If you use this function, you MAY need to     ## 
    125         ## call ZZ_destruct on the returned value after  ## 
    126         ## you are finished with it.  You need to do     ## 
    127         ## so if and only if (n > self.cache_limit and   ## 
    128         ## n != self.prec_cap).  So your code should     ## 
    129         ## look something like the following:            ## 
    130         ##                                               ## 
    131         ## cdef PowComputer_ext ppow                     ## 
    132         ## ppow = PowComputer(5, 10, 1000, poly)         ## 
    133         ## cdef unsigned long n = get_long_somehow()     ## 
    134         ## cdef ZZ_c foo = ppow.pow_ZZ(n)                ## 
    135         ## # Do stuff with foo                           ## 
    136         ## # Now done with foo                           ## 
    137         ## if n > ppow.cache_limit and n != ppow.prec_cap## 
    138         ##     ZZ_destruct(foo)                          ## 
    139         ################################################### 
    140         if n <= self.cache_limit: 
    141             return self.small_powers[n] 
    142         if n == self.prec_cap: 
    143             return self.top_power 
    144         cdef ZZ_c ans 
    145         ZZ_construct(&ans) 
    146         power_ZZ(ans, self.small_powers[1], n) 
    147         return ans 
    148  
    149 cdef class PowComputer_ZZ_pX(PowComputer_ext): 
    150     cdef ntl_ZZ_pContext get_context(self, unsigned long n): 
    151         cdef ZZ_c pn = self.pow_ZZ(n) 
    152         cdef ntl_ZZ_pContext_class context = <ntl_ZZ_pContext_class> ntl_ZZ_pContext(pn) 
    153         if n > self.cache_limit and n != self.prec_cap: 
    154             ZZ_destruct(pn) 
    155         return context 
    156      
    157     cdef ntl_ZZ_pContext get_top_context(self): 
    158         return ntl_ZZ_pContext(self.top_power) 
    159  
    160     cdef void restore_context(self, unsigned long n): 
    161         self.get_context(n).restore_c() 
    162  
    163     cdef void restore_top_context(self): 
    164         self.get_top_context().restore_c() 
    165      
    166     cdef ZZ_pX_Modulus_c get_modulus(self, unsigned long n): 
    167         raise NotImplementedError 
    168  
    169     cdef ZZ_pX_Modulus_c get_top_modulus(self): 
    170         raise NotImplementedError 
    171  
    172457cdef class PowComputer_ZZ_pX_FM(PowComputer_ZZ_pX): 
     458    """ 
     459    This class only caches a context and modulus for p^prec_cap. 
     460    Designed for use with fixed modulus p-adic rings, in Eisenstein and unramified extensions of $\mathbb{Z}_p$. 
     461    """ 
     462 
    173463    def __new__(self, Integer prime, unsigned long cache_limit, unsigned long prec_cap, bint in_field, poly): 
     464        """ 
     465        Caches a context and modulus for prime^prec_cap 
     466 
     467        EXAMPLES: 
     468        sage: A = PowComputer_ext_maker(5, 3, 10, False, ntl.ZZ_pX([-5,0,1],5^10), "FM") #indirect doctest 
     469        sage: A 
     470        PowComputer_ext for 5, with polynomial [9765620 0 1] 
     471        """ 
     472 
    174473        # The __new__ method for PowComputer_ext has already run, so we have access to small_powers, top_power. 
    175474 
    176475        # We use ntl_ZZ_pContexts so that contexts are cached centrally. 
    177         self.c = ntl_ZZ_pContext(self.top_power) 
     476 
     477        self.c = self.get_context(prec_cap) 
    178478        self.c.restore_c() 
    179  
    180479        # For now, we don't do anything complicated with poly 
    181480        if PY_TYPE_CHECK(poly, ntl_ZZ_pX) and (<ntl_ZZ_pX>poly).c is self.c: 
    182             self.poly = (<ntl_ZZ_pX>poly).x 
     481            ZZ_pX_Modulus_construct(&self.mod) 
     482            ZZ_pX_Modulus_build(self.mod, (<ntl_ZZ_pX>poly).x) 
     483            # These will be reset if we're actually eisenstein 
     484            self.e = 1 
     485            self.f = ZZ_pX_deg((<ntl_ZZ_pX>poly).x) 
     486            self.ram_prec_cap = self.prec_cap 
    183487        else: 
     488            print "NOT IMPLEMENTED IN PowComputer_ZZ_pX_FM" 
    184489            raise NotImplementedError 
    185         ZZ_pX_Modulus_construct(&self.mod) 
    186         ZZ_pX_Modulus_build(self.mod, self.poly) 
    187490 
    188491    def __init__(self, Integer prime, unsigned long cache_limit, unsigned long prec_cap, bint in_field, poly): 
     492        """ 
     493        Caches a context and modulus for prime^prec_cap 
     494 
     495        EXAMPLES: 
     496        sage: A = PowComputer_ext_maker(5, 3, 10, False, ntl.ZZ_pX([-5,0,1],5^10), "FM") #indirect doctest 
     497        sage: A 
     498        PowComputer_ext for 5, with polynomial [9765620 0 1] 
     499        """ 
    189500        PowComputer_ZZ_pX.__init__(self, prime, cache_limit, prec_cap, in_field, poly) 
    190501 
    191     cdef ntl_ZZ_pContext get_top_context(self): 
     502    def __dealloc__(self): 
     503        """ 
     504        Cleans up the memory for self.mod 
     505 
     506        EXAMPLES: 
     507        sage: A = PowComputer_ext_maker(5, 3, 10, False, ntl.ZZ_pX([-5,0,1],5^10), "FM") #indirect doctest 
     508        sage: del A # indirect doctest 
     509        """ 
     510        if self._initialized: 
     511            self.cleanup_ZZ_pX_FM() 
     512 
     513    cdef void cleanup_ZZ_pX_FM(self): 
     514        """ 
     515        Cleans up the memory for self.mod 
     516 
     517        EXAMPLES: 
     518        sage: A = PowComputer_ext_maker(5, 3, 10, False, ntl.ZZ_pX([-5,0,1],5^10), "FM") #indirect doctest 
     519        sage: del A # indirect doctest 
     520        """ 
     521        ZZ_pX_Modulus_destruct(&self.mod) 
     522 
     523    cdef ntl_ZZ_pContext_class get_top_context(self): 
     524        """ 
     525        Returns a ZZ_pContext for self.prime^self.prec_cap 
     526         
     527        sage: PC = PowComputer_ext_maker(5, 5, 10, False, ntl.ZZ_pX([-5,0,1],5^10), "FM") 
     528        sage: PC.get_top_context_test() # indirect doctest 
     529        NTL modulus 9765625 
     530        """ 
    192531        return self.c 
    193532 
    194533    cdef void restore_top_context(self): 
     534        """ 
     535        Restores the context corresponding to self.prime^self.prec_cap 
     536 
     537        EXAMPLES: 
     538        sage: PC = PowComputer_ext_maker(5, 5, 10, False, ntl.ZZ_pX([-5,0,1],5^10), "FM") 
     539        sage: PC.restore_top_context_test() #indirect doctest         
     540        """ 
    195541        self.c.restore_c() 
    196542 
    197     cdef ZZ_pX_Modulus_c get_modulus(self, unsigned long n): 
    198         ## You always need to call ZZ_pX_Modulus_destruct on the return value of this function once you're done. 
    199         cdef ZZX_c temp 
    200         cdef ZZ_pX_c tempZZ_pX 
    201         self.c.restore_c() 
    202         ZZX_construct(&temp) 
    203         ZZ_pX_to_ZZX(temp, self.poly) 
    204         self.restore_context(n) 
    205         ZZ_pX_construct(&tempZZ_pX) 
    206         ZZX_to_ZZ_pX(tempZZ_pX, temp) 
    207         cdef ZZ_pX_Modulus ans 
    208         ZZ_pX_Modulus_construct(&ans) 
    209         ZZ_pX_Modulus_build(ans, tempZZ_pX) 
    210         ZZX_destruct(&temp) 
    211         ZZ_pX_destruct(&tempZZ_pX) 
    212         return ans 
    213  
    214     cdef ZZ_pX_Modulus_c get_top_modulus(self): 
    215         ## Never call ZZ_pX_Modulus_destruct on the return value of this function 
    216         return self.mod 
    217  
    218      
     543    cdef ZZ_pX_Modulus_c* get_top_modulus(self): 
     544        """ 
     545        Returns the modulus corresponding to self.polynomial() (mod self.prime^self.prec_cap) 
     546 
     547        EXAMPLES: 
     548        sage: A = PowComputer_ext_maker(5, 3, 10, False, ntl.ZZ_pX([-5,0,1],5^10), "FM") 
     549        sage: a = ntl.ZZ_pX([129223,1231],5^10) 
     550        sage: b = ntl.ZZ_pX([289741,323],5^10) 
     551        sage: A.get_top_modulus_test(a, b) #indirect doctest 
     552        [1783058 7785200]          
     553        """ 
     554        return &self.mod 
     555 
     556cdef class PowComputer_ZZ_pX_FM_Eis(PowComputer_ZZ_pX_FM): 
     557    """ 
     558    This class computes and stores eis_shifter, which aids in right shifting elements. 
     559    """ 
     560 
     561    def __new__(self, Integer prime, unsigned long cache_limit, unsigned long prec_cap, bint in_field, poly): 
     562        # The __new__ method for PowComputer_ZZ_pX_FM has already run, so we have access to self.mod 
     563 
     564        # self.low_shifter stores multipliers for p/x^(2^i) 
     565        # If self.deg is one more than a power of 2, we need to store p/x, p/x^2, up to p/x^(2^n) where 2^n is that power of 2. 
     566        #print "here" 
     567        #cdef ntl_ZZ_pX printer = ntl_ZZ_pX([], self.c) 
     568        self.e = ZZ_pX_deg((<ntl_ZZ_pX>poly).x) 
     569        self.f = 1 
     570        self.ram_prec_cap = self.prec_cap * self.e 
     571        if self.deg <= 1: 
     572            raise ValueError 
     573 
     574    def _low_shifter(self, i): 
     575        cdef long _i = i 
     576        cdef ntl_ZZ_pX ans 
     577        if _i >= 0 and _i < self.low_length: 
     578            ans = ntl_ZZ_pX([], self.get_top_context()) 
     579            ans.x = self.low_shifter[i].val() 
     580            return ans 
     581        else: 
     582            raise IndexError 
     583 
     584    def _high_shifter(self, i): 
     585        cdef long _i = i 
     586        cdef ntl_ZZ_pX ans 
     587        if _i >= 0 and _i < self.high_length: 
     588            ans = ntl_ZZ_pX([], self.get_top_context()) 
     589            ans.x = self.high_shifter[i].val() 
     590            return ans 
     591        else: 
     592            raise IndexError 
     593         
     594 
     595             
     596 
     597    def __dealloc__(self): 
     598        if self._initialized: 
     599            self.cleanup_ZZ_pX_FM_Eis() 
     600 
     601    cdef void cleanup_ZZ_pX_FM_Eis(self): 
     602        pass 
     603        # I may or may not need to deallocate these: 
     604        # 
     605        #cdef int i # yes, an int is good enough 
     606        #for i from 0 <= i < self.low_length: 
     607        #    ZZ_pX_Multiplier_destruct(self.low_shifter[i]) 
     608        #sage_free(self.low_shifter) 
     609        #for i from 0 <= i < self.high_length: 
     610        #    ZZ_pX_Multiplier_destruct(self.high_shifter[i]) 
     611        #sage_free(self.high_shifter) 
     612         
     613 
     614cdef class PowComputer_ZZ_pX_small(PowComputer_ZZ_pX): 
     615    """ 
     616    This class caches contexts and moduli densely between 1 and cache_limit.  It requires cache_limit == prec_cap. 
     617 
     618    It is intended for use with capped relative and capped absolute rings and fields, in Eisenstein and unramified 
     619    extensions of the base p-adic fields. 
     620    """ 
     621 
     622    def __new__(self, Integer prime, unsigned long cache_limit, unsigned long prec_cap, bint in_field, poly): 
     623        """ 
     624        Caches contexts and moduli densely between 1 and cache_limit. 
     625 
     626        EXAMPLES: 
     627        sage: A = PowComputer_ext_maker(5, 10, 10, False, ntl.ZZ_pX([-5,0,1],5^10), "small") # indirect doctest 
     628        sage: A 
     629        PowComputer_ext for 5, with polynomial [9765620 0 1] 
     630        """ 
     631        # The __new__ method for PowComputer_ext has already run, so we have access to small_powers, top_power. 
     632 
     633        # We use ntl_ZZ_pContexts so that contexts are cached centrally. 
     634 
     635        if not PY_TYPE_CHECK(poly, ntl_ZZ_pX): 
     636            self.cleanup_ext() 
     637            self.cleanup_ZZ_pX() 
     638            raise TypeError 
     639 
     640        if cache_limit != prec_cap: 
     641            self.cleanup_ext() 
     642            self.cleanup_ZZ_pX() 
     643            raise ValueError, "prec_cap and cache_limit must be equal in the small case" 
     644 
     645        self.c = [] 
     646        #if self.c == NULL: 
     647        #    self.cleanup_ext() 
     648        #    self.cleanup_ZZ_pX() 
     649        #    raise MemoryError, "out of memory allocating contexts" 
     650        _sig_on 
     651        self.mod = <ZZ_pX_Modulus_c *>sage_malloc(sizeof(ZZ_pX_Modulus_c) * (cache_limit + 1)) 
     652        _sig_off 
     653        if self.mod == NULL: 
     654            self.cleanup_ext() 
     655            self.cleanup_ZZ_pX() 
     656            raise MemoryError, "out of memory allocating moduli" 
     657 
     658        cdef Py_ssize_t i 
     659        cdef ZZ_pX_c tmp, pol 
     660        ZZ_pX_construct(&tmp) 
     661        ZZ_pX_construct(&pol) 
     662        pol = (<ntl_ZZ_pX>poly).x 
     663        self.c.append(None) 
     664        for i from 1 <= i <= cache_limit: 
     665            self.c.append(PowComputer_ZZ_pX.get_context(self,i)) 
     666            ZZ_pX_Modulus_construct(&(self.mod[i])) 
     667            ZZ_pX_conv_modulus(tmp, pol, (<ntl_ZZ_pContext_class>self.c[i]).x) 
     668            ZZ_pX_Modulus_build(self.mod[i], tmp) 
     669        ## I get malloc errors if I leave the following in: I don't know why. 
     670        #ZZ_pX_destruct(&tmp) 
     671        #ZZ_pX_destruct(&pol) 
     672 
     673    def __init__(self, Integer prime, unsigned long cache_limit, unsigned long prec_cap, bint in_field, poly): 
     674        """ 
     675        Initializes prime, cache_limit, prec_cap, in_field. 
     676 
     677        EXAMPLES: 
     678        sage: A = PowComputer_ext_maker(5, 10, 10, False, ntl.ZZ_pX([-5,0,1],5^10), "small") # indirect doctest 
     679        sage: A 
     680        PowComputer_ext for 5, with polynomial [9765620 0 1] 
     681        """ 
     682        PowComputer_ZZ_pX.__init__(self, prime, cache_limit, prec_cap, in_field, poly) 
     683 
     684    def __dealloc__(self): 
     685        """ 
     686        Deallocates cache of contexts, moduli. 
     687 
     688        EXAMPLES: 
     689        sage: A = PowComputer_ext_maker(5, 10, 10, False, ntl.ZZ_pX([-5,0,1],5^10), "small") 
     690        sage: del A # indirect doctest 
     691        """ 
     692        if self._initialized: 
     693            self.cleanup_ZZ_pX_small() 
     694 
     695    cdef void cleanup_ZZ_pX_small(self): 
     696        """ 
     697        Deallocates cache of contexts, moduli. 
     698 
     699        EXAMPLES: 
     700        sage: A = PowComputer_ext_maker(5, 10, 10, False, ntl.ZZ_pX([-5,0,1],5^10), "small") 
     701        sage: del A # indirect doctest 
     702        """ 
     703        pass 
     704        ## These cause segfaults: I don't know why. 
     705        #cdef Py_ssize_t i 
     706        #for i from 0 <= i <= self.cache_limit: 
     707        #    ZZ_pX_Modulus_destruct(&(self.mod[i])) 
     708        #sage_free(self.mod) 
     709 
     710    cdef ntl_ZZ_pContext_class get_context(self, unsigned long n): 
     711        """ 
     712        Returns the context for p^n. 
     713 
     714        Note that this function will raise an Index error if n > self.cache_limit. 
     715        Also, it will return None on input 0 
     716 
     717        INPUT: 
     718        n -- A long between 1 and self.cache_limit, inclusive 
     719        OUTPUT: 
     720        A context for p^n 
     721 
     722        EXAMPLES: 
     723        sage: A = PowComputer_ext_maker(5, 10, 10, False, ntl.ZZ_pX([-5,0,1],5^10), "small") 
     724        sage: A.get_context_test(4) #indirect doctest 
     725        NTL modulus 625 
     726        """ 
     727        return self.c[n] 
     728 
     729    cdef restore_context(self, unsigned long n): 
     730        """ 
     731        Restores the context for p^n. 
     732 
     733        INPUT: 
     734        n -- A long between 1 and self.cache_limit, inclusive 
     735 
     736        EXAMPLES:  
     737        sage: A = PowComputer_ext_maker(5, 10, 10, False, ntl.ZZ_pX([-5,0,1],5^10), "small") 
     738        sage: A.restore_context_test(4) #indirect doctest 
     739        """ 
     740        _sig_on 
     741        (<ntl_ZZ_pContext_class>self.c[n]).restore_c() 
     742        _sig_off 
     743 
     744    cdef ntl_ZZ_pContext_class get_top_context(self): 
     745        """ 
     746        Returns a ZZ_pContext for self.prime^self.prec_cap 
     747         
     748        sage: PC = PowComputer_ext_maker(5, 10, 10, False, ntl.ZZ_pX([-5,0,1],5^10), "small") 
     749        sage: PC.get_top_context_test() # indirect doctest 
     750        NTL modulus 9765625 
     751        """         
     752        return self.c[self.prec_cap] 
     753 
     754    cdef void restore_top_context(self): 
     755        """ 
     756        Restores the context corresponding to self.prime^self.prec_cap 
     757 
     758        EXAMPLES: 
     759        sage: PC = PowComputer_ext_maker(5, 10, 10, False, ntl.ZZ_pX([-5,0,1],5^10), "small") 
     760        sage: PC.restore_top_context_test() #indirect doctest         
     761        """ 
     762        (<ntl_ZZ_pContext_class>self.c[self.prec_cap]).restore_c() 
     763 
     764    cdef ZZ_pX_Modulus_c* get_modulus(self, unsigned long n): 
     765        """ 
     766        Returns the modulus corresponding to self.polynomial() (mod self.prime^n). 
     767 
     768        INPUT: 
     769        n -- A long between 1 and self.cache_limit, inclusive 
     770 
     771        EXAMPLES: 
     772        sage: A = PowComputer_ext_maker(5, 10, 10, False, ntl.ZZ_pX([-5,0,1],5^10), "small") 
     773        sage: a = ntl.ZZ_pX([4,2],5^2) 
     774        sage: b = ntl.ZZ_pX([6,3],5^2) 
     775        sage: A.get_modulus_test(a, b, 2) 
     776        [4 24] 
     777        """ 
     778        return &(self.mod[n]) 
     779 
     780    cdef ZZ_pX_Modulus_c* get_top_modulus(self): 
     781        """ 
     782        Returns the modulus corresponding to self.polynomial() (mod self.prime^self.prec_cap) 
     783 
     784        EXAMPLES: 
     785        sage: A = PowComputer_ext_maker(5, 10, 10, False, ntl.ZZ_pX([-5,0,1],5^10), "small") 
     786        sage: a = ntl.ZZ_pX([129223,1231],5^10) 
     787        sage: b = ntl.ZZ_pX([289741,323],5^10) 
     788        sage: A.get_top_modulus_test(a, b) #indirect doctest 
     789        [1783058 7785200]          
     790        """ 
     791        return &(self.mod[self.prec_cap]) 
     792 
     793cdef class PowComputer_ZZ_pX_small_Eis(PowComputer_ZZ_pX_small): 
     794    """ 
     795    This class computes and stores eis_shifter, which aids in right shifting elements. 
     796    eis_shifter is only stored at maximal precision: in order to get lower precision versions just reduce mod p. 
     797    """ 
     798    def _low_shifter(self, i): 
     799        cdef long _i = i 
     800        cdef ntl_ZZ_pX ans 
     801        if _i >= 0 and _i < self.low_length: 
     802            ans = ntl_ZZ_pX([], self.get_top_context()) 
     803            ans.x = self.low_shifter[i].val() 
     804            return ans 
     805        else: 
     806            raise IndexError 
     807 
     808    def _high_shifter(self, i): 
     809        cdef long _i = i 
     810        cdef ntl_ZZ_pX ans 
     811        if _i >= 0 and _i < self.high_length: 
     812            ans = ntl_ZZ_pX([], self.get_top_context()) 
     813            ans.x = self.high_shifter[i].val() 
     814            return ans 
     815        else: 
     816            raise IndexError 
     817         
     818 
     819             
     820 
     821    def __dealloc__(self): 
     822        if self._initialized: 
     823            self.cleanup_ZZ_pX_FM_Eis() 
     824 
     825    cdef void cleanup_ZZ_pX_FM_Eis(self): 
     826        pass 
     827        # I may or may not need to deallocate these: 
     828        # 
     829        #cdef int i # yes, an int is good enough 
     830        #for i from 0 <= i < self.low_length: 
     831        #    ZZ_pX_Multiplier_destruct(self.low_shifter[i]) 
     832        #sage_free(self.low_shifter) 
     833        #for i from 0 <= i < self.high_length: 
     834        #    ZZ_pX_Multiplier_destruct(self.high_shifter[i]) 
     835        #sage_free(self.high_shifter) 
     836 
     837cdef class PowComputer_ZZ_pX_big(PowComputer_ZZ_pX): 
     838    """ 
     839    This class caches all contexts and moduli between 1 and cache_limit, and also caches for prec_cap.  In addition, it stores 
     840    a dictionary of contexts and moduli of  
     841    """ 
     842 
     843    def __new__(self, Integer prime, unsigned long cache_limit, unsigned long prec_cap, bint in_field, poly): 
     844        """ 
     845        Caches contexts and moduli densely between 1 and cache_limit.  Caches a context and modulus for prec_cap. 
     846        Also creates the dictionaries. 
     847 
     848        EXAMPLES: 
     849        sage: A = PowComputer_ext_maker(5, 6, 10, False, ntl.ZZ_pX([-5,0,1],5^10), "big") # indirect doctest 
     850        sage: A 
     851        PowComputer_ext for 5, with polynomial [9765620 0 1] 
     852        """ 
     853        # The __new__ method for PowComputer_ext has already run, so we have access to small_powers, top_power. 
     854 
     855        # We use ntl_ZZ_pContexts so that contexts are cached centrally. 
     856 
     857        if not PY_TYPE_CHECK(poly, ntl_ZZ_pX): 
     858            self.cleanup_ext() 
     859            self.cleanup_ZZ_pX() 
     860            raise TypeError 
     861 
     862        self.context_list = [] 
     863        #if self.c == NULL: 
     864        #    self.cleanup_ext() 
     865        #    self.cleanup_ZZ_pX() 
     866        #    raise MemoryError, "out of memory allocating contexts" 
     867        _sig_on 
     868        self.modulus_list = <ZZ_pX_Modulus_c *>sage_malloc(sizeof(ZZ_pX_Modulus_c) * (cache_limit + 1)) 
     869        _sig_off 
     870        if self.modulus_list == NULL: 
     871            self.cleanup_ext() 
     872            self.cleanup_ZZ_pX() 
     873            raise MemoryError, "out of memory allocating moduli" 
     874 
     875        cdef Py_ssize_t i 
     876        cdef ZZ_pX_c tmp, pol 
     877        ZZ_pX_construct(&tmp) 
     878        ZZ_pX_construct(&pol) 
     879        pol = (<ntl_ZZ_pX>poly).x 
     880        self.context_list.append(None) 
     881        for i from 1 <= i <= cache_limit: 
     882            self.context_list.append(PowComputer_ZZ_pX.get_context(self,i)) 
     883            ZZ_pX_Modulus_construct(&(self.modulus_list[i])) 
     884            ZZ_pX_conv_modulus(tmp, pol, (<ntl_ZZ_pContext_class>self.context_list[i]).x) 
     885            ZZ_pX_Modulus_build(self.modulus_list[i], tmp) 
     886        self.top_context = PowComputer_ZZ_pX.get_context(self, prec_cap) 
     887        ZZ_pX_Modulus_construct(&(self.top_mod)) 
     888        ZZ_pX_conv_modulus(tmp, pol, self.top_context.x) 
     889        ZZ_pX_Modulus_build(self.top_mod, tmp) 
     890        ## I get malloc errors if I leave the following in: I don't know why. 
     891        #ZZ_pX_destruct(&tmp) 
     892        #ZZ_pX_destruct(&pol) 
     893        self.context_dict = {} 
     894        self.modulus_dict = {} 
     895 
     896    def __init__(self, Integer prime, unsigned long cache_limit, unsigned long prec_cap, bint in_field, poly): 
     897        """ 
     898        Initializes prime, cache_limit, prec_cap, in_field. 
     899 
     900        EXAMPLES: 
     901        sage: A = PowComputer_ext_maker(5, 6, 10, False, ntl.ZZ_pX([-5,0,1],5^10), "big") # indirect doctest 
     902        sage: A 
     903        PowComputer_ext for 5, with polynomial [9765620 0 1] 
     904        """ 
     905        PowComputer_ZZ_pX.__init__(self, prime, cache_limit, prec_cap, in_field, poly) 
     906 
     907    def __dealloc__(self): 
     908        """ 
     909        Deallocates the stored moduli and contexts. 
     910 
     911        EXAMPLES: 
     912        sage: A = PowComputer_ext_maker(5, 6, 10, False, ntl.ZZ_pX([-5,0,1],5^10), "big")  
     913        sage: del A # indirect doctest 
     914        """ 
     915        if self._initialized: 
     916            self.cleanup_ZZ_pX_big() 
     917 
     918    cdef void cleanup_ZZ_pX_big(self): 
     919        """ 
     920        Deallocates the stored moduli and contexts. 
     921 
     922        EXAMPLES: 
     923        sage: A = PowComputer_ext_maker(5, 6, 10, False, ntl.ZZ_pX([-5,0,1],5^10), "big")  
     924        sage: del A # indirect doctest 
     925        """ 
     926        pass 
     927        ## These cause a segfault.  I don't know why. 
     928        #cdef Py_ssize_t i 
     929        #for i from 0 <= i <= self.cache_limit: 
     930        #    ZZ_pX_Modulus_destruct(&(self.modulus_list[i])) 
     931        #sage_free(self.modulus_list) 
     932        #ZZ_pX_Modulus_destruct(&self.top_mod) 
     933 
     934    def reset_dictionaries(self): 
     935        """ 
     936        Resets the dictionaries.  Note that if there are elements lying around that need access to these dictionaries, calling this function and then doing arithmetic with those elements could cause trouble (if the context object gets garbage collected for example.  The bugs introduced could be very subtle, because NTL will generate a new context object and use it, but there's the potential for the object to be incompatible with the different context object). 
     937 
     938        EXAMPLES: 
     939        sage: A = PowComputer_ext_maker(5, 6, 10, False, ntl.ZZ_pX([-5,0,1],5^10), "big") 
     940        sage: P = A.get_context_test(8) 
     941        sage: A._context_dict() 
     942        {8L: NTL modulus 390625} 
     943        sage: A.reset_dictionaries() 
     944        """ 
     945        self.context_dict = {} 
     946        self.modulus_dict = {} 
     947 
     948    def _context_dict(self): 
     949        """ 
     950        Returns the context dictionary. 
     951 
     952        EXAMPLES: 
     953        sage: A = PowComputer_ext_maker(5, 6, 10, False, ntl.ZZ_pX([-5,0,1],5^10), "big") 
     954        sage: P = A.get_context_test(8) 
     955        sage: A._context_dict() 
     956        {8L: NTL modulus 390625}         
     957        """ 
     958        return self.context_dict 
     959 
     960    def _modulus_dict(self): 
     961        """ 
     962        Returns the context dictionary. 
     963 
     964        EXAMPLES: 
     965        sage: A = PowComputer_ext_maker(5, 6, 10, False, ntl.ZZ_pX([-5,0,1],5^10), "big") 
     966        sage: P = A.get_context_test(8) 
     967        sage: A._modulus_dict() 
     968        {} 
     969        sage: a = ntl.ZZ_pX([4,2],5^8) 
     970        sage: b = ntl.ZZ_pX([6,3],5^8) 
     971        sage: A.get_modulus_test(a, b, 8) 
     972        [54 24] 
     973        sage: A._modulus_dict() 
     974        {8L: NTL ZZ_pXModulus [390620 0 1] (mod 390625)} 
     975        """ 
     976        return self.modulus_dict 
     977 
     978    cdef ntl_ZZ_pContext_class get_context(self, unsigned long n): 
     979        """ 
     980        Returns the context for p^n. 
     981 
     982        Note that this function will raise an Index error if n > self.cache_limit. 
     983        Also, it will return None on input 0 
     984 
     985        INPUT: 
     986        n -- A long between 1 and self.cache_limit, inclusive 
     987        OUTPUT: 
     988        A context for p^n 
     989 
     990        EXAMPLES: 
     991        sage: A = PowComputer_ext_maker(5, 6, 10, False, ntl.ZZ_pX([-5,0,1],5^10), "big") 
     992        sage: A.get_context_test(4) #indirect doctest 
     993        NTL modulus 625 
     994        sage: A.get_context_test(8) #indirect doctest 
     995        NTL modulus 390625 
     996        """ 
     997        if n == 0: 
     998            raise ValueError, "n must be positive" 
     999        if n <= self.cache_limit: 
     1000            return self.context_list[n] 
     1001        elif n == self.prec_cap: 
     1002            return self.top_context 
     1003        else: 
     1004            try: 
     1005                return self.context_dict[n] 
     1006            except KeyError: 
     1007                self.context_dict[n] = PowComputer_ZZ_pX.get_context(self, n) 
     1008                return self.context_dict[n] 
     1009 
     1010    cdef ntl_ZZ_pContext_class get_top_context(self): 
     1011        """ 
     1012        Returns a ZZ_pContext for self.prime^self.prec_cap 
     1013         
     1014        sage: PC = PowComputer_ext_maker(5, 5, 10, False, ntl.ZZ_pX([-5,0,1],5^10), "big") 
     1015        sage: PC.get_top_context_test() # indirect doctest 
     1016        NTL modulus 9765625 
     1017        """         
     1018        return self.top_context 
     1019 
     1020    cdef void restore_top_context(self): 
     1021        """ 
     1022        Restores the context corresponding to self.prime^self.prec_cap 
     1023 
     1024        EXAMPLES: 
     1025        sage: PC = PowComputer_ext_maker(5, 5, 10, False, ntl.ZZ_pX([-5,0,1],5^10), "big") 
     1026        sage: PC.restore_top_context_test() #indirect doctest         
     1027        """ 
     1028        self.top_context.restore_c() 
     1029 
     1030    cdef ZZ_pX_Modulus_c* get_modulus(self, unsigned long n): 
     1031        """ 
     1032        Returns the modulus corresponding to self.polynomial() (mod self.prime^n). 
     1033 
     1034        INPUT: 
     1035        n -- A long between 1 and self.cache_limit, inclusive 
     1036 
     1037        EXAMPLES: 
     1038        sage: A = PowComputer_ext_maker(5, 3, 10, False, ntl.ZZ_pX([-5,0,1],5^10), "big") 
     1039        sage: a = ntl.ZZ_pX([4,2],5^2) 
     1040        sage: b = ntl.ZZ_pX([6,3],5^2) 
     1041        sage: A.get_modulus_test(a, b, 2) # indirect doctest 
     1042        [4 24] 
     1043        sage: a = ntl.ZZ_pX([4,2],5^6) 
     1044        sage: b = ntl.ZZ_pX([6,3],5^6) 
     1045        sage: A.get_modulus_test(a, b, 6) # indirect doctest 
     1046        [54 24] 
     1047        """ 
     1048        cdef ntl_ZZ_pX tmp 
     1049        cdef ntl_ZZ_pX_Modulus holder 
     1050        cdef ntl_ZZ_pContext_class c 
     1051        if n == 0: 
     1052            raise ValueError, "n must be positive" 
     1053        elif n <= self.cache_limit: 
     1054            return &(self.modulus_list[n]) 
     1055        elif n == self.prec_cap: 
     1056            return &self.top_mod 
     1057        else: 
     1058            try: 
     1059                holder = self.modulus_dict[n] 
     1060                return &(holder.x) 
     1061            except KeyError: 
     1062                c = self.get_context(n) 
     1063                c.restore_c() 
     1064                tmp = PY_NEW(ntl_ZZ_pX) 
     1065                tmp.c = c 
     1066                ZZ_pX_conv_modulus(tmp.x, self.top_mod.val(), c.x) 
     1067                holder = ntl_ZZ_pX_Modulus(tmp) 
     1068                self.modulus_dict[n] = holder 
     1069                return &(holder.x) 
     1070 
     1071    cdef ZZ_pX_Modulus_c* get_top_modulus(self): 
     1072        """ 
     1073        Returns the modulus corresponding to self.polynomial() (mod self.prime^self.prec_cap) 
     1074 
     1075        EXAMPLES: 
     1076        sage: A = PowComputer_ext_maker(5, 5, 10, False, ntl.ZZ_pX([-5,0,1],5^10), "big") 
     1077        sage: a = ntl.ZZ_pX([129223,1231],5^10) 
     1078        sage: b = ntl.ZZ_pX([289741,323],5^10) 
     1079        sage: A.get_top_modulus_test(a, b) #indirect doctest 
     1080        [1783058 7785200]          
     1081        """ 
     1082        return &self.top_mod 
     1083 
     1084 
     1085def PowComputer_ext_maker(prime, cache_limit, prec_cap, in_field, poly, prec_type = "small", ext_type = "u"): 
     1086    """ 
     1087    Returns a PowComputer that caches the values $1, prime, prime^2, \ldots, prime^cache_limit$. 
     1088 
     1089    Once you create a PowComputer, merely call it to get values out. 
     1090    You can input any integer, even if it's outside of the precomputed range. 
     1091 
     1092    INPUT: 
     1093    prime -- An integer, the base that you want to exponentiate. 
     1094    cache_limit -- A positive integer that you want to cache powers up to. 
     1095 
     1096    EXAMPLES: 
     1097    sage: PC = PowComputer_ext_maker(5, 10, 10, False, ntl.ZZ_pX([-5, 0, 1], 5^10), "small") 
     1098    sage: PC 
     1099    PowComputer_ext for 5, with polynomial [9765620 0 1] 
     1100    """ 
     1101    cdef Integer _prime = Integer(prime) 
     1102    cdef Integer _cache_limit = Integer(cache_limit) 
     1103    cdef Integer _prec_cap = Integer(prec_cap) 
     1104    cdef bint inf = in_field 
     1105    if prec_type == "small" and ext_type == "u": 
     1106        return PowComputer_ZZ_pX_small(_prime, mpz_get_ui(_cache_limit.value), mpz_get_ui(_prec_cap.value), inf, poly) 
     1107    elif prec_type == "small" and ext_type == "e": 
     1108        return PowComputer_ZZ_pX_small_Eis(_prime, mpz_get_ui(_cache_limit.value), mpz_get_ui(_prec_cap.value), inf, poly) 
     1109    elif prec_type == "big" and ext_type == "u": 
     1110        return PowComputer_ZZ_pX_big(_prime, mpz_get_ui(_cache_limit.value), mpz_get_ui(_prec_cap.value), inf, poly) 
     1111    elif prec_type == "big" and ext_type == "e": 
     1112        return PowComputer_ZZ_pX_big_Eis(_prime, mpz_get_ui(_cache_limit.value), mpz_get_ui(_prec_cap.value), inf, poly) 
     1113    elif prec_type == "FM" and ext_type == "u": 
     1114        return PowComputer_ZZ_pX_FM(_prime, mpz_get_ui(_cache_limit.value), mpz_get_ui(_prec_cap.value), inf, poly) 
     1115    elif prec_type == "FM" and ext_type == "e": 
     1116        return PowComputer_ZZ_pX_FM_Eis(_prime, mpz_get_ui(_cache_limit.value), mpz_get_ui(_prec_cap.value), inf, poly) 
     1117    else: 
     1118        ValueError, "prec_type must be one of 'small', 'big' or 'FM' and ext_type must be one of 'u' or 'e'" 
     1119 
     1120 
     1121cdef void Eis_init(PowComputer_ext prime_pow, ZZ_pX_Multiplier_c* low_shifter, ZZ_pX_Multiplier_c high_shifter, Integer prime, unsigned long cache_limit, unsigned long prec_cap, unsigned long deg, poly): 
     1122    cdef unsigned long D = self.deg - 1 
     1123    cdef int low_length = 0 
     1124    cdef int high_length = 0 
     1125    if sizeof(long) > 4 and D > 4294967295: # 2^32 - 1 
     1126        low_length += 32 
     1127        D = D >> 32 
     1128    if D >= 65536: # 2^16 
     1129        low_length += 16 
     1130        D = D >> 16 
     1131    if D >= 256: # 2^8 
     1132        low_length += 8 
     1133        D = D >> 8 
     1134    if D >= 16: # 2^4 
     1135        low_length += 4 
     1136        D = D >> 4 
     1137    if D >= 4: # 2^2 
     1138        low_length += 2 
     1139        D = D >> 2 
     1140    if D >= 2: # 2^1 
     1141        low_length += 1 
     1142        D = D >> 1 
     1143    low_length += 1 
     1144    # self.low_length is the number of elements in the list we need to store. 
     1145    # if self.deg = 2, self.low_length = 1 (store p/x) 
     1146    # if self.deg = 3,4, self.low_length = 2 (store p/x, p/x^2) 
     1147    # if self.deg = 5,6,7,8, self.low_length = 3 (store p/x, p/x^2, p/x^4) 
     1148    # if self.deg = 9,...,16, self.low_length = 4 (store p/x, p/x^2, p/x^4, p/x^8) 
     1149 
     1150    # Now we do the same process for powers of p, ie storing p^(2^k)/x^(e*2^k) 
     1151    D = self.prec_cap - 1 
     1152    high_length = 0 
     1153    if sizeof(long) > 4 and D > 4294967295: # 2^32 - 1 
     1154        high_length += 32 
     1155        D = D >> 32 
     1156    if D >= 65536: # 2^16 
     1157        high_length += 16 
     1158        D = D >> 16 
     1159    if D >= 256: # 2^8 
     1160        high_length += 8 
     1161        D = D >> 8 
     1162    if D >= 16: # 2^4 
     1163        high_length += 4 
     1164        D = D >> 4 
     1165    if D >= 4: # 2^2 
     1166        high_length += 2 
     1167        D = D >> 2 
     1168    if D >= 2: # 2^1 
     1169        high_length += 1 
     1170        D = D >> 1 
     1171    high_length += 1 
     1172    # self.high_length is the number of elements in the list we need to store. 
     1173    # if self.prec_cap = 2, self.high_length = 1 (store p/x^e) 
     1174    # if self.prec_cap = 3,4, self.high_length = 2 (store p/x^e, p^2/x^(2e)) 
     1175    # if self.prec_cap = 5,6,7,8, self.high_length = 3 (store p/x^e, p^2/x^(2e), p^4/x^(4e)) 
     1176    # if self.prec_cap = 9,...,16, self.high_length = 4 (store p/x, p^2/x^(2e), p^4/x^(4e), p^8/x^(8e)) 
     1177 
     1178    _sig_on 
     1179    low_shifter = <ZZ_pX_Multiplier_c *>sage_malloc(sizeof(ZZ_pX_Multiplier_c) * self.low_length) 
     1180    high_shifter = <ZZ_pX_Multiplier_c *>sage_malloc(sizeof(ZZ_pX_Multiplier_c) * self.high_length) 
     1181    _sig_off 
     1182    cdef long i 
     1183    cdef ZZ_pX_c tmp, modup, into_multiplier 
     1184    cdef ZZ_c a 
     1185    ZZ_construct(&a) 
     1186    # We obtain successive p/x^(2^i) by squaring and then dividing by p.  So we need one extra digit of precision. 
     1187    self.c.restore_c() 
     1188    ZZ_pX_construct(&into_multiplier) 
     1189    cdef ntl_ZZ_pContext_class cup = self.get_context(self.prec_cap + self.low_length) 
     1190    cup.restore_c() 
     1191    ZZ_pX_construct(&tmp) 
     1192    ZZ_pX_construct(&modup) 
     1193    ZZ_pX_conv_modulus(modup, self.mod.val(), cup.x) 
     1194    ZZ_div(a, ZZ_p_rep(ZZ_pX_ConstTerm(modup)), self.small_powers[1]) 
     1195    ZZ_InvMod(a, a, self.pow_ZZ_tmp(self.prec_cap + self.low_length)[0]) 
     1196    ZZ_negate(a, a) 
     1197    #cdef ntl_ZZ_pX printer = ntl_ZZ_pX([],cup) 
     1198    #printer.x = modup 
     1199    #print printer 
     1200    # Note that we're losing one digit of precision here. 
     1201    # This is correct because right shifting does not preserve precision. 
     1202    # a is now the negative of the inverse of the unit part of the constant of the defining polynomial (there's a mouthful) 
     1203    ZZ_pX_RightShift(tmp, modup, 1) 
     1204    ## printer.x = modup 
     1205    ## print printer 
     1206    ZZ_pX_mul_ZZ_p(tmp, tmp, ZZ_to_ZZ_p(a)) 
     1207    # tmp is now p/x 
     1208    ZZ_pX_conv_modulus(into_multiplier, tmp, self.c.x) 
     1209    ZZ_pX_Multiplier_construct(self.low_shifter) 
     1210    ZZ_pX_Multiplier_build(self.low_shifter[0], into_multiplier, self.mod) 
     1211    for i from 1 <= i < self.low_length: 
     1212        # Currently tmp = p / x^(2^(i-1)).  Squaring yields p^2 / x^(2^i) 
     1213        ZZ_pX_SqrMod(tmp, tmp, modup) 
     1214        # Now we divide by p.  We don't really have the extra digit of precision that cup would imply, but we're about to reduce, and then square. 
     1215        # This should give us one digit of precision loss, as expected. 
     1216        ZZ_pX_right_pshift(tmp, tmp, self.small_powers[1], cup.x) 
     1217        ZZ_pX_conv_modulus(into_multiplier, tmp, self.c.x) 
     1218        ZZ_pX_Multiplier_construct(&(self.low_shifter[i])) 
     1219        ZZ_pX_Multiplier_build(self.low_shifter[i], into_multiplier, self.mod) 
     1220 
     1221    # Now we handle high_shifter. 
     1222    # We can obtain p/x^e by computing the inverse of x^e/p. 
     1223    # Note that modup is still defined from before 
     1224    cup.restore_c() 
     1225 
     1226    ZZ_pX_conv_modulus(modup, self.mod.val(), cup.x) 
     1227    ZZ_pX_SetCoeff_long(modup, self.deg, 0) 
     1228    ZZ_pX_negate(modup, modup) 
     1229    ZZ_pX_right_pshift(into_multiplier, modup, self.small_powers[1], self.c.x) 
     1230 
     1231    # into_multiplier now holds x^e/p 
     1232    # self.c.x should have been restored, but we make sure 
     1233    self.c.restore_c() 
     1234    ZZ_pX_InvMod_newton(into_multiplier, into_multiplier, self.mod, self.c.x, (<ntl_ZZ_pContext_class>self.get_context(1)).x) 
     1235    ZZ_pX_Multiplier_construct(self.high_shifter) 
     1236    ZZ_pX_Multiplier_build(self.high_shifter[0], into_multiplier, self.mod) 
     1237    # Now we cache powers of p/x^e.  This is a unit, so we don't have to worry about precision issues (yay!) 
     1238    for i from 1 <= i < self.high_length: 
     1239        ZZ_pX_SqrMod_pre(into_multiplier, into_multiplier, self.mod) 
     1240        ZZ_pX_Multiplier_construct(&(self.high_shifter[i])) 
     1241        ZZ_pX_Multiplier_build(self.high_shifter[i], into_multiplier, self.mod) 
     1242 
     1243    # I'm not sure whether I need to destruct the temporary variables. 
     1244    # ZZ_pX_destruct(&tmp) 
     1245    # ZZ_pX_destruct(&modup) 
     1246    # ZZ_pX_destruct(&into_multiplier) 
     1247    # ZZ_destruct(&a) 
Note: See TracChangeset for help on using the changeset viewer.