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
""" Polynomial Template for C/C++ Library Interfaces """
#***************************************************************************** # Copyright (C) 2008 Martin Albrecht <M.R.Albrecht@rhul.ac.uk> # Copyright (C) 2008 Robert Bradshaw # # This program is free software: you can redistribute it and/or modify # it under the terms of the GNU General Public License 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/ #*****************************************************************************
from sage.rings.polynomial.polynomial_element cimport Polynomial from sage.structure.element cimport ModuleElement, Element, RingElement from sage.structure.element import coerce_binop, bin_op from sage.structure.richcmp cimport rich_to_bool from sage.rings.fraction_field_element import FractionFieldElement from sage.rings.integer cimport Integer from sage.libs.all import pari_gen
import operator
from sage.interfaces.all import singular as singular_default
def make_element(parent, args):
cdef inline Polynomial_template element_shift(self, int n): if n > 0: error_msg = "Cannot shift %s << %n."%(self, n) else: error_msg = "Cannot shift %s >> %n."%(self, n) raise TypeError(error_msg)
else:
cdef class Polynomial_template(Polynomial): r""" Template for interfacing to external C / C++ libraries for implementations of polynomials.
AUTHORS:
- Robert Bradshaw (2008-10): original idea for templating - Martin Albrecht (2008-10): initial implementation
This file implements a simple templating engine for linking univariate polynomials to their C/C++ library implementations. It requires a 'linkage' file which implements the ``celement_`` functions (see :mod:`sage.libs.ntl.ntl_GF2X_linkage` for an example). Both parts are then plugged together by inclusion of the linkage file when inheriting from this class. See :mod:`sage.rings.polynomial.polynomial_gf2x` for an example.
We illustrate the generic glueing using univariate polynomials over `\mathop{\mathrm{GF}}(2)`.
.. note::
Implementations using this template MUST implement coercion from base ring elements and :meth:`get_unsafe`. See :class:`~sage.rings.polynomial.polynomial_gf2x.Polynomial_GF2X` for an example. """ def __init__(self, parent, x=None, check=True, is_gen=False, construct=False): """ EXAMPLES::
sage: P.<x> = GF(2)[] sage: P(0) 0 sage: P(GF(2)(1)) 1 sage: P(3) 1 sage: P([1,0,1]) x^2 + 1 sage: P(list(map(GF(2),[1,0,1]))) x^2 + 1 """ cdef celement *gen cdef celement *monomial cdef Py_ssize_t deg
except NotImplementedError: raise TypeError("%s not understood."%x)
except NotImplementedError: raise TypeError("%s not understood."%x)
# r += parent(e)*power
x = x.numerator() self.__class__.__init__(self, parent, x, check=check, is_gen=is_gen, construct=construct) else:
def get_cparent(self): return <long> self._cparent
def __reduce__(self): """ EXAMPLES::
sage: P.<x> = GF(2)[] sage: loads(dumps(x)) == x True """
cpdef list list(self, bint copy=True): """ EXAMPLES::
sage: P.<x> = GF(2)[] sage: x.list() [0, 1] sage: list(x) [0, 1] """ cdef Py_ssize_t i
def __dealloc__(self): """ EXAMPLES::
sage: P.<x> = GF(2)[] sage: del x
TESTS:
The following has been a problem in a preliminary version of :trac:`12313`::
sage: K.<z> = GF(4) sage: P.<x> = K[] sage: del P sage: del x sage: import gc sage: _ = gc.collect() """
cpdef _add_(self, right): """ EXAMPLES::
sage: P.<x> = GF(2)[] sage: x + 1 x + 1 """
#assert(r._parent(pari(self) + pari(right)) == r)
cpdef _sub_(self, right): """ EXAMPLES::
sage: P.<x> = GF(2)[] sage: x - 1 x + 1 """ #assert(r._parent(pari(self) - pari(right)) == r)
def __neg__(self): """ EXAMPLES::
sage: P.<x> = GF(2)[] sage: -x x """ #assert(r._parent(-pari(self)) == r)
cpdef _lmul_(self, Element left): """ EXAMPLES::
sage: P.<x> = GF(2)[] sage: t = x^2 + x + 1 sage: 0*t 0 sage: 1*t x^2 + x + 1
sage: R.<y> = GF(5)[] sage: u = y^2 + y + 1 sage: 3*u 3*y^2 + 3*y + 3 sage: 5*u 0 sage: (2^81)*u 2*y^2 + 2*y + 2 sage: (-2^81)*u 3*y^2 + 3*y + 3
::
sage: P.<x> = GF(2)[] sage: t = x^2 + x + 1 sage: t*0 0 sage: t*1 x^2 + x + 1
sage: R.<y> = GF(5)[] sage: u = y^2 + y + 1 sage: u*3 3*y^2 + 3*y + 3 sage: u*5 0 """
cpdef _mul_(self, right): """ EXAMPLES::
sage: P.<x> = GF(2)[] sage: x*(x+1) x^2 + x """ #assert(r._parent(pari(self) * pari(right)) == r)
@coerce_binop def gcd(self, Polynomial_template other): """ Return the greatest common divisor of self and other.
EXAMPLES::
sage: P.<x> = GF(2)[] sage: f = x*(x+1) sage: f.gcd(x+1) x + 1 sage: f.gcd(x^2) x """
#assert(r._parent(pari(self).gcd(pari(other))) == r)
@coerce_binop def xgcd(self, Polynomial_template other): """ Computes extended gcd of self and other.
EXAMPLES::
sage: P.<x> = GF(7)[] sage: f = x*(x+1) sage: f.xgcd(x+1) (x + 1, 0, 1) sage: f.xgcd(x^2) (x, 1, 6) """ return other, self._parent(0), self._parent(1)
#rp, sp, tp = pari(self).xgcd(pari(other)) #assert(r._parent(rp) == r) #assert(s._parent(sp) == s) #assert(t._parent(tp) == t)
cpdef _floordiv_(self, right): """ EXAMPLES::
sage: P.<x> = GF(2)[] sage: x//(x + 1) 1 sage: (x + 1)//x 1 sage: F = GF(47) sage: R.<x> = F[] sage: x // 1 x sage: x // F(1) x sage: 1 // x 0 sage: parent(x // 1) Univariate Polynomial Ring in x over Finite Field of size 47 sage: parent(1 // x) Univariate Polynomial Ring in x over Finite Field of size 47 """
raise ZeroDivisionError #assert(r._parent(pari(self) // pari(right)) == r)
cpdef _mod_(self, other): """ EXAMPLES::
sage: P.<x> = GF(2)[] sage: (x^2 + 1) % x^2 1
TESTS::
We test that :trac:`10578` is fixed::
sage: P.<x> = GF(2)[] sage: x % 1r 0 """ cdef Polynomial_template _other = <Polynomial_template>other
if celement_is_zero(&_other.x, (<Polynomial_template>self)._cparent): raise ZeroDivisionError
cdef type T = type(self) cdef Polynomial_template r = <Polynomial_template>T.__new__(T) celement_construct(&r.x, (<Polynomial_template>self)._cparent) r._parent = (<Polynomial_template>self)._parent r._cparent = (<Polynomial_template>self)._cparent celement_mod(&r.x, &(<Polynomial_template>self).x, &_other.x, (<Polynomial_template>self)._cparent) #assert(r._parent(pari(self) % pari(other)) == r) return r
@coerce_binop def quo_rem(self, Polynomial_template right): """ EXAMPLES::
sage: P.<x> = GF(2)[] sage: f = x^2 + x + 1 sage: f.quo_rem(x + 1) (x, 1) """
def __long__(self): """ EXAMPLES::
sage: P.<x> = GF(2)[] sage: int(x) Traceback (most recent call last): ... ValueError: Cannot coerce polynomial with degree 1 to integer.
sage: int(P(1)) 1 """
def __nonzero__(self): """ EXAMPLES::
sage: P.<x> = GF(2)[] sage: bool(x), x.is_zero() (True, False) sage: bool(P(0)), P(0).is_zero() (False, True) """
cpdef _richcmp_(self, other, int op): """ EXAMPLES::
sage: P.<x> = GF(2)[] sage: x != 1 True sage: x < 1 False sage: x > 1 True """ cdef int c
def __hash__(self): """ EXAMPLES::
sage: P.<x> = GF(2)[] sage: {x:1} {x: 1} """ cdef long result_mon cdef long c_hash cdef long var_name_hash cdef int i # we delay the hashing until now to not waste it one a constant poly # I'm assuming (incorrectly) that hashes of zero indicate that the element is 0. # This assumption is not true, but I think it is true enough for the purposes and it # it allows us to write fast code that omits terms with 0 coefficients. This is # important if we want to maintain the '==' relationship with sparse polys. else: # Hash (self[i], generator, i) as a tuple according to the algorithm. return -2
def __pow__(self, ee, modulus): """ EXAMPLES::
sage: P.<x> = GF(2)[] sage: P.<x> = GF(2)[] sage: x^1000 x^1000 sage: (x+1)^2 x^2 + 1 sage: (x+1)^(-2) 1/(x^2 + 1) sage: f = x^9 + x^7 + x^6 + x^5 + x^4 + x^2 + x sage: h = x^10 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + 1 sage: (f^2) % h x^9 + x^8 + x^7 + x^5 + x^3 sage: pow(f, 2, h) x^9 + x^8 + x^7 + x^5 + x^3 """ raise NotImplementedError("%s^%s not defined."%(ee,self))
cdef long e raise TypeError("Only integral powers defined.") raise ArithmeticError("0^0 is undefined.")
else: modulus = parent._coerce_(modulus)
#assert(r._parent(pari(self)**ee) == r) else:
def __copy__(self): """ EXAMPLES::
sage: P.<x> = GF(2)[] sage: copy(x) is x False sage: copy(x) == x True """
def is_gen(self): """ EXAMPLES::
sage: P.<x> = GF(2)[] sage: x.is_gen() True sage: (x+1).is_gen() False """
def shift(self, int n): """ EXAMPLES::
sage: P.<x> = GF(2)[] sage: f = x^3 + x^2 + 1 sage: f.shift(1) x^4 + x^3 + x sage: f.shift(-1) x^2 + x """
def __lshift__(self, int n): """ EXAMPLES::
sage: P.<x> = GF(2)[] sage: f = x^3 + x^2 + 1 sage: f << 1 x^4 + x^3 + x sage: f << -1 x^2 + x """
def __rshift__(self, int n): """ EXAMPLES::
sage: P.<x> = GF(2)[] sage: x>>1 1 sage: (x^2 + x)>>1 x + 1 sage: (x^2 + x) >> -1 x^3 + x^2 """
cpdef bint is_zero(self): """ EXAMPLES::
sage: P.<x> = GF(2)[] sage: x.is_zero() False """
cpdef bint is_one(self): """ EXAMPLES::
sage: P.<x> = GF(2)[] sage: P(1).is_one() True """
def degree(self): """ EXAMPLES::
sage: P.<x> = GF(2)[] sage: x.degree() 1 sage: P(1).degree() 0 sage: P(0).degree() -1 """
cpdef Polynomial truncate(self, long n): r""" Returns this polynomial mod `x^n`.
EXAMPLES::
sage: R.<x> =GF(2)[] sage: f = sum(x^n for n in range(10)); f x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1 sage: f.truncate(6) x^5 + x^4 + x^3 + x^2 + x + 1
If the precision is higher than the degree of the polynomial then the polynomial itself is returned::
sage: f.truncate(10) is f True """
def _singular_(self, singular=singular_default, have_ring=False): r""" Return Singular representation of this polynomial
INPUT:
- ``singular`` -- Singular interpreter (default: default interpreter) - ``have_ring`` -- set to True if the ring was already set in Singular
EXAMPLES::
sage: P.<x> = PolynomialRing(GF(7)) sage: f = 3*x^2 + 2*x + 5 sage: singular(f) 3*x^2+2*x-2 """
def _derivative(self, var=None): r""" Returns the formal derivative of self with respect to var.
var must be either the generator of the polynomial ring to which this polynomial belongs, or None (either way the behaviour is the same).
.. SEEALSO:: :meth:`.derivative`
EXAMPLES::
sage: R.<x> = Integers(77)[] sage: f = x^4 - x - 1 sage: f._derivative() 4*x^3 + 76 sage: f._derivative(None) 4*x^3 + 76
sage: f._derivative(2*x) Traceback (most recent call last): ... ValueError: cannot differentiate with respect to 2*x
sage: y = var("y") sage: f._derivative(y) Traceback (most recent call last): ... ValueError: cannot differentiate with respect to y """
|