Coverage for local/lib/python2.7/site-packages/sage/rings/polynomial/padics/polynomial_padic_capped_relative_dense.py : 67%
Hot-keys on this page
r m x p toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
|
""" p-adic Capped Relative Dense Polynomials """
#***************************************************************************** # Distributed under the terms of the GNU General Public License (GPL) # as published by the Free Software Foundation; either version 2 of # the License, or (at your option) any later version. # http://www.gnu.org/licenses/ #*****************************************************************************
""" TESTS::
sage: K = Qp(13,7) sage: R.<t> = K[] sage: R([K(13), K(1)]) (1 + O(13^7))*t + (13 + O(13^8)) sage: T.<t> = ZZ[] sage: R(t + 2) (1 + O(13^7))*t + (2 + O(13^7))
Check that :trac:`13620` has been fixed::
sage: f = R.zero() sage: R(f.dict()) 0
"""
#First we list the types that are turned into Polynomials x = Polynomial_integer_dense(PolynomialRing(ZZ, parent.variable_name()), x, construct = True) x.denominator() == 1: #Currently we ignore precision information in the denominator. This should be changed eventually x = x.numerator()
#We now coerce various types into lists of coefficients. There are fast pathways for some types of polynomials if not absprec is infinity or not relprec is infinity: x._normalize() self._poly = x._poly self._valbase = x._valbase self._valaddeds = x._valaddeds self._relprecs = x._relprecs self._normalized = x._normalized self._list = x._list if not absprec is infinity or not relprec is infinity: self._adjust_prec_info(absprec, relprec) return self._poly = x self._valbase = Integer(0) p = parentbr.prime() self._relprecs = [c.valuation(p) + parentbr.precision_cap() for c in x.list()] self._comp_valaddeds() self._normalized = len(self._valaddeds) == 0 or (min(self._valaddeds) == 0) self._list = None if not absprec is infinity or not relprec is infinity: self._adjust_prec_info(absprec, relprec) return else: # The default behavior, if we haven't already figured out what # the type is, is to assume it coerces into the base_ring as a # constant polynomial
# In contrast to other polynomials, the zero element is not distinguished # by having its list empty. Instead, it has list [0]
# Remove this -- for p-adics this is terrible, since it kills any non exact zero. #if len(x) == 1 and not x[0]: # x = []
self._adjust_prec_info(absprec, relprec) else:
""" Create a new constant polynomial in parent P with value a.
ASSUMPTION:
The value a must be an element of the base ring of P. That assumption is not verified.
EXAMPLES::
sage: R.<t> = Zp(5)[] sage: t._new_constant_poly(O(5),R) (O(5)) """
# Currently slow: need to optimize else:
""" For pickling. This function is here because the relative precisions were getting screwed up for some reason. """
""" Recomputes the list of coefficients.
EXAMPLES::
sage: K = Qp(13,7) sage: R.<t> = K[] sage: a = t[:1] sage: a._comp_list() sage: a 0 """ + [self.base_ring()(0, absprec = self._relprecs[i] + self._valbase) for i in range(polylen, len(self._relprecs))] self._list.pop()
else:
r""" Assumes that self._poly, self._val and self._relprec are set initially and adjusts self._val and self._relprec to the termwise minimum of absprec and relprec. """
# min = sage.rings.padics.misc.min # slen = len(self._relprec) # if isinstance(absprec, list): # alen = len(absprec) # elif absprec is infinity: # alen = 0 # absprec = [] # else: # alen = 1 # if isinstance(relprec, list): # rlen = len(relprec) # elif relprec is infinity: # rlen = 0 # relprec = [] # else: # rlen = 1 # preclen = max(slen, rlen, alen) # if not isinstance(absprec, list): # absprec = [absprec] * preclen # if not isinstance(relprec, list): # relprec = [relprec] * preclen # vallist = [c.valuation(self.base_ring().prime()) + self._val for c in self._poly.list()] ####### # vmin = min(vallist) # amin = min(absprec) # if amin < vmin: # vmin = amin # if vmin < self._val: # vadjust =
# if not isinstance(absprec, list): # self._val = min(vallist + [absprec]) # absprec = [absprec] * preclen # else: # self._val = padics.misc.min(vallist + absprec) # absprec = absprec + [infinity] * (preclen - len(absprec)) # if self._val is infinity: # self._relprec = [] # return # if not isinstance(relprec, list): # relprec = [relprec] * preclen # else: # relprec = relprec + [parent.base_ring().precision_cap()] * (preclen - len(relprec)) # self._relprec = [min(a, v + r) - self._val for (a, r, v) in zip(absprec, relprec, vallist)] #Remember to normalize at the end if self._normalized is true because you need to reduce mod p^n
self._comp_valaddeds() [(0 if (c is infinity) else (one << (n * c))) for c in self._relprecs[len(self._valaddeds):]])
""" Return a list of coefficients of ``self``.
.. NOTE::
The length of the list returned may be greater than expected since it includes any leading zeros that have finite absolute precision.
EXAMPLES::
sage: K = Qp(13,7) sage: R.<t> = K[] sage: a = 2*t^3 + 169*t - 1 sage: a (2 + O(13^7))*t^3 + (13^2 + O(13^9))*t + (12 + 12*13 + 12*13^2 + 12*13^3 + 12*13^4 + 12*13^5 + 12*13^6 + O(13^7)) sage: a.list() [12 + 12*13 + 12*13^2 + 12*13^3 + 12*13^4 + 12*13^5 + 12*13^6 + O(13^7), 13^2 + O(13^9), 0, 2 + O(13^7)] """ else:
""" Return an integer polynomial congruent to this one modulo the precision of each coefficient.
.. NOTE::
The lift that is returned will not necessarily be the same for polynomials with the same coefficients (i.e. same values and precisions): it will depend on how the polynomials are created.
EXAMPLES::
sage: K = Qp(13,7) sage: R.<t> = K[] sage: a = 13^7*t^3 + K(169,4)*t - 13^4 sage: a.lift() 62748517*t^3 + 169*t - 28561 """
""" Returns the coefficient of x^n if `n` is an integer, returns the monomials of self of degree in slice `n` if `n` is a slice.
Return the `n`-th coefficient of ``self``.
EXAMPLES::
sage: K = Qp(13,7) sage: R.<t> = K[] sage: a = 13^7*t^3 + K(169,4)*t - 13^4 sage: a[1] 13^2 + O(13^4)
Slices can be used to truncate polynomials::
sage: a[:2] (13^2 + O(13^4))*t + (12*13^4 + 12*13^5 + 12*13^6 + 12*13^7 + 12*13^8 + 12*13^9 + 12*13^10 + O(13^11))
Any other kind of slicing is deprecated or an error, see :trac:`18940`::
sage: a[1:3] doctest:...: DeprecationWarning: polynomial slicing with a start index is deprecated, use list() and slice the resulting list instead See http://trac.sagemath.org/18940 for details. (13^2 + O(13^4))*t sage: a[1:3:2] Traceback (most recent call last): ... NotImplementedError: polynomial slicing with a step is not defined """ else: start = 0 + [self[i] for i in range(start, stop)])
except AttributeError: raise TypeError("list indices must be integers, not {0}".format(type(n).__name__))
* self._poly[n], absprec = self._valbase + self._relprecs[n])
""" Return the sum of ``self`` and ``right``.
EXAMPLES::
sage: K = Qp(13,7) sage: R.<t> = K[] sage: a = t^4 + 17*t^2 + 1 sage: b = -t^4 + 9*t^2 + 13*t - 1 sage: c = a + b; c (O(13^7))*t^4 + (2*13 + O(13^7))*t^2 + (13 + O(13^8))*t + (O(13^7)) sage: c.list() [O(13^7), 13 + O(13^8), 2*13 + O(13^7), 0, O(13^7)] """ else: # Currently we don't reduce the coefficients of the answer modulo the appropriate power of p or normalize (selfpoly + rightpoly, \ baseval, \ [min(a + self._valbase - baseval, b + right._valbase - baseval) for (a, b) in zip(_extend_by_infinity(self._relprecs, max(len(self._relprecs), len(right._relprecs))), \ _extend_by_infinity(right._relprecs, max(len(self._relprecs), len(right._relprecs))))], \ False, None, None), construct = True)
""" Return the difference of ``self`` and ``right``.
EXAMPLES::
sage: K = Qp(13,7) sage: R.<t> = K[] sage: a = t^4 + 17*t^2 + 1 sage: b = t^4 - 9*t^2 - 13*t + 1 sage: c = a - b; c (O(13^7))*t^4 + (2*13 + O(13^7))*t^2 + (13 + O(13^8))*t + (O(13^7)) sage: c.list() [O(13^7), 13 + O(13^8), 2*13 + O(13^7), 0, O(13^7)] """ else: # Currently we don't reduce the coefficients of the answer modulo the appropriate power of p or normalize (selfpoly - rightpoly, \ baseval, \ [min(a + self._valbase - baseval, b + right._valbase - baseval) for (a, b) in zip(_extend_by_infinity(self._relprecs, max(len(self._relprecs), len(right._relprecs))), \ _extend_by_infinity(right._relprecs, max(len(self._relprecs), len(right._relprecs))))], \ False, None, None), construct = True)
r""" Multiplies ``self`` and ``right``.
ALGORITHM: We use an algorithm thought up by Joe Wetherell to find the precisions of the product. It works as follows: Suppose $f = \sum_i a_i x^i$ and $g = \sum_j b_j x^j$. Let $N = \max(\deg f, \deg g) + 1$ (in the actual implementation we use $N = 2^{\lfloor \log_2\max(\deg f, \deg g)\rfloor + 1}$). The valuations and absolute precisions of each coefficient contribute to the absolute precision of the kth coefficient of the product in the following way: for each $i + j = k$, you take the valuation of $a_i$ plus the absolute precision of $b_j$, and then take the valuation of $b_j$ plus the absolute precision of $a_i$, take the minimum of those two, and then take the minimum over all $i$, $j$ summing to $k$.
You can simulate this as follows. Construct new polynomials of degree $N$:
\begin{align*} A &= \sum_i N^{\mbox{valuation of $a_i$}} x^i \\ B &= \sum_j N^{\mbox{absolute precision of $b_j$}} x^j \\ C &= \sum_i N^{\mbox{absolute precision of $a_i$}} x^i \\ D &= \sum_j N^{\mbox{valuation of $b_j$}} x^j \\ \end{align*}
Now you compute AB and CD. Because you're representing things 'N-adically', you don't get any 'overflow', and you can just read off what the precisions of the product are. In fact it tells you more, it tells you exactly how many terms of each combination of valuation modulus contribute to each term of the product (though this feature is not currently exposed in our implementation.
Since we're working 'N-adically' we can just consider $N^{\infty} = 0$.
NOTE: The timing of normalization in arithmetic operations may very well change as we do more tests on the relative time requirements of these operations.
EXAMPLES::
sage: K = Qp(13,7) sage: R.<t> = K[] sage: a = t^4 + 17*t^2 + 1 sage: b = -t^4 + 9*t^2 + 13*t - 1 sage: c = a + b; c (O(13^7))*t^4 + (2*13 + O(13^7))*t^2 + (13 + O(13^8))*t + (O(13^7)) sage: d = R([K(1,4), K(2, 6), K(1, 5)]); d (1 + O(13^5))*t^2 + (2 + O(13^6))*t + (1 + O(13^4)) sage: e = c * d; e (O(13^7))*t^6 + (O(13^7))*t^5 + (2*13 + O(13^6))*t^4 + (5*13 + O(13^6))*t^3 + (4*13 + O(13^5))*t^2 + (13 + O(13^5))*t + (O(13^7)) sage: e.list() [O(13^7), 13 + O(13^5), 4*13 + O(13^5), 5*13 + O(13^6), 2*13 + O(13^6), O(13^7), O(13^7)] """ # These two will be the same length
""" Return ``self`` multiplied by a constant.
EXAMPLES::
sage: K = Qp(13,7) sage: R.<t> = K[] sage: a = t^4 + K(13,5)*t^2 + 13 sage: K(13,7) * a (13 + O(13^7))*t^4 + (13^2 + O(13^6))*t^2 + (13^2 + O(13^8)) """ # The code below has never been tested and is somehow subtly broken.
if self._valaddeds is None: self._comp_valaddeds() if left != 0: val, unit = left.val_unit() left_rprec = left.precision_relative() relprecs = [min(left_rprec + self._valaddeds[i], self._relprecs[i]) for i in range(len(self._relprecs))] elif left._is_exact_zero(): return Polynomial_padic_capped_relative_dense(self.parent(), []) else: return Polynomial_padic_capped_relative_dense(self.parent(), (self._poly.parent()(0), self._valbase + left.valuation(), self._valaddeds, False, self._valaddeds, None), construct = True) return Polynomial_padic_capped_relative_dense(self.parent(), (self._poly._rmul_(unit), self._valbase + val, relprecs, False, self._valaddeds, None), construct = True)
""" Return the negation of ``self``.
EXAMPLES::
sage: K = Qp(13,2) sage: R.<t> = K[] sage: a = t^4 + 13*t^2 + 4 sage: -a (12 + 12*13 + O(13^2))*t^4 + (12*13 + 12*13^2 + O(13^3))*t^2 + (9 + 12*13 + O(13^2)) """
""" Return a new polynomials whose coefficients are multiplied by p^shift.
EXAMPLES::
sage: K = Qp(13, 4) sage: R.<t> = K[] sage: a = t + 52 sage: a.lshift_coeffs(3) (13^3 + O(13^7))*t + (4*13^4 + O(13^8)) """ return self.rshift_coeffs(-shift, no_list) else: return Polynomial_padic_capped_relative_dense(self.parent(), (self._poly, self._valbase + shift, self._relprecs, False, self._valaddeds, [c.__lshift__(shift) for c in self._list]), construct = True)
""" Return a new polynomial whose coefficients are p-adically shifted to the right by shift.
NOTES: Type Qp(5)(0).__rshift__? for more information.
EXAMPLES::
sage: K = Zp(13, 4) sage: R.<t> = K[] sage: a = t^2 + K(13,3)*t + 169; a (1 + O(13^4))*t^2 + (13 + O(13^3))*t + (13^2 + O(13^6)) sage: b = a.rshift_coeffs(1); b (O(13^3))*t^2 + (1 + O(13^2))*t + (13 + O(13^5)) sage: b.list() [13 + O(13^5), 1 + O(13^2), O(13^3)] sage: b = a.rshift_coeffs(2); b (O(13^2))*t^2 + (O(13))*t + (1 + O(13^4)) sage: b.list() [1 + O(13^4), O(13), O(13^2)] """ return self.lshift_coeffs(-shift, no_list) # We can't just absorb this into the next if statement because we allow rshift to preserve _normalized if no_list or self._list is None: return Polynomial_padic_capped_relative_dense(self.parent(), (self._poly, self._valbase - shift, self._relprecs, self._normalized, self._valaddeds, None), construct = True) else: return Polynomial_padic_capped_relative_dense(self.parent(), (self._poly, self._valbase - shift, self._relprecs, self._normalized, self._valaddeds, [c.__rshift__(shift) for c in self._list]), construct = True) else:
#def __floordiv__(self, right): # if is_Polynomial(right) and right.is_constant() and right[0] in self.base_ring(): # d = self.base_ring()(right[0]) # elif (right in self.base_ring()): # d = self.base_ring()(right) # else: # raise NotImplementedError # return self._rmul_(self.base_ring()(~d.unit_part())).rshift_coeffs(d.valuation())
""" It's a really bad idea to use this function for p-adic polynomials. There are speed issues, and it may not be bug-free currently. """ n = int(n) value = self.base_ring()(value) if self.is_gen(): raise ValueError("cannot modify generator") if n < 0: raise IndexError("n must be >= 0") if self._valbase is infinity: if value._is_exact_zero(): return self._valbase = value.valuation() if value != 0: self._poly._unsafe_mutate(self, n, value.unit_part().lift()) self._relprecs = [infinity] * n + [value.precision_relative()] else: self._relprecs = [infinity] * n + [0] self._valaddeds = [infinity] * n + [0] zero = self.base_ring()(0) self._list = [zero] * n + [value] self._normalized = True elif value.valuation() >= self._valbase: # _valbase and _normalized stay the same if value != 0: self._poly._unsafe_mutate(self, n, (value.__rshift__(self._valbase)).lift()) else: self._poly._unsafe_mutate(self, n, 0) if n < len(self._relprecs): self._relprecs[n] = value.precision_absolute() - self._valbase if not self._valaddeds is None: self._valaddeds[n] = value.valuation() - self._valbase if not self._list is None: self._list[n] = value else: self._relprecs.extend([infinity] * (n - len(self._relprecs)) + [value.precision_absolute() - self._valbase]) if not self._valaddeds is None: self._valaddeds.extend([infinity] * (n - len(self._relprecs)) + [value.valuation() - self._valbase]) if not self._list is None: zero = self.base_ring()(0) self._list.extend([zero] * (n - len(self._relprecs)) + [value]) else: basediff = self._valbase - value.valuation() self._valbase = value.valuation() if not self._valaddeds is None: self._valaddeds = [c + basediff for c in self._valaddeds] self._poly = self._poly * self.base_ring().prime_pow(basediff) if value != 0: self._poly._unsafe_mutate(self, n, value.unit_part().lift()) else: self._poly._unsafe_mutate(self, n, 0) if n < len(self._relprecs): self._relprecs[n] = value.precision_relative() else: self._relprecs.extend([infinity] * (n - len(self._relprecs)) + [value.precision_relative()]) self._normalized = False if not self._list is None: if n < len(self._list): self._list[n] = value else: zero = self._base_ring()(0) self._list.extend([zero] * (n - len(self._list)) + [value])
""" Return ``self`` as a Pari object. """
""" Return a copy of ``self``. """ return Polynomial_padic_capped_relative_dense(self.parent(), (copy.copy(self._poly), self._valbase, copy.copy(self._relprecs), self._normalized, copy.copy(self._valaddeds), copy.copy(self._list)), construct = True)
""" Return the degree of ``self``.
INPUT:
- secure -- a boolean (default: ``False``)
If ``secure`` is ``True`` and the degree of this polynomial is not determined (because the leading coefficient is indistinguishable from 0), an error is raised.
If ``secure`` is ``False``, the returned value is the largest $n$ so that the coefficient of $x^n$ does not compare equal to $0$.
EXAMPLES::
sage: K = Qp(3,10) sage: R.<T> = K[] sage: f = T + 2; f (1 + O(3^10))*T + (2 + O(3^10)) sage: f.degree() 1 sage: (f-T).degree() 0 sage: (f-T).degree(secure=True) Traceback (most recent call last): ... PrecisionError: the leading coefficient is indistinguishable from 0
sage: x = O(3^5) sage: li = [3^i * x for i in range(0,5)]; li [O(3^5), O(3^6), O(3^7), O(3^8), O(3^9)] sage: f = R(li); f (O(3^9))*T^4 + (O(3^8))*T^3 + (O(3^7))*T^2 + (O(3^6))*T + (O(3^5)) sage: f.degree() -1 sage: f.degree(secure=True) Traceback (most recent call last): ... PrecisionError: the leading coefficient is indistinguishable from 0 """ "indistinguishable from 0")
""" Return the largest $n$ so that precision information is stored about the coefficient of $x^n$.
Always greater than or equal to degree.
EXAMPLES::
sage: K = Qp(3,10) sage: R.<T> = K[] sage: f = T + 2; f (1 + O(3^10))*T + (2 + O(3^10)) sage: f.prec_degree() 1 """
""" Return absolute precision information about ``self``.
INPUT:
``self`` -- a p-adic polynomial
n -- ``None`` or an integer (default ``None``).
OUTPUT:
If n == None, returns a list of absolute precisions of coefficients. Otherwise, returns the absolute precision of the coefficient of x^n.
EXAMPLES::
sage: K = Qp(3,10) sage: R.<T> = K[] sage: f = T + 2; f (1 + O(3^10))*T + (2 + O(3^10)) sage: f.precision_absolute() [10, 10] """ return self._relprecs[n] + self._valbase
""" Return relative precision information about ``self``.
INPUT:
``self`` -- a p-adic polynomial
n -- ``None`` or an integer (default ``None``).
OUTPUT:
If n == None, returns a list of relative precisions of coefficients. Otherwise, returns the relative precision of the coefficient of x^n.
EXAMPLES::
sage: K = Qp(3,10) sage: R.<T> = K[] sage: f = T + 2; f (1 + O(3^10))*T + (2 + O(3^10)) sage: f.precision_relative() [10, 10] """ n = int(n) if n < 0 or n >= len(self._relprecs) or self._relprecs[n] is infinity: return Integer(0) if self._valaddeds is None: return self._relprecs[n] - self._poly[n].valuation(self.base_ring().prime()) else: return self._relprecs[n] - self._valaddeds[n]
""" Return valuation information about ``self``'s coefficients.
INPUT:
``self`` -- a p-adic polynomial
n -- ``None`` or an integer (default ``None``).
OUTPUT:
If n == None, returns a list of valuations of coefficients. Otherwise, returns the valuation of the coefficient of x^n.
EXAMPLES::
sage: K = Qp(3,10) sage: R.<T> = K[] sage: f = T + 2; f (1 + O(3^10))*T + (2 + O(3^10)) sage: f.valuation_of_coefficient(1) 0 """ self._comp_valaddeds() self._normalize() return [ c + self._valbase for c in self._valaddeds ] return infinity
""" Return the valuation of ``self``.
INPUT:
``self`` -- a p-adic polynomial
val_of_var -- ``None`` or a rational (default ``None``).
OUTPUT:
If val_of_var == None, returns the largest power of the variable dividing self. Otherwise, returns the valuation of ``self`` where the variable is assigned valuation val_of_var
EXAMPLES::
sage: K = Qp(3,10) sage: R.<T> = K[] sage: f = T + 2; f (1 + O(3^10))*T + (2 + O(3^10)) sage: f.valuation() 0 """ self._comp_valaddeds()
""" Return a new polynomial whose coefficients are the reversed coefficients of ``self``, where ``self`` is considered as a polynomial of degree n.
If n is ``None``, defaults to the degree of ``self``.
If n is smaller than the degree of ``self``, some coefficients will be discarded.
EXAMPLES::
sage: K = Qp(13,7) sage: R.<t> = K[] sage: f = t^3 + 4*t; f (1 + O(13^7))*t^3 + (4 + O(13^7))*t sage: f.reverse() (4 + O(13^7))*t^2 + (1 + O(13^7)) sage: f.reverse(3) (4 + O(13^7))*t^2 + (1 + O(13^7)) sage: f.reverse(2) (4 + O(13^7))*t sage: f.reverse(4) (4 + O(13^7))*t^3 + (1 + O(13^7))*t sage: f.reverse(6) (4 + O(13^7))*t^5 + (1 + O(13^7))*t^3 """ valadded = None else: L = None else:
r""" Return f(a*X)
.. TODO::
Need to write this function for integer polynomials before this works.
EXAMPLES::
sage: K = Zp(13, 5) sage: R.<t> = K[] sage: f = t^3 + K(13, 3) * t sage: f.rescale(2) # not implemented """ negval = False try: a = self.base_ring()(a) except ValueError as msg: if msg == "element has negative valuation.": negval = True else: raise ValueError(msg) if negval: return self.parent().base_extend(self.base_ring().fraction_field())(self).rescale(a) if self.base_ring().is_field() and a.valuation() < 0: D = self.prec_degree() return a**D * self.reverse(D).rescale(~a).reverse(D) aval = a.valuation() arprec = a.precision_relative() if self._valaddeds is None: self._comp_valaddeds() valadded = [self._valaddeds[i] + aval * i for i in range(len(self._valaddeds))] relprec = [infinity if (self._relprecs[i] is infinity) else (min(self._relprecs[i] - self._valaddeds[i], arprec) + aval * i + self._valaddeds[i]) for i in range(len(self._relprecs))] relprec[0] = self._relprecs[0] if a == 0: zzpoly = self._poly.parent()(0) else: zzpoly = self._poly.rescale(Integer(a)) return Polynomial_padic_capped_relative_dense(self.parent(), (zzpoly, self._valbase, relprec, False, valadded, None), construct = True)
""" Return the quotient and remainder in division of ``self`` by ``right``.
EXAMPLES::
sage: K = Qp(3,10) sage: R.<T> = K[] sage: f = T + 2 sage: g = T**4 + 3*T+22 sage: g.quo_rem(f) ((1 + O(3^10))*T^3 + (1 + 2*3 + 2*3^2 + 2*3^3 + 2*3^4 + 2*3^5 + 2*3^6 + 2*3^7 + 2*3^8 + 2*3^9 + O(3^10))*T^2 + (1 + 3 + O(3^10))*T + (1 + 3 + 2*3^2 + 2*3^3 + 2*3^4 + 2*3^5 + 2*3^6 + 2*3^7 + 2*3^8 + 2*3^9 + O(3^10)), (2 + 3 + 3^3 + O(3^10)))
TESTS:
Verify that :trac:`15188` has been resolved::
sage: R.<x> = Qp(3)[] sage: x.quo_rem(x) ((1 + O(3^20)), 0)
"""
""" An implementation of quo_rem that doesn't have good run-time or precision characteristics.
A better one is :meth:`_quo_rem_list`. """ K = self.base_ring().fraction_field() f = self.base_extend(K) g = right.base_extend(K) if g == 0: raise ZeroDivisionError("cannot divide by a polynomial " "indistinguishable from 0") x = f.parent().gen() quo = f.parent()(0) while f.degree() >= g.degree(): a = f.leading_coefficient() / g.leading_coefficient() quo = quo + a * (x ** (f.degree() - g.degree())) f = f - a * (x ** (f.degree() - g.degree())) * g return (quo, f)
""" An implementation of quo_rem using lists of coefficients.
Faster than :meth:`_quo_rem_naive`.
AUTHOR:
- Xavier Caruso (2013-03) """ raise ZeroDivisionError("cannot divide by a polynomial " "indistinguishable from 0")
#def gcd(self, right): # raise NotImplementedError
#def lcm(self, right): # raise NotImplementedError
def xgcd(self, right): """ Extended gcd of ``self`` and ``other``.
INPUT:
- ``other`` -- an element with the same parent as ``self``
OUTPUT:
Polynomials ``g``, ``u``, and ``v`` such that ``g = u*self + v*other``
.. WARNING::
The computations are performed using the standard Euclidean algorithm which might produce mathematically incorrect results in some cases. See :trac:`13439`.
EXAMPLES::
sage: R.<x> = Qp(3,3)[] sage: f = x + 1 sage: f.xgcd(f^2) ((1 + O(3^3))*x + (1 + O(3^3)), (1 + O(3^3)), 0)
In these examples the results are incorrect, see :trac:`13439`::
sage: R.<x> = Qp(3,3)[] sage: f = 3*x + 7 sage: g = 5*x + 9 sage: f.xgcd(f*g) # known bug ((3 + O(3^4))*x + (1 + 2*3 + O(3^3)), (1 + O(3^3)), 0)
sage: R.<x> = Qp(3)[] sage: f = 490473657*x + 257392844/729 sage: g = 225227399/59049*x - 8669753175 sage: f.xgcd(f*g) # known bug ((3^3 + 3^5 + 2*3^6 + 2*3^7 + 3^8 + 2*3^10 + 2*3^11 + 3^12 + 3^13 + 3^15 + 2*3^16 + 3^18 + O(3^23))*x + (2*3^-6 + 2*3^-5 + 3^-3 + 2*3^-2 + 3^-1 + 2*3 + 2*3^2 + 2*3^3 + 2*3^4 + 3^6 + 2*3^7 + 2*3^8 + 2*3^9 + 2*3^10 + 3^11 + O(3^14)), (1 + O(3^20)), 0)
"""
#def discriminant(self): # raise NotImplementedError
return self.discriminant()
#def resultant(self): # raise NotImplementedError
r""" Return the Newton polygon of this polynomial.
.. NOTE::
If some coefficients have not enough precision an error is raised.
OUTPUT:
- a Newton polygon
EXAMPLES::
sage: K = Qp(2, prec=5) sage: P.<x> = K[] sage: f = x^4 + 2^3*x^3 + 2^13*x^2 + 2^21*x + 2^37 sage: f.newton_polygon() Finite Newton polygon with 4 vertices: (0, 37), (1, 21), (3, 3), (4, 0)
sage: K = Qp(5) sage: R.<t> = K[] sage: f = 5 + 3*t + t^4 + 25*t^10 sage: f.newton_polygon() Finite Newton polygon with 4 vertices: (0, 1), (1, 0), (4, 0), (10, 2)
Here is an example where the computation fails because precision is not sufficient::
sage: g = f + K(0,0)*t^4; g (5^2 + O(5^22))*t^10 + (O(5^0))*t^4 + (3 + O(5^20))*t + (5 + O(5^21)) sage: g.newton_polygon() Traceback (most recent call last): ... PrecisionError: The coefficient of t^4 has not enough precision
TESTS::
sage: (5*f).newton_polygon() Finite Newton polygon with 4 vertices: (0, 2), (1, 1), (4, 1), (10, 3)
AUTHOR:
- Xavier Caruso (2013-03-20) """ for x, val in enumerate(self._valaddeds)]) for x, val in enumerate(self._relprecs)])
# The two following tests should always fail (i.e. the corresponding errors # should never be raised). However, it's probably safer to keep them. raise PrecisionError("The constant coefficient has not enough precision") raise PrecisionError("The leading coefficient has not enough precision")
""" Return ``True`` if this polynomial is an Eisenstein polynomial.
EXAMPLES::
sage: K = Qp(5) sage: R.<t> = K[] sage: f = 5 + 5*t + t^4 sage: f.is_eisenstein() True
TESTS::
sage: f = R([K(5,1),0,0,1]); f (1 + O(5^20))*t^3 + (O(5)) sage: f.is_eisenstein() Traceback (most recent call last): ... PrecisionError: Not enough precision on the constant coefficient
sage: g = R([5,K(0,0),0,1]); g (1 + O(5^20))*t^3 + (O(5^0))*t + (5 + O(5^21)) sage: g.is_eisenstein() True sage: g.is_eisenstein(secure=True) Traceback (most recent call last): ... PrecisionError: Not enough precision on the coefficient of t
AUTHOR:
- Xavier Caruso (2013-03) """ raise PrecisionError("The degree of the polynomial is not determined") self._comp_valaddeds() else: else: raise PrecisionError("Not enough precision on the coefficient of %s^%s" % (self.variable_name(), i)) else: return False return False
""" Return a list of the Newton slopes of this polynomial.
These are the valuations of the roots of this polynomial.
If ``repetition`` is ``True``, each slope is repeated a number of times equal to its multiplicity. Otherwise it appears only one time.
INPUT:
- ``repetition`` -- boolean (default ``True``)
OUTPUT:
- a list of rationals
EXAMPLES::
sage: K = Qp(5) sage: R.<t> = K[] sage: f = 5 + 3*t + t^4 + 25*t^10 sage: f.newton_polygon() Finite Newton polygon with 4 vertices: (0, 1), (1, 0), (4, 0), (10, 2) sage: f.newton_slopes() [1, 0, 0, 0, -1/3, -1/3, -1/3, -1/3, -1/3, -1/3]
sage: f.newton_slopes(repetition=False) [1, 0, -1/3]
AUTHOR:
- Xavier Caruso (2013-03-20) """
r""" Return the factorization of ``self`` modulo `p`. """ self._normalize() if self._valbase < 0: raise ValueError("Polynomial does not have integral coefficients") elif self._valbase > 0: raise ValueError("Factorization of the zero polynomial not defined") elif min(self._relprecs) <= 0: raise PrecisionError("Polynomial is not known to high enough precision") return self._poly.factor_mod(self.base_ring().prime())
else: raise ValueError("unknown pickling version") |