.. _padic-poly: **padic_poly.h** -- polynomials over p-adic numbers =============================================================================== Module documentation -------------------------------------------------------------------------------- We represent a polynomial in `\mathbf{Q}_p[x]` as a product `p^v f(x)`, where `p` is a prime number, `v \in \mathbf{Z}` and `f(x) \in \mathbf{Z}[x]`. As a data structure, we call this polynomial *normalised* if the polynomial `f(x)` is *normalised*, that is, if the top coefficient is non-zero. We say this polynomial is in *canonical form* if one of the coefficients of `f(x)` is a `p`-adic unit. If `f(x)` is the zero polynomial, we require that `v = 0`. We say this polynomial is *reduced* modulo `p^N` if it is canonical form and if all coefficients lie in the range `[0, p^N)`. Memory management -------------------------------------------------------------------------------- .. function:: void padic_poly_init(padic_poly_t poly) Initialises ``poly`` for use, setting its length to zero. The precision of the polynomial is set to ``PADIC_DEFAULT_PREC``. A corresponding call to :func:`padic_poly_clear` must be made after finishing with the :type:`padic_poly_t` to free the memory used by the polynomial. .. function:: void padic_poly_init2(padic_poly_t poly, slong alloc, slong prec) Initialises ``poly`` with space for at least ``alloc`` coefficients and sets the length to zero. The allocated coefficients are all set to zero. The precision is set to ``prec``. .. function:: void padic_poly_realloc(padic_poly_t poly, slong alloc, const fmpz_t p) Reallocates the given polynomial to have space for ``alloc`` coefficients. If ``alloc`` is zero the polynomial is cleared and then reinitialised. If the current length is greater than ``alloc`` the polynomial is first truncated to length ``alloc``. .. function:: void padic_poly_fit_length(padic_poly_t poly, slong len) If ``len`` is greater than the number of coefficients currently allocated, then the polynomial is reallocated to have space for at least ``len`` coefficients. No data is lost when calling this function. The function efficiently deals with the case where ``fit_length`` is called many times in small increments by at least doubling the number of allocated coefficients when length is larger than the number of coefficients currently allocated. .. function:: void _padic_poly_set_length(padic_poly_t poly, slong len) Demotes the coefficients of ``poly`` beyond ``len`` and sets the length of ``poly`` to ``len``. Note that if the current length is greater than ``len`` the polynomial may no slonger be in canonical form. .. function:: void padic_poly_clear(padic_poly_t poly) Clears the given polynomial, releasing any memory used. It must be reinitialised in order to be used again. .. function:: void _padic_poly_normalise(padic_poly_t poly) Sets the length of ``poly`` so that the top coefficient is non-zero. If all coefficients are zero, the length is set to zero. This function is mainly used internally, as all functions guarantee normalisation. .. function:: void _padic_poly_canonicalise(fmpz * poly, slong * v, slong len, const fmpz_t p) void padic_poly_canonicalise(padic_poly_t poly, const fmpz_t p) Brings the polynomial ``poly`` into canonical form, assuming that it is normalised already. Does *not* carry out any reduction. .. function:: void padic_poly_reduce(padic_poly_t poly, const padic_ctx_t ctx) Reduces the polynomial ``poly`` modulo `p^N`, assuming that it is in canonical form already. .. function:: void padic_poly_truncate(padic_poly_t poly, slong n, const fmpz_t p) Truncates the polynomial to length at most~`n`. Polynomial parameters -------------------------------------------------------------------------------- .. function:: slong padic_poly_degree(const padic_poly_t poly) Returns the degree of the polynomial ``poly``. .. function:: slong padic_poly_length(const padic_poly_t poly) Returns the length of the polynomial ``poly``. .. function:: slong padic_poly_val(const padic_poly_t poly) Returns the valuation of the polynomial ``poly``, which is defined to be the minimum valuation of all its coefficients. The valuation of the zero polynomial is~`0`. Note that this is implemented as a macro and can be used as either a ``lvalue`` or a ``rvalue``. .. function:: slong padic_poly_prec(padic_poly_t poly) Returns the precision of the polynomial ``poly``. Note that this is implemented as a macro and can be used as either a ``lvalue`` or a ``rvalue``. Note that increasing the precision might require a call to :func:`padic_poly_reduce`. Randomisation -------------------------------------------------------------------------------- .. function:: void padic_poly_randtest(padic_poly_t f, flint_rand_t state, slong len, const padic_ctx_t ctx) Sets `f` to a random polynomial of length at most ``len`` with entries reduced modulo `p^N`. .. function:: void padic_poly_randtest_not_zero(padic_poly_t f, flint_rand_t state, slong len, const padic_ctx_t ctx) Sets `f` to a non-zero random polynomial of length at most ``len`` with entries reduced modulo `p^N`. .. function:: void padic_poly_randtest_val(padic_poly_t f, flint_rand_t state, slong val, slong len, const padic_ctx_t ctx) Sets `f` to a random polynomial of length at most ``len`` with at most the prescribed valuation ``val`` and entries reduced modulo `p^N`. Specifically, we aim to set the valuation to be exactly equal to ``val``, but do not check for additional cancellation when creating the coefficients. Assignment and basic manipulation -------------------------------------------------------------------------------- .. function:: void padic_poly_set_padic(padic_poly_t poly, const padic_t x, const padic_ctx_t ctx) Sets the polynomial ``poly`` to the `p`-adic number `x`, reduced to the precision of the polynomial. .. function:: void padic_poly_set(padic_poly_t poly1, const padic_poly_t poly2, const padic_ctx_t ctx) Sets the polynomial ``poly1`` to the polynomial ``poly2``, reduced to the precision of ``poly1``. .. function:: void padic_poly_set_si(padic_poly_t poly, slong x, const padic_ctx_t ctx) Sets the polynomial ``poly`` to the ``signed slong`` integer `x` reduced to the precision of the polynomial. .. function:: void padic_poly_set_ui(padic_poly_t poly, ulong x, const padic_ctx_t ctx) Sets the polynomial ``poly`` to the ``unsigned slong`` integer `x` reduced to the precision of the polynomial. .. function:: void padic_poly_set_fmpz(padic_poly_t poly, const fmpz_t x, const padic_ctx_t ctx) Sets the polynomial ``poly`` to the integer `x` reduced to the precision of the polynomial. .. function:: void padic_poly_set_fmpq(padic_poly_t poly, const fmpq_t x, const padic_ctx_t ctx) Sets the polynomial ``poly`` to the value of the rational `x`, reduced to the precision of the polynomial. .. function:: void padic_poly_set_fmpz_poly(padic_poly_t rop, const fmpz_poly_t op, const padic_ctx_t ctx) Sets the polynomial ``rop`` to the integer polynomial ``op`` reduced to the precision of the polynomial. .. function:: void padic_poly_set_fmpq_poly(padic_poly_t rop, const fmpq_poly_t op, const padic_ctx_t ctx) Sets the polynomial ``rop`` to the value of the rational polynomial ``op``, reduced to the precision of the polynomial. .. function:: int padic_poly_get_fmpz_poly(fmpz_poly_t rop, const padic_poly_t op, const padic_ctx_t ctx) Sets the integer polynomial ``rop`` to the value of the `p`-adic polynomial ``op`` and returns `1` if the polynomial is `p`-adically integral. Otherwise, returns `0`. .. function:: void padic_poly_get_fmpq_poly(fmpq_poly_t rop, const padic_poly_t op, const padic_ctx_t ctx) Sets ``rop`` to the rational polynomial corresponding to the `p`-adic polynomial ``op``. .. function:: void padic_poly_zero(padic_poly_t poly) Sets ``poly`` to the zero polynomial. .. function:: void padic_poly_one(padic_poly_t poly) Sets ``poly`` to the constant polynomial `1`, reduced to the precision of the polynomial. .. function:: void padic_poly_swap(padic_poly_t poly1, padic_poly_t poly2) Swaps the two polynomials ``poly1`` and ``poly2``, including their precisions. This is done efficiently by swapping pointers. Getting and setting coefficients -------------------------------------------------------------------------------- .. function:: void padic_poly_get_coeff_padic(padic_t c, const padic_poly_t poly, slong n, const padic_ctx_t ctx) Sets `c` to the coefficient of `x^n` in the polynomial, reduced modulo the precision of `c`. .. function:: void padic_poly_set_coeff_padic(padic_poly_t f, slong n, const padic_t c, const padic_ctx_t ctx) Sets the coefficient of `x^n` in the polynomial `f` to `c`, reduced to the precision of the polynomial `f`. Note that this operation can take linear time in the length of the polynomial. Comparison -------------------------------------------------------------------------------- .. function:: int padic_poly_equal(const padic_poly_t poly1, const padic_poly_t poly2) Returns whether the two polynomials ``poly1`` and ``poly2`` are equal. .. function:: int padic_poly_is_zero(const padic_poly_t poly) Returns whether the polynomial ``poly`` is the zero polynomial. .. function:: int padic_poly_is_one(const padic_poly_t poly) Returns whether the polynomial ``poly`` is equal to the constant polynomial~`1`, taking the precision of the polynomial into account. Addition and subtraction -------------------------------------------------------------------------------- .. function:: void _padic_poly_add(fmpz * rop, slong * rval, slong N, const fmpz * op1, slong val1, slong len1, slong N1, const fmpz * op2, slong val2, slong len2, slong N2, const padic_ctx_t ctx) Sets ``(rop, *val, FLINT_MAX(len1, len2)`` to the sum of ``(op1, val1, len1)`` and ``(op2, val2, len2)``. Assumes that the input is reduced and guarantees that this is also the case for the output. Assumes that `\min\{v_1, v_2\} < N`. Supports aliasing between the output and input arguments. .. function:: void padic_poly_add(padic_poly_t f, const padic_poly_t g, const padic_poly_t h, const padic_ctx_t ctx) Sets `f` to the sum `g + h`. .. function:: void _padic_poly_sub(fmpz * rop, slong * rval, slong N, const fmpz * op1, slong val1, slong len1, slong N1, const fmpz * op2, slong val2, slong len2, slong N2, const padic_ctx_t ctx) Sets ``(rop, *val, FLINT_MAX(len1, len2)`` to the difference of ``(op1, val1, len1)`` and ``(op2, val2, len2)``. Assumes that the input is reduced and guarantees that this is also the case for the output. Assumes that `\min\{v_1, v_2\} < N`. Support aliasing between the output and input arguments. .. function:: void padic_poly_sub(padic_poly_t f, const padic_poly_t g, const padic_poly_t h, const padic_ctx_t ctx) Sets `f` to the difference `g - h`. .. function:: void padic_poly_neg(padic_poly_t f, const padic_poly_t g, const padic_ctx_t ctx) Sets `f` to `-g`. Scalar multiplication -------------------------------------------------------------------------------- .. function:: void _padic_poly_scalar_mul_padic(fmpz * rop, slong * rval, slong N, const fmpz * op, slong val, slong len, const padic_t c, const padic_ctx_t ctx) Sets ``(rop, *rval, len)`` to ``(op, val, len)`` multiplied by the scalar `c`. The result will only be correctly reduced if the polynomial is non-zero. Otherwise, the array ``(rop, len)`` will be set to zero but the valuation ``*rval`` might be wrong. .. function:: void padic_poly_scalar_mul_padic(padic_poly_t rop, const padic_poly_t op, const padic_t c, const padic_ctx_t ctx) Sets the polynomial ``rop`` to the product of the polynomial ``op`` and the `p`-adic number `c`, reducing the result modulo `p^N`. Multiplication -------------------------------------------------------------------------------- .. function:: void _padic_poly_mul(fmpz * rop, slong * rval, slong N, const fmpz * op1, slong val1, slong len1, const fmpz * op2, slong val2, slong len2, const padic_ctx_t ctx) Sets ``(rop, *rval, len1 + len2 - 1)`` to the product of ``(op1, val1, len1)`` and ``(op2, val2, len2)``. Assumes that the resulting valuation ``*rval``, which is the sum of the valuations ``val1`` and ``val2``, is less than the precision~`N` of the context. Assumes that ``len1 >= len2 > 0``. .. function:: void padic_poly_mul(padic_poly_t res, const padic_poly_t poly1, const padic_poly_t poly2, const padic_ctx_t ctx) Sets the polynomial ``res`` to the product of the two polynomials ``poly1`` and ``poly2``, reduced modulo `p^N`. Powering -------------------------------------------------------------------------------- .. function:: void _padic_poly_pow(fmpz * rop, slong * rval, slong N, const fmpz * op, slong val, slong len, ulong e, const padic_ctx_t ctx) Sets the polynomial ``(rop, *rval, e (len - 1) + 1)`` to the polynomial ``(op, val, len)`` raised to the power~`e`. Assumes that `e > 1` and ``len > 0``. Does not support aliasing between the input and output arguments. .. function:: void padic_poly_pow(padic_poly_t rop, const padic_poly_t op, ulong e, const padic_ctx_t ctx) Sets the polynomial ``rop`` to the polynomial ``op`` raised to the power~`e`, reduced to the precision in ``rop``. In the special case `e = 0`, sets ``rop`` to the constant polynomial one reduced to the precision of ``rop``. Also note that when `e = 1`, this operation sets ``rop`` to ``op`` and then reduces ``rop``. When the valuation of the input polynomial is negative, this results in a loss of `p`-adic precision. Suppose that the input polynomial is given to precision~`N` and has valuation~`v < 0`. The result then has valuation `e v < 0` but is only correct to precision `N + (e - 1) v`. Series inversion -------------------------------------------------------------------------------- .. function:: void padic_poly_inv_series(padic_poly_t g, const padic_poly_t f, slong n, const padic_ctx_t ctx) Computes the power series inverse `g` of `f` modulo `X^n`, where `n \geq 1`. Given the polynomial `f \in \mathbf{Q}[X] \subset \mathbf{Q}_p[X]`, there exists a unique polynomial `f^{-1} \in \mathbf{Q}[X]` such that `f f^{-1} = 1` modulo `X^n`. This function sets `g` to `f^{-1}` reduced modulo `p^N`. Assumes that the constant coefficient of `f` is non-zero. Moreover, assumes that the valuation of the constant coefficient of `f` is minimal among the coefficients of `f`. Note that the result `g` is zero if and only if `- \operatorname{ord}_p(f) \geq N`. Derivative -------------------------------------------------------------------------------- .. function:: void _padic_poly_derivative(fmpz * rop, slong * rval, slong N, const fmpz * op, slong val, slong len, const padic_ctx_t ctx) Sets ``(rop, rval)`` to the derivative of ``(op, val)`` reduced modulo `p^N`. Supports aliasing of the input and the output parameters. .. function:: void padic_poly_derivative(padic_poly_t rop, const padic_poly_t op, const padic_ctx_t ctx) Sets ``rop`` to the derivative of ``op``, reducing the result modulo the precision of ``rop``. Shifting -------------------------------------------------------------------------------- .. function:: void padic_poly_shift_left(padic_poly_t rop, const padic_poly_t op, slong n, const padic_ctx_t ctx) Notationally, sets the polynomial ``rop`` to the polynomial ``op`` multiplied by `x^n`, where `n \geq 0`, and reduces the result. .. function:: void padic_poly_shift_right(padic_poly_t rop, const padic_poly_t op, slong n, const padic_ctx_t ctx) Notationally, sets the polynomial ``rop`` to the polynomial ``op`` after floor division by `x^n`, where `n \geq 0`, ensuring the result is reduced. Evaluation -------------------------------------------------------------------------------- .. function:: void _padic_poly_evaluate_padic(fmpz_t u, slong * v, slong N, const fmpz * poly, slong val, slong len, const fmpz_t a, slong b, const padic_ctx_t ctx) void padic_poly_evaluate_padic(padic_t y, const padic_poly_t poly, const padic_t a, const padic_ctx_t ctx) Sets the `p`-adic number ``y`` to ``poly`` evaluated at `a`, reduced in the given context. Suppose that the polynomial can be written as `F(X) = p^w f(X)` with `\operatorname{ord}_p(f) = 1`, that `\operatorname{ord}_p(a) = b` and that both are defined to precision~`N`. Then `f` is defined to precision `N-w` and so `f(a)` is defined to precision `N-w` when `a` is integral and `N-w+(n-1)b` when `b < 0`, where `n = \deg(f)`. Thus, `y = F(a)` is defined to precision `N` when `a` is integral and `N+(n-1)b` when `b < 0`. Composition -------------------------------------------------------------------------------- .. function:: void _padic_poly_compose(fmpz * rop, slong * rval, slong N, const fmpz * op1, slong val1, slong len1, const fmpz * op2, slong val2, slong len2, const padic_ctx_t ctx) Sets ``(rop, *rval, (len1-1)*(len2-1)+1)`` to the composition of the two input polynomials, reducing the result modulo `p^N`. Assumes that ``len1`` is non-zero. Does not support aliasing. .. function:: void padic_poly_compose(padic_poly_t rop, const padic_poly_t op1, const padic_poly_t op2, const padic_ctx_t ctx) Sets ``rop`` to the composition of ``op1`` and ``op2``, reducing the result in the given context. To be clear about the order of composition, let `f(X)` and `g(X)` denote the polynomials ``op1`` and ``op2``, respectively. Then ``rop`` is set to `f(g(X))`. .. function:: void _padic_poly_compose_pow(fmpz * rop, slong * rval, slong N, const fmpz * op, slong val, slong len, slong k, const padic_ctx_t ctx) Sets ``(rop, *rval, (len - 1)*k + 1)`` to the composition of ``(op, val, len)`` and the monomial `x^k`, where `k \geq 1`. Assumes that ``len`` is positive. Supports aliasing between the input and output polynomials. .. function:: void padic_poly_compose_pow(padic_poly_t rop, const padic_poly_t op, slong k, const padic_ctx_t ctx) Sets ``rop`` to the composition of ``op`` and the monomial `x^k`, where `k \geq 1`. Note that no reduction takes place. Input and output -------------------------------------------------------------------------------- .. function:: int padic_poly_debug(const padic_poly_t poly) Prints the data defining the `p`-adic polynomial ``poly`` in a simple format useful for debugging purposes. In the current implementation, always returns `1`. .. function:: int _padic_poly_fprint(FILE * file, const fmpz * poly, slong val, slong len, const padic_ctx_t ctx) int padic_poly_fprint(FILE * file, const padic_poly_t poly, const padic_ctx_t ctx) Prints a simple representation of the polynomial ``poly`` to the stream ``file``. A non-zero polynomial is represented by the number of coefficients, two spaces, followed by a list of the coefficients, which are printed in a way depending on the print mode, In the ``PADIC_TERSE`` mode, the coefficients are printed as rational numbers. The ``PADIC_SERIES`` mode is currently not supported and will raise an abort signal. In the ``PADIC_VAL_UNIT`` mode, the coefficients are printed in the form `p^v u`. The zero polynomial is represented by ``"0"``. In the current implementation, always returns `1`. .. function:: int _padic_poly_print(const fmpz * poly, slong val, slong len, const padic_ctx_t ctx) int padic_poly_print(const padic_poly_t poly, const padic_ctx_t ctx) Prints a simple representation of the polynomial ``poly`` to ``stdout``. In the current implementation, always returns `1`. .. function:: int _padic_poly_fprint_pretty(FILE * file, const fmpz * poly, slong val, slong len, const char * var, const padic_ctx_t ctx) int padic_poly_fprint_pretty(FILE * file, const padic_poly_t poly, const char * var, const padic_ctx_t ctx) int _padic_poly_print_pretty(const fmpz * poly, slong val, slong len, const char * var, const padic_ctx_t ctx) int padic_poly_print_pretty(const padic_poly_t poly, const char * var, const padic_ctx_t ctx) Testing -------------------------------------------------------------------------------- .. function:: int _padic_poly_is_canonical(const fmpz * op, slong val, slong len, const padic_ctx_t ctx) int padic_poly_is_canonical(const padic_poly_t op, const padic_ctx_t ctx) int _padic_poly_is_reduced(const fmpz * op, slong val, slong len, slong N, const padic_ctx_t ctx) int padic_poly_is_reduced(const padic_poly_t op, const padic_ctx_t ctx)