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 emph{normalised} if the polynomial \(f(x)\) is emph{normalised}, that is, if the top coefficient is non-zero. We say this polynomial is in emph{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 emph{reduced} modulo \(p^N\) if it is canonical form and if all coefficients lie in the range \([0, p^N)\).
Memory management¶
-
void
padic_poly_init
(padic_poly_t poly)¶ Initialises
poly
for use, setting its length to zero. The precision of the polynomial is set toPADIC_DEFAULT_PREC
. A corresponding call topadic_poly_clear()
must be made after finishing with thepadic_poly_t
to free the memory used by the polynomial.
-
void
padic_poly_init2
(padic_poly_t poly, slong alloc, slong prec)¶ Initialises
poly
with space for at leastalloc
coefficients and sets the length to zero. The allocated coefficients are all set to zero. The precision is set toprec
.
-
void
padic_poly_realloc
(padic_poly_t poly, slong alloc, const fmpz_t p)¶ Reallocates the given polynomial to have space for
alloc
coefficients. Ifalloc
is zero the polynomial is cleared and then reinitialised. If the current length is greater thanalloc
the polynomial is first truncated to lengthalloc
.
-
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 leastlen
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.
-
void
_padic_poly_set_length
(padic_poly_t poly, slong len)¶ Demotes the coefficients of
poly
beyondlen
and sets the length ofpoly
tolen
.Note that if the current length is greater than
len
the polynomial may no slonger be in canonical form.
-
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.
-
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.
-
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 emph{not} carry out any reduction.
-
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.
Polynomial parameters¶
-
slong
padic_poly_degree
(padic_poly_t poly)¶ Returns the degree of the polynomial
poly
.
-
slong
padic_poly_length
(padic_poly_t poly)¶ Returns the length of the polynomial
poly
.
-
slong
padic_poly_val
(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 arvalue
.
-
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 arvalue
.Note that increasing the precision might require a call to
padic_poly_reduce()
.
Randomisation¶
-
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\).
-
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\).
-
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 valuationval
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¶
-
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.
-
void
padic_poly_set
(padic_poly_t poly1, const padic_poly_t poly2, const padic_ctx_t ctx)¶ Sets the polynomial
poly1
to the polynomialpoly2
, reduced to the precision ofpoly1
.
-
void
padic_poly_set_si
(padic_poly_t poly, slong x, const padic_ctx_t ctx)¶ Sets the polynomial
poly
to thesigned slong
integer \(x\) reduced to the precision of the polynomial.
-
void
padic_poly_set_ui
(padic_poly_t poly, ulong x, const padic_ctx_t ctx)¶ Sets the polynomial
poly
to theunsigned slong
integer \(x\) reduced to the precision of the polynomial.
-
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.
-
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.
-
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 polynomialop
reduced to the precision of the polynomial.
-
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 polynomialop
, reduced to the precision of the polynomial.
-
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 polynomialop
and returns \(1\) if the polynomial is \(p\)-adically integral. Otherwise, returns \(0\).
-
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 polynomialop
.
-
void
padic_poly_zero
(padic_poly_t poly)¶ Sets
poly
to the zero polynomial.
-
void
padic_poly_one
(padic_poly_t poly)¶ Sets
poly
to the constant polynomial \(1\), reduced to the precision of the polynomial.
-
void
padic_poly_swap
(padic_poly_t poly1, padic_poly_t poly2)¶ Swaps the two polynomials
poly1
andpoly2
, including their precisions.This is done efficiently by swapping pointers.
Getting and setting coefficients¶
-
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\).
-
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¶
-
int
padic_poly_equal
(const padic_poly_t poly1, const padic_poly_t poly2)¶ Returns whether the two polynomials
poly1
andpoly2
are equal.
-
int
padic_poly_is_zero
(const padic_poly_t poly)¶ Returns whether the polynomial
poly
is the zero polynomial.
-
int
padic_poly_is_one
(const padic_poly_t poly, const padic_ctx_t ctx)¶ Returns whether the polynomial
poly
is equal to the constant polynomial~`1`, taking the precision of the polynomial into account.
Addition and subtraction¶
-
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.
-
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\).
-
void
_padic_poly_sub
(fmpz *rop, slong *rval, const fmpz *op1, slong val1, slong len1, const fmpz *op2, slong val2, slong len2, 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.
-
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\).
-
void
padic_poly_neg
(padic_poly_t f, const padic_poly_t g, const padic_ctx_t ctx)¶ Sets \(f\) to \(-g\).
Scalar multiplication¶
-
void
_padic_poly_scalar_mul_padic
(fmpz *rop, slong *rval, 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.
-
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 polynomialop
and the \(p\)-adic number \(c\), reducing the result modulo \(p^N\).
Multiplication¶
-
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 valuationsval1
andval2
, is less than the precision~`N` of the context.Assumes that
len1 >= len2 > 0
.
-
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 polynomialspoly1
andpoly2
, reduced modulo \(p^N\).
Powering¶
-
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.
-
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 polynomialop
raised to the power~`e`, reduced to the precision inrop
.In the special case \(e = 0\), sets
rop
to the constant polynomial one reduced to the precision ofrop
. Also note that when \(e = 1\), this operation setsrop
toop
and then reducesrop
.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¶
-
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 \(- \ord_p(f) \geq N\).
Derivative¶
-
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.
-
void
padic_poly_derivative
(padic_poly_t rop, const padic_poly_t op, const padic_ctx_t ctx)¶ Sets
rop
to the derivative ofop
, reducing the result modulo the precision ofrop
.
Shifting¶
-
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 polynomialop
multiplied by \(x^n\), where \(n \geq 0\), and reduces the result.
-
void
padic_poly_shift_right
(padic_poly_t rop, const padic_poly_t op, slong n)¶ Notationally, sets the polynomial
rop
to the polynomialop
after floor division by \(x^n\), where \(n \geq 0\), ensuring the result is reduced.
Evaluation¶
-
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
topoly
evaluated at \(a\), reduced in the given context.Suppose that the polynomial can be written as \(F(X) = p^w f(X)\) with \(\ord_p(f) = 1\), that \(\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¶
-
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.
-
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 ofop1
andop2
, 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
andop2
, respectively. Thenrop
is set to \(f(g(X))\).
-
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.
-
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 ofop
and the monomial \(x^k\), where \(k \geq 1\).Note that no reduction takes place.
Input and output¶
-
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\).
-
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 streamfile
.A non-zero polynomial is represented by the number of coeffients, 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\).
-
int
padic_poly_print
(const padic_poly_t poly, const padic_ctx_t ctx)¶ Prints a simple representation of the polynomial
poly
tostdout
.In the current implementation, always returns \(1\).
-
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
(FILE *file, 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)¶