Changeset 3408:51894e033e7b


Ignore:
Timestamp:
03/10/07 16:50:04 (6 years ago)
Author:
David Roe <roed@…>
Branch:
default
Message:

Shifting, working on lots of stuff

Location:
sage/rings
Files:
15 edited

Legend:

Unmodified
Added
Removed

  • sage/rings/integer.pxd

    r3229 r3408  
    1616    cdef ModuleElement _neg_c_impl(self) 
    1717 
    18     cdef _lshift(self, unsigned long int n) 
    19     cdef _rshift(Integer self, unsigned long int n) 
     18    cdef _lshift(self, long int n) 
     19    cdef _rshift(Integer self, long int n) 
    2020    cdef _and(Integer self, Integer other) 
    2121    cdef _or(Integer self, Integer other) 

  • sage/rings/integer.pyx

    r3370 r3408  
    16371637        return g0, s0, t0 
    16381638 
    1639     cdef _lshift(self, unsigned long int n): 
     1639    cdef _lshift(self, long int n): 
    16401640        """ 
    16411641        Shift self n bits to the left, i.e., quickly multiply by $2^n$. 
    16421642        """ 
    16431643        cdef Integer x 
    1644         x = Integer() 
     1644        x = <Integer> PY_NEW(Integer) 
    16451645 
    16461646        _sig_on 
    1647         mpz_mul_2exp(x.value, self.value, n) 
     1647        if n < 0: 
     1648            mpz_fdiv_q_2exp(x.value, self.value, -n) 
     1649        else: 
     1650            mpz_mul_2exp(x.value, self.value, n) 
    16481651        _sig_off 
    16491652        return x 
    … …  
    16651668        return bin_op(x, y, operator.lshift) 
    16661669     
    1667     cdef _rshift(Integer self, unsigned long int n): 
     1670    cdef _rshift(Integer self, long int n): 
    16681671        cdef Integer x 
    1669         x = Integer() 
     1672        x = <Integer> PY_NEW(Integer) 
     1673         
    16701674        _sig_on 
    1671         mpz_fdiv_q_2exp(x.value, self.value, n) 
     1675        if n < 0: 
     1676            mpz_mul_2exp(x.value, self.value, -n) 
     1677        else: 
     1678            mpz_fdiv_q_2exp(x.value, self.value, n) 
    16721679        _sig_off 
    16731680        return x 

  • sage/rings/padics/README/README.tex

    r3403 r3408  
    7878The different ways of doing this account for the different types of $p$-adics. 
    7979 
    80 We have the following definition of the $p$-adic integers: 
     80We can think of $p$-adics in two ways.  First, as a projective limit of finite groups: 
    8181$$\Zp = \lim_{\leftarrow n} \Zpn.$$ 
    82 In order to store a $p$-adic integer to a given finite precision level, 
    83 we can merely store it as an element of $\Zpn$ for some $n$. 
     82Secondly, as Cauchy sequences of rationals (or integers, in the case of $\Zp$, under the 
     83$p$-adic metric.  Since we only need to consider these sequences up to equivalence, this 
     84second way of thinking of the $p$-adics is the same as considering power series in $p$ with 
     85integral coefficients in the range $0$ to $p-1$.  If we only allow nonnegative powers of $p$ 
     86then these power series converge to elements of $\Zp$, and if we allow bounded negative powers 
     87of $p$ then we get $\Qp$. 
     88 
     89Both of these representations give a natural way of thinking about finite approximations to a 
     90$p$-adic element.  In the first representation, we can just stop at some point 
     91in the projective limit, giving an element of $\Zpn$.  As $\Zp / p^n\Zp \cong \Zpn$, 
     92this is is equivalent to specifying our element modulo $p^n\Zp$. 
    8493\begin{definition} 
    8594The \emph{absolute precision} of a finite approximation $\bar{x} \in \Zpn$ to $x \in \Zp$ 
    8695is the non-negative integer $n$. 
    8796\end{definition} 
     97In the second representation, we can achieve the same thing by truncating a series  
     98$$a_0 + a_1 p + a_2 p^2 + \cdots$$ 
     99at $p^n$, yielding 
     100$$a_0 + a_1 p + \cdots + a_{n-1} p^{n-1} + O(p^n).$$ 
     101As above, we call this $n$ the absolute precision of our element. 
     102 
     103Given any $x \in \Qp$ with $x \ne 0$, we can write $x = p^v u$ where $v \in \ZZ$ and $u \in Zpx$. 
     104We could thus also store an element of $\Qp$ (or $\Zp$) by storing $v$ and a finite approximation 
     105of $u$.  This motivates the following definition: 
     106\begin{definition} 
     107The \emph{relative precision} of an approximation to $x$ is defined as the absolute precision 
     108of the approximation minus the valuation of $x$. 
     109\end{definition} 
     110For example, if $x = a_k p^k + a_{k+1} p^{k+1} + \cdots + a_{n-1} p^{n-1} + O(p^n)$  then the 
     111absolute precision of $x$ is $n$, the valuation of $x$ is $k$ and the relative precision of $x$ 
     112is $n-k$. 
     113 
     114There are four different representations of $\Zp$ in Sage and two representations of $\Qp$: 
     115the fixed modulus ring, the capped absolute precision ring, the capped relative precision 
     116ring, the capped relative precision field, the lazy ring and the lazy field. 
     117 
     118\subsection{Fixed Modulus Rings} 
     119The first, and simplest, type of $\Zp$ is basically a wrapper around $\Zpn$, providing a 
     120unified interface with the rest of the $p$-adics.  You specify a precision, and all elements 
     121are stored to that absolute precision.  If you perform an operation that would normally lose 
     122precision, the element does not track that it no longer has full precision. 
     123 
     124The fixed modulus ring provide the lowest level of convenience, but it is also the one that 
     125has the lowest computational overhead.  Once we have ironed out some bugs, the fixed modulus 
     126elements will be those most optimized for speed. 
     127 
     128As with all of the implementations of $\Zp$, one creates a new ring using the constructor 
     129\verb/Zp/, and passing in \verb/'fixed-mod'/ for the \verb/type/ parameter.  For example, 
     130\begin{verbatim} 
     131sage: R = Zp(5, prec = 10, type = 'fixed-mod', print_mode = 'series') 
     132sage: R 
     1335-adic Ring of fixed modulus 5^10 
     134\end{verbatim} 
     135 
     136One can create elements as follows: 
     137\begin{verbatim} 
     138sage: a = R(375) 
     139sage: a 
     1403*5^3 + O(5^10) 
     141sage: b = R(105) 
     142sage: b 
     1435 + 4*5^2 + O(5^10) 
     144\end{verbatim} 
     145 
     146Now that we have some elements, we can do arithmetic in the ring. 
     147\begin{verbatim} 
     148sage: a + b 
     1495 + 4*5^2 + 3*5^3 + O(5^10) 
     150sage: a * b 
     1513*5^4 + 2*5^5 + 2*5^6 + O(5^10) 
     152sage: a // 5 
     1533*5^2 + O(5^10) 
     154\end{verbatim} 
     155 
     156Since elements don't actually store their actual precision, one can only divide by units: 
     157\begin{verbatim} 
     158sage: a / 2 
     1594*5^3 + 2*5^4 + 2*5^5 + 2*5^6 + 2*5^7 + 2*5^8 + 2*5^9 + O(5^10) 
     160sage: a / b 
     161... 
     162<type 'exceptions.ValueError'>: cannot invert non-unit 
     163\end{verbatim} 
     164 
     165If you want to divide by a non-unit, do it using the \verb@//@ operator: 
     166\begin{verbatim} 
     167sage: a // b 
     1683*5^2 + 3*5^3 + 2*5^5 + 5^6 + 4*5^7 + 2*5^8 + O(5^10) 
     169\end{verbatim} 
     170 
     171\subsection{Capped Absolute Rings} 
     172The second type of implementation of $\Zp$ is similar to the fixed modulus implementation, 
     173except that individual elements track their known precision.  
     174The absolute precision of each element is limited to be less than the precision cap of the ring, 
     175even if mathematically the precision of the element would be known to greater precision 
     176(see Appendix A for the reasons for the existence of a precision cap). 
     177 
     178Once again, use \verb/Zp/ to create a capped absolute $p$-adic ring. 
     179\begin{verbatim} 
     180sage: R = Zp(5, prec = 10, type = 'capped-abs', print_mode = 'series') 
     181sage: R 
     1825-adic Ring with capped absolute precision 10 
     183\end{verbatim} 
     184 
     185We can do similar things as in the fixed modulus case: 
     186\begin{verbatim} 
     187sage: a = R(375) 
     188sage: a 
     1893*5^3 + O(5^10) 
     190sage: b = R(105) 
     191sage: b 
     1925 + 4*5^2 + O(5^10) 
     193sage: a + b 
     1945 + 4*5^2 + 3*5^3 + O(5^10) 
     195sage: a * b 
     1963*5^4 + 2*5^5 + 2*5^6 + O(5^10) 
     197sage: c = a // 5 
     198sage: c 
     1993*5^2 + O(5^9) 
     200\end{verbatim} 
     201 
     202Note that when we divided by 5, the precision of \verb/c/ dropped.  This lower precision is now reflected in arithmetic. 
     203\begin{verbatim} 
     204sage: c + b 
     2055 + 2*5^2 + 5^3 + O(5^9) 
     206\end{verbatim} 
     207 
     208Division is allowed: the element that results is a capped relative field element, which is discussed in the next section: 
     209\begin{verbatim} 
     210sage: 1 / (c + b) 
     2115^-1 + 3 + 2*5 + 5^2 + 4*5^3 + 4*5^4 + 3*5^6 + O(5^7) 
     212\end{verbatim} 
     213 
     214\subsection{Capped Relative Rings and Fields} 
     215Instead of restricting the absolute precision of elements (which doesn't make much sense when elements have negative 
     216valuations), one can cap the relative precision of elements.  This is analogous to floating point representations 
     217of real numbers.  As in the reals, multiplication works very well: the valuations add and the relative precision of 
     218the product is the minimum of the relative precisions of the inputs.   Addition, however, faces similar issues as 
     219floating point addition: relative precision is lost when lower order terms cancel. 
     220 
     221To create a capped relative precision ring, use \verb/Zp/ as before.  To create capped relative precision fields, use 
     222\verb/Qp/. 
     223\begin{verbatim} 
     224sage: R = Zp(5, prec = 10, type = 'capped-rel', print_mode = 'series') 
     225sage: R 
     2265-adic Ring with capped relative precision 10 
     227sage: K = Qp(5, prec = 10, type = 'capped-rel', print_mode = 'series') 
     228sage: K 
     2295-adic Field with capped relative precision 10 
     230\end{verbatim} 
     231 
     232We can do all of the same operations as in the other two cases, but precision works a bit differently: 
     233the maximum precision of an element is limited by the precision cap of the ring. 
     234\begin{verbatim} 
     235sage: a = R(375) 
     236sage: a 
     2373*5^3 + O(5^13) 
     238sage: b = K(105) 
     239sage: b 
     2405 + 4*5^2 + O(5^11) 
     241sage: a + b 
     2425 + 4*5^2 + 3*5^3 + O(5^11) 
     243sage: a * b 
     2443*5^4 + 2*5^5 + 2*5^6 + O(5^14) 
     245sage: c = a // 5 
     246sage: c 
     2473*5^2 + O(5^12) 
     248sage: c + 1 
     2491 + 3*5^2 + O(5^10) 
     250\end{verbatim} 
     251 
     252As with the capped absolute precision rings, we can divide, yielding a capped relative precision field element. 
     253\begin{verbatim} 
     254sage: 1 / (c + b) 
     2555^-1 + 3 + 2*5 + 5^2 + 4*5^3 + 4*5^4 + 3*5^6 + 2*5^7 + 5^8 + O(5^9) 
     256\end{verbatim} 
     257 
     258\subsection{Lazy Rings and Fields} 
     259The model for lazy elements is quite different from any of the other types of $p$-adics. 
     260In addition to storing a finite approximation, one also stores a method for increasing 
     261the precision.  The interface supports two ways to do this: \verb/set_precision_relative/ and  
     262\verb/set_precision_absolute/. 
     263 
     264\begin{verbatim} 
     265sage: R = Zp(5, prec = 10, type = 'lazy', print_mode = 'series', halt = 30) 
     266sage: R 
     267Lazy 5-adic Ring 
     268sage: R.precision_cap() 
     26910 
     270sage: R.halting_parameter() 
     27130 
     272sage: K = Qp(5, type = 'lazy') 
     273sage: K.precision_cap() 
     27420 
     275sage: K.halting_parameter() 
     27640 
     277\end{verbatim} 
     278 
     279There are two parameters that are set at the creation of a lazy ring or field.  The first is \verb/prec/, which 
     280controls the precision to which elements are initially computed.  When computing with lazy rings, sometimes situations 
     281arise where the insolvability of the halting problem gives us problems.  For example, 
     282\begin{verbatim} 
     283sage: a = R(16) 
     284sage: b = a.log().exp() - a 
     285sage: b 
     286 
     287sage b.valuation() 
     288 
     289 
     290The second is \verb/halt/ 
     291 
     292\begin{verbatim} 
    88293 
    89294 

  • sage/rings/padics/padic_field_capped_relative_element.py

    r3407 r3408  
    233233    def _integer_(self): 
    234234        return self._unit.lift() * self.parent().prime_pow(self.valuation()) 
     235 
     236    def __lshift__(self, shift): 
     237        shift = Integer(shift) 
     238        return pAdicFieldCappedRelativeElement(self.parent(), (self.valuation() + shift, self._unit, self._relprec), construct = True) 
     239 
     240    def __rshift__(self, shift): 
     241        shift = Integer(shift) 
     242        return pAdicFieldCappedRelativeElement(self.parent(), (self.valuation() - shift, self._unit, self._relprec), construct = True) 
    235243 
    236244    def _mul_(self, right): 

  • sage/rings/padics/padic_field_generic_element.py

    r3312 r3408  
    4040        else: 
    4141            return self.list()[n - v] 
     42 
     43    def __floordiv__(self, right): 
     44        return self / right 
     45 
     46    def __mod__(self, right): 
     47        if right == 0: 
     48            raise ZeroDivisionError 
     49        return self.parent()(0) 

  • sage/rings/padics/padic_generic.py

    r3346 r3408  
    116116                243 
    117117        """ 
    118         if n != infinity: 
     118        if n is infinity: 
     119            return 0 
     120        elif n < 0: 
     121            raise ValueError, "should not use prime_pow to compute negative powers of p.  Use 1 / prime_pow(-n) instead." 
     122        else: 
    119123            return self._p ** n 
    120         return 0 
    121124 
    122125    def residue_characteristic(self): 

  • sage/rings/padics/padic_generic_element.py

    r3401 r3408  
    568568        elif self.is_unit(): 
    569569            z = self.unit_part() 
    570             return (z**Integer(p-1)).log()/Integer(p-1) 
     570            return (z**Integer(p-1)).log() // Integer(p-1) 
    571571        else: 
    572572            raise ValueError, "not a unit" 

  • sage/rings/padics/padic_lazy_element.py

    r3407 r3408  
    7272        if isinstance(self, pAdicLazy_zero): 
    7373            return self 
    74         return pAdicLazy_floordiv(self, right) 
     74        try: 
     75            right.set_precision_relative(1) 
     76        except PrecisionError: 
     77            raise ZeroDivisionError, "Cannot divide by a p-adic very close to zero.  Casting both into a lazy ring with higher halting parameter may help" 
     78        return pAdicLazy_rshift(self / right.unit_part(), right.valuation()) 
    7579 
    7680    def __getitem__(self, n): 
    … …  
    9599        return (self._cache.lift() // ppow) % self.parent().prime() 
    96100 
     101    def __lshift__(self, shift): 
     102        shift = Integer(shift) 
     103        if shift < 0 and not self.parent().is_field(): 
     104            return pAdicLazy_rshift(self, -shift) 
     105        return pAdicLazy_lshift(self, shift) 
     106 
     107    def __rshift__(self, shift): 
     108        shift = Integer(shift) 
     109        if shift < 0 or self.parent().is_field(): 
     110            return pAdicLazy_lshift(self, -shift) 
     111        return pAdicLazy_rshift(self, shift) 
     112 
    97113    def __mod__(self, right): 
     114        right = self.parent()(right) 
    98115        if self.parent().is_field() or self.valuation() > right.valuation() or isinstance(self, pAdicLazy_zero): 
    99116            return pAdicLazy_zero(self.parent()) 
     117        #return self - right * (self // right) #can be made more efficient 
    100118        try: 
    101119            right.set_precision_relative(1) 
    … …  
    148166 
    149167    def exp(self): 
    150         #Do valuation checking 
     168        if self._is_unit(): 
     169            raise ValueError, "cannot take exp of a unit" 
    151170        return pAdicLazy_exp(self) 
    152171 
    … …  
    207226 
    208227    def log(self): 
    209         #Do valuation checking 
    210         return pAdic_log(self) 
     228        if not self.is_unit(): 
     229            raise ValueError, "cannot take log of a non-unit" 
     230        return pAdicLazy_log(self) 
    211231 
    212232    def log_artin_hasse(self): 
    … …  
    228248        self.set_precision_absolute(n) 
    229249        try: 
    230             return Mod(self._cache.lift() * self.parent().prime_pow(self._base_valuation()), self.parent().prime_pow(n)) 
     250            return Mod(self._cache.lift() * self.parent().prime_pow(self._base_valuation), self.parent().prime_pow(n)) 
    231251        except ZeroDivisionError: 
    232252            raise ValueError, "element must have non-negative valuation in order to compute residue" 
    … …  
    538558        self._set_cache(self._x._cache * self._y._cache) 
    539559 
    540 class pAdicLazy_divtype(pAdicLazy_multype): 
     560class pAdicLazy_div(pAdicLazy_multype): 
    541561    def __init__(self, x, y, halt = None): 
    542562        pAdicGenericElement.__init__(self, x.parent().fraction_field()) 
    … …  
    549569        self._recompute() 
    550570 
    551 class pAdicLazy_div(pAdicLazy_divtype): 
    552571    def _recompute(self): 
    553572        self._set_base_valuation(self._x._base_valuation - self._y._base_valuation) 
    … …  
    555574        self._set_cache(self._x._cache / self._y._cache) 
    556575 
    557 class pAdicLazy_floordiv(pAdicLazyElement): 
    558     def __init__(self, x, y, halt = None): 
    559         self._u = x / y.unit_part() 
    560         pAdicLazy_divtype.__init__(self, x.parent()) 
    561  
    562     def _recompute(self): 
    563         #This is wrong 
    564         self._u._recompute()  
    565         top = self._u._cache.lift() 
    566         shift = y._base_valuation - x._base_valuation + x._min_valuation() 
    567         bottom = x.parent().prime_pow(shift) 
    568         ans = top // bottom 
    569         self._cache_prec = x._cache_prec + x._base_valuation - shift 
    570         self._cache = Mod(ans, self._cache_prec) 
     576class pAdicLazy_lshift(pAdicLazyElement): 
     577    def __init__(self, x, shift): #self can be a ring or field element, shift positive or negative integer.  If a ring element, shift is positive 
     578        pAdicGenericElement.__init__(self, x.parent()) 
     579        self._x = x 
     580        self._shift = shift 
     581        self._recompute() 
     582 
     583    def _recompute(self): 
     584        self._set_base_valuation(self._x._base_valuation + self._shift) 
     585        self._set_cache_prec(self._x._cache_prec) 
     586        self._set_cache(self._x._cache) 
     587 
     588    def set_precision_relative(self, n, halt = None): 
     589        self._x.set_precision_relative(n, halt) 
     590        self._recompute() 
     591 
     592    def set_precision_absolute(self, n, halt = None): 
     593        self._x.set_precision_absolute(n + self._shift) 
     594 
     595class pAdicLazy_rshift(pAdicLazyElement): 
     596    def __init__(self, x, shift): #self is a ring element and shift is nonnegative 
     597        pAdicGenericElement.__init__(self, x.parent()) 
     598        x.set_precision_relative(shift + 1) #I'm being a bit lazy here, so that the code in recompute is simpler 
     599        self._x = x 
     600        self._shift = shift 
     601        self._recompute() 
     602 
     603    def _recompute(self): 
     604        val = self._x.valuation() 
     605        if self._shift <= val: 
     606            self._set_base_valuation(val - self._shift) 
     607            self._set_cache(self._x._cache) 
     608            self._set_cache_prec(self._x._cache_prec) 
     609            self._suck = Integer(0) 
     610        else: 
     611            shift = self._shift 
     612            unit = self._x._unit_part().lift() // self.parent().prime_pow(shift - val) 
     613            val = unit.valuation(self.parent().prime()) 
     614            rprec = self._x.precision_absolute() - shift 
     615            if val is infinity: 
     616                self._suck = self._x.precision_relative() #this might not be right 
     617                val = max(rprec, Integer(0)) 
     618                rprec = Integer(0) 
     619                unit = Mod(0, 1) 
     620            elif val > 0: 
     621                self._suck = shift - self._x.valuation() + val 
     622                rprec = rprec - val 
     623                unit = Mod(unit // self.parent().prime_pow(val), self.parent().prime_pow(rprec)) 
     624            else: 
     625                self._suck = shift - self._x.valuation() 
     626                unit = Mod(unit, self.parent().prime_pow(rprec)) 
     627            self._set_base_valuation(val) 
     628            self._set_cache(unit) 
     629            self._set_cache_prec(rprec) 
     630 
     631    def set_precision_relative(self, n, halt = None): 
     632        if n > self.precision_relative(): 
     633            self._x.set_precision_relative(n + self._suck) 
     634            self._recompute() 
     635 
     636    def set_precision_absolute(self, n, halt = None): 
     637        if n > self.precision_absolute(): 
     638            self._x.set_precision_absolute(n + self._shift) 
    571639 
    572640class pAdicLazy_pow(pAdicLazyElement): 
    … …  
    679747 
    680748class pAdicLazy_log(pAdicLazyElement): 
    681     def __init__(self, x): 
    682         pAdicGenericElement.__init__(self, x.parent()) 
    683         self._x = x 
    684         raise NotImplementedError 
     749    def __init__(self, x): #x must be a unit 
     750        pAdicGenericElement.__init__(self, x.parent()) 
     751        if x.residue(1) == 1: 
     752            self._x = x 
     753            self._n = Integer(1) 
     754        else: 
     755            self._x = x.__pow__(x.parent().prime() - 1) 
     756            self._n = x.parent().prime() - 1 
     757        self._recompute() 
     758 
     759    def _recompute(self): 
     760        p = self.parent().prime() 
     761        prec = self._x.precision_absolute() 
     762        extra_prec = 0 
     763        while extra_prec < Integer(prec + extra_prec).exact_log(p): 
     764            extra_prec += 1 
     765        from sage.rings.padics.zp import Zp 
     766        working_ring = Zp(p, prec + extra_prec, type = 'capped-abs') 
     767        x = working_ring(Integer(1) - self._x.residue(prec).lift()) 
     768        xpow = x 
     769        ans = working_ring(0) 
     770        for n in range(1, prec + extra_prec): 
     771            ans -= xpow // working_ring(n) 
     772            xpow *= x 
     773        ans = ans // self._n 
     774        ans = ans.residue(prec) 
     775        val = ans.lift().valuation(self.parent().prime()) 
     776        ans = Mod(ans.lift() // self.parent().prime_pow(val), self.parent().prime_pow(prec - val)) 
     777        self._set_cache(ans) 
     778        self._set_base_valuation(val) 
     779        self._set_cache_prec(prec - self._base_valuation) 
     780 
     781    def set_precision_absolute(self, n): 
     782        if n > self.precision_absolute(): 
     783            self._x.set_precision_absolute(n) 
     784            self._recompute() 
     785 
     786    def set_precision_relative(self, n): 
     787        if n > self.precision_relative(): 
     788            v = self.valuation() 
     789            self._x.set_precision_absolute(v + n) 
     790            self._recompute() 
    685791 
    686792class pAdicLazy_exp(pAdicLazyElement): 

  • sage/rings/padics/padic_ring_capped_absolute_element.py

    r3407 r3408  
    143143 
    144144    def _neg_(self): 
     145        """ 
     146        Returns -x. 
     147 
     148        INPUT: 
     149        x -- a p-adic capped absolute element 
     150        OUTPUT: 
     151        -x 
     152 
     153        EXAMPLES: 
     154        sage: R = Zp(5, prec=10, type='capped-abs') 
     155        sage: a = R(1) 
     156        sage: -a 
     157        4 + 4*5 + 4*5^2 + 4*5^3 + 4*5^4 + 4*5^5 + 4*5^6 + 4*5^7 + 4*5^8 + 4*5^9 + O(5^10) 
     158        """ 
    145159        return pAdicRingCappedAbsoluteElement(self.parent(), (-self._value, self._absprec), construct = True) 
    146160 
    … …  
    158172        return self * right.__invert__() 
    159173 
    160     def __floordiv__(self, right): 
    161         #There is still a bug in here 
    162         if isinstance(right, Integer): 
    163             right = pAdicRingCappedAbsoluteElement(self.parent(), right) 
    164         rval = right.valuation() 
    165         ppow = self.parent().prime_pow(rval) 
    166         runit = right._unit_part() 
    167         prec = min(self.precision_absolute(), right.precision_relative() + self.valuation()) 
    168         quotient = Mod(self._value.lift(), self.parent().prime_pow(prec)) / Mod(runit, self.parent().prime_pow(prec)) 
    169         return pAdicRingCappedAbsoluteElement(self.parent(), (Mod(quotient.lift() // ppow, self.parent().prime_pow(self.parent().precision_cap())), min(self.precision_relative(), right.precision_relative()) + self.valuation() - rval), construct = True) 
    170  
    171     def __mod__(self, right): 
    172         rval = right.valuation() 
    173         ppow = self.parent().prime_pow(rval) 
    174         runit = right.unit_part() 
    175         quotient = self / runit 
    176         return pAdicRingCappedAbsoluteElement(self.parent(), (Mod(quotient.lift() % ppow, self.parent().prime_pow(self.parent().precision_cap())), self.parent().precision_cap()), construct = True) 
    177          
     174    #def __floordiv__(self, right): 
     175    #    #There is still a bug in here 
     176    #    if isinstance(right, Integer): 
     177    #        right = pAdicRingCappedAbsoluteElement(self.parent(), right) 
     178    #    rval = right.valuation() 
     179    #    ppow = self.parent().prime_pow(rval) 
     180    #    runit = right._unit_part() 
     181    #    prec = min(self.precision_absolute(), right.precision_relative() + self.valuation()) 
     182    #    #print "self = %s, right = %s, rval = %s, runit = %s, prec = %s"%(self, right, rval, runit, prec) 
     183    #    quotient = Mod(self._value.lift(), self.parent().prime_pow(prec)) / Mod(runit, self.parent().prime_pow(prec)) 
     184    #    return pAdicRingCappedAbsoluteElement(self.parent(), (Mod(quotient.lift() // ppow, self.parent().prime_pow(self.parent().precision_cap())), min(self.precision_relative(), right.precision_relative()) + self.valuation() - rval), construct = True) 
     185 
     186    #def __mod__(self, right): 
     187    #    rval = right.valuation() 
     188    #    ppow = self.parent().prime_pow(rval) 
     189    #    runit = right.unit_part() 
     190    #    quotient = self / runit 
     191    #    return pAdicRingCappedAbsoluteElement(self.parent(), (Mod(quotient.lift() % ppow, self.parent().prime_pow(self.parent().precision_cap())), self.parent().precision_cap()), construct = True) 
     192 
     193    def __lshift__(self, shift): 
     194        shift = Integer(shift) 
     195        if shift < 0: 
     196            return self.__rshift__(-shift) 
     197        return pAdicRingCappedAbsoluteElement(self.parent(), (Mod(self._value.lift() *self.parent().prime_pow(shift), self.parent().prime_pow(self.parent().precision_cap())), self.precision_absolute() + shift), construct = True) 
     198 
     199    def __rshift__(self, shift): 
     200        shift = Integer(shift) 
     201        if shift < 0: 
     202            return self.__lshift__(-shift) 
     203        if shift > self.precision_absolute(): 
     204            return pAdicRingCappedAbsoluteElement(self.parent(), (Mod(0, self.parent().prime_pow(self.parent().precision_cap())), Integer(0)), construct = True) 
     205        return pAdicRingCappedAbsoluteElement(self.parent(), (Mod(self._value.lift() // self.parent().prime_pow(shift), self.parent().prime_pow(self.parent().precision_cap())), self.precision_absolute() - shift), construct = True) 
    178206 
    179207    def _mul_(self, right): 

  • sage/rings/padics/padic_ring_capped_relative_element.py

    r3407 r3408  
    304304        if isinstance(right, Integer): 
    305305            right = pAdicRingCappedRelativeElement(self.parent(), right) 
     306        return (self / right.unit_part()).__rshift__(right.valuation()) 
     307 
     308    #    val = self.valuation() 
     309    #    rval = right.valuation() 
     310    #    if val >= rval: 
     311    #        prec = min(self.precision_absolute() - rval, right.precision_relative()) 
     312    #        return pAdicRingCappedRelativeElement(self.parent(), (val - rval, Mod(self._unit.lift(), self.parent().prime_pow(prec)) / Mod(right._unit.lift(), self.parent().prime_pow(prec)), prec), construct = True) 
     313    #    else: 
     314    #        ppow = self.parent().prime_pow(rval - val) 
     315    #        u = (self._unit / right._unit).lift() // ppow 
     316    #        uval = u.valuation(self.parent().prime()) 
     317    #        prec = min(self.precision_absolute() - rval - uval, right.precision_relative()) 
     318    #        return pAdicRingCappedRelativeElement(self.parent(), (uval, Mod(u / self.parent().prime_pow(uval), self.parent().prime_pow(prec)), prec), construct = True) 
     319 
     320    def __lshift__(self, shift): 
     321        shift = Integer(shift) 
     322        if shift < 0: 
     323            return self.__rshift__(-shift) 
     324        return pAdicRingCappedRelativeElement(self.parent(), (self.valuation() + shift, self._unit_part(), self.precision_relative()), construct = True) 
     325 
     326    def __rshift__(self, shift): 
     327        shift = Integer(shift) 
     328        if shift < 0: 
     329            return self.__lshift__(-shift) 
    306330        val = self.valuation() 
    307         rval = right.valuation() 
    308         if val >= rval: 
    309             prec = min(self.precision_absolute() - rval, right.precision_relative()) 
    310             return pAdicRingCappedRelativeElement(self.parent(), (val - rval, Mod(self._unit.lift(), self.parent().prime_pow(prec)) / Mod(right._unit.lift(), self.parent().prime_pow(prec)), prec), construct = True) 
    311         else: 
    312             ppow = self.parent().prime_pow(rval - val) 
    313             u = (self._unit / right._unit).lift() // ppow 
    314             uval = u.valuation(self.parent().prime()) 
    315             prec = min(self.precision_absolute() - rval - uval, right.precision_relative()) 
    316             return pAdicRingCappedRelativeElement(self.parent(), (uval, Mod(u / self.parent().prime_pow(uval), self.parent().prime_pow(prec)), prec), construct = True) 
    317  
    318     def __mod__(self, right): 
    319         if isinstance(right, Integer): 
    320             right = pAdicRingCappedRelativeElement(self.parent(), right) 
    321         val = self.valuation() 
    322         rval = right.valuation() 
    323         if val >= rval: 
    324             return pAdicRingCappedRelativeElement(self.parent(), 0) 
    325         else: 
    326             ppow = self.parent().prime_pow(rval - val) 
    327             u = (self._unit / right._unit).lift() % ppow 
    328             return pAdicRingCappedRelativeElement(self.parent(), (self.valuation(), Mod(u, self.parent().prime_pow(self.parent().precision_cap())), self.parent().precision_cap()), construct = True) 
     331        if shift <= val: 
     332            val = val - shift 
     333            unit = self._unit_part() 
     334            rprec = self.precision_relative() 
     335        else: 
     336            unit = self._unit_part().lift() // self.parent().prime_pow(shift - val) 
     337            val = unit.valuation(self.parent().prime()) 
     338            rprec = self.precision_relative() + self.valuation() - shift 
     339            if val is infinity: 
     340                unit = Mod(0, 1) 
     341                val = max(rprec, Integer(0)) 
     342                rprec = Integer(0) 
     343            elif val > 0: 
     344                rprec = rprec - val 
     345                unit = Mod(unit // self.parent().prime_pow(val), self.parent().prime_pow(rprec)) 
     346            else: 
     347                unit = Mod(unit, self.parent().prime_pow(rprec)) 
     348        return pAdicRingCappedRelativeElement(self.parent(), (val, unit, rprec), construct = True) 
     349 
     350    #def __mod__(self, right): 
     351    #    if isinstance(right, Integer): 
     352    #        right = pAdicRingCappedRelativeElement(self.parent(), right) 
     353    #    val = self.valuation() 
     354    #    rval = right.valuation() 
     355    #    if val >= rval: 
     356    #        return pAdicRingCappedRelativeElement(self.parent(), 0) 
     357    #    else: 
     358    #        ppow = self.parent().prime_pow(rval - val) 
     359    #        u = (self._unit / right._unit).lift() % ppow 
     360    #        return pAdicRingCappedRelativeElement(self.parent(), (self.valuation(), Mod(u, self.parent().prime_pow(self.parent().precision_cap())), self.parent().precision_cap()), construct = True) 
    329361 
    330362    def _integer_(self): 

  • sage/rings/padics/padic_ring_fixed_mod_element.py

    r3407 r3408  
    193193            return pAdicRingFixedModElement(self.parent(), inverse, construct = True) 
    194194 
    195     def __mod__(self, right): 
    196         r""" 
    197         Returns self modulo right. 
    198          
    199         This doesn't make a whole lot of sense :-) but things are defined so 
    200         that always (x // y) * y + (x % y) == x. 
    201          
    202         TODO: 
    203             -- write down a full and proper explanation of the exact semantics 
    204             of floordiv and mod for all padic rings/fields; this should go 
    205             in a single overall doc file somewhere, and a reference to it 
    206             plus a summary should go in this docstring 
    207             -- make this work when "right" is e.g. an Integer -- perhaps 
    208             the mod operator needs to be brought under the SAGE arithmetic 
    209             architecture umbrella 
    210              
    211         """ 
    212         val = self.valuation() 
    213         rval = right.valuation() 
    214         quotient =  self / right._unit_part() 
    215         return pAdicRingFixedModElement(self.parent(), 
    216                      Mod(quotient.lift() % self.parent().prime_pow(rval), 
    217                      self.parent().prime_pow(self.parent().precision_cap())), 
    218                      construct = True) 
     195    #def __mod__(self, right): 
     196    #    r""" 
     197    #    Returns self modulo right. 
     198    #     
     199    #    This doesn't make a whole lot of sense :-) but things are defined so 
     200    #    that always (x // y) * y + (x % y) == x. 
     201    #     
     202    #    TODO: 
     203    #        -- write down a full and proper explanation of the exact semantics 
     204    #        of floordiv and mod for all padic rings/fields; this should go 
     205    #        in a single overall doc file somewhere, and a reference to it 
     206    #        plus a summary should go in this docstring 
     207    #        -- make this work when "right" is e.g. an Integer -- perhaps 
     208    #        the mod operator needs to be brought under the SAGE arithmetic 
     209    #        architecture umbrella 
     210    #         
     211    #    """ 
     212    #    val = self.valuation() 
     213    #    rval = right.valuation() 
     214    #    quotient =  self / right._unit_part() 
     215    #    return pAdicRingFixedModElement(self.parent(), 
     216    #                 Mod(quotient.lift() % self.parent().prime_pow(rval), 
     217    #                 self.parent().prime_pow(self.parent().precision_cap())), 
     218    #                 construct = True) 
     219 
     220    def __lshift__(self, shift): 
     221        shift = Integer(shift) 
     222        if shift < 0: 
     223            return self.__rshift__(-shift) 
     224        return pAdicRingFixedModElement(self.parent(), self._value * self.parent().prime_pow(shift), construct = True) 
     225 
     226    def __rshift__(self, shift): 
     227        shift = Integer(shift) 
     228        if shift < 0: 
     229            return self.__lshift__(-shift) 
     230        return pAdicRingFixedModElement(self.parent(), Mod(self._value.lift() // self.parent().prime_pow(shift), self.parent().prime_pow(self.parent().precision_cap())), construct = True) 
     231 
    219232 
    220233    def _neg_(self): 
    … …  
    274287                            self._value / right._value, construct = True) 
    275288 
    276     def __floordiv__(self, right): 
    277         if isinstance(right, Integer): 
    278             right = pAdicRingFixedModElement(self.parent(), right) 
    279         ppow = self.parent().prime_pow(right.valuation()) 
    280         runit = right._unit_part() 
    281         quotient = Mod((self._value / runit).lift() // ppow, self.parent().prime_pow(self.parent().precision_cap())) 
    282         return pAdicRingFixedModElement(self.parent(), quotient, construct = True) 
    283  
    284     def _integer_(self): 
    285         r""" 
    286         Return an integer congruent to self modulo self's precision. 
    287          
    288         See the lift() method. 
    289         """ 
    290         return self._value.lift() 
     289    #def __floordiv__(self, right): 
     290    #    if isinstance(right, Integer): 
     291    #        right = pAdicRingFixedModElement(self.parent(), right) 
     292    #    ppow = self.parent().prime_pow(right.valuation()) 
     293    #    runit = right._unit_part() 
     294    #    quotient = Mod((self._value / runit).lift() // ppow, self.parent().prime_pow(self.parent().precision_cap())) 
     295    #    return pAdicRingFixedModElement(self.parent(), quotient, construct = True) 
     296 
     297    #def _integer_(self): 
     298    #    r""" 
     299    #    Return an integer congruent to self modulo self's precision. 
     300    #     
     301    #    See the lift() method. 
     302    #    """ 
     303    #    return self._value.lift() 
    291304 
    292305    def _mul_(self, right): 

  • sage/rings/padics/padic_ring_generic_element.py

    r3312 r3408  
    6262 
    6363    def __floordiv__(self, right): 
    64         raise NotImplementedError 
     64        if isinstance(right, Integer): 
     65            right = pAdicRingCappedRelativeElement(self.parent(), right) 
     66        return (self / right.unit_part()).__rshift__(right.valuation()) 
     67 
     68    def __mod__(self, right): 
     69        return self - right * self.__floordiv__(right) 
    6570 
    6671    def _integer_(self): 
    67         raise NotImplementedError 
     72        return self.lift() 
    6873 
    6974 

  • sage/rings/rational.pxd

    r2664 r3408  
    99 
    1010    cdef void set_from_mpq(Rational self, mpq_t value) 
    11     cdef _lshift(self, unsigned long int exp) 
    12     cdef _rshift(self, unsigned long int exp)     
     11    cdef _lshift(self, long int exp) 
     12    cdef _rshift(self, long int exp)     
    1313 
    1414    cdef integer.Integer _integer_c(self) 

  • sage/rings/rational.pyx

    r3354 r3408  
    10371037        return mpz_cmp_si(mpq_numref(self.value), 0) == 0 
    10381038     
    1039     cdef _lshift(self, unsigned long int exp): 
     1039    cdef _lshift(self, long int exp): 
    10401040        r""" 
    1041         Return $self/2^exp$ 
     1041        Return $self*2^exp$ 
    10421042        """ 
    10431043        cdef Rational x 
    10441044        x = <Rational> PY_NEW(Rational) 
    10451045        _sig_on 
    1046         mpq_mul_2exp(x.value,self.value,exp)        
     1046        if exp < 0: 
     1047            mpq_div_2exp(x.value,self.value,-exp) 
     1048        else: 
     1049            mpq_mul_2exp(x.value,self.value,exp)        
    10471050        _sig_off 
    10481051        return x 
    10491052 
    10501053    def __lshift__(x,y): 
    1051         if isinstance(x, Rational) and isinstance(y, Rational): 
    1052             return x._lshift(y)  
     1054        if isinstance(x, Rational) and isinstance(y, (int, long, integer.Integer)): 
     1055            return (<Rational>x)._lshift(y)  
    10531056        return bin_op(x, y, operator.lshift) 
    10541057     
    1055     cdef _rshift(self, unsigned long int exp): 
     1058    cdef _rshift(self, long int exp): 
    10561059        r""" 
    10571060        Return $self/2^exp$ 
    … …  
    10601063        x = <Rational> PY_NEW(Rational) 
    10611064        _sig_on 
    1062         mpq_div_2exp(x.value,self.value,exp) 
     1065        if exp < 0: 
     1066            mpq_mul_2exp(x.value,self.value,-exp) 
     1067        else: 
     1068            mpq_div_2exp(x.value,self.value,exp) 
    10631069        _sig_off 
    10641070        return x 
    10651071 
    10661072    def __rshift__(x,y): 
    1067         if isinstance(x, Rational) and isinstance(y, Rational): 
    1068             return x._rshift(y)  
     1073        if isinstance(x, Rational) and isinstance(y, (int, long, integer.Integer)): 
     1074            return (<Rational>x)._rshift(y)  
    10691075        return bin_op(x, y, operator.rshift) 
    10701076     
Note: See TracChangeset for help on using the changeset viewer.