.. _padic:

**padic.h** -- p-adic numbers
===============================================================================


Introduction
--------------------------------------------------------------------------------

The ``padic_t`` data type represents elements of `\mathbf{Q}_p` to
precision `N`, stored in the form `x = p^v u` with `u, v \in \mathbf{Z}`.
Arithmetic operations can be carried out with respect to a context
containing the prime number `p` and various pieces of pre-computed data.

Independent of the context, we consider a `p`-adic number
`x = u p^v` to be in canonical form whenever either
`p \nmid u` or `u = v = 0`, and we say it is reduced
if, in addition, for non-zero `u`, `u \in (0, p^{N-v})`.

We briefly describe the interface:

The functions in this module expect arguments of type ``padic_t``,
and each variable carries its own precision.  The functions have an
interface that is similar to the MPFR functions.  In particular, they
have the same semantics, specified as follows:  Compute the requested
operation exactly and then reduce the result to the precision of the
output variable.

Data structures
--------------------------------------------------------------------------------

A `p`-adic number of type ``padic_t`` comprises a unit `u`, 
a valuation `v`, and a precision `N`.
We provide the following macros to access these fields, so that 
code can be developed somewhat independently from the underlying 
data layout.

.. function:: fmpz * padic_unit(const padic_t op)

    Returns the unit part of the `p`-adic number as a FLINT integer, which 
    can be used as an operand for the ``fmpz`` functions.

.. function:: slong padic_val(const padic_t op)

    Returns the valuation part of the `p`-adic number.

    Note that this function is implemented as a macro and that 
    the expression ``padic_val(op)`` can be used as both an 
    *lvalue* and an *rvalue*.

.. function:: slong padic_get_val(const padic_t op)

    Returns the valuation part of the `p`-adic number.

.. function:: slong padic_prec(const padic_t op)

    Returns the precision of the `p`-adic number.

    Note that this function is implemented as a macro and that 
    the expression ``padic_prec(op)`` can be used as both an 
    *lvalue* and an *rvalue*.

.. function:: slong padic_get_prec(const padic_t op)

    Returns the precision of the `p`-adic number.


Context
--------------------------------------------------------------------------------

A context object for `p`-adic arithmetic contains data pertinent to 
`p`-adic computations, but which we choose not to store with each 
element individually.
Currently, this includes the prime number `p`, its ``double`` 
inverse in case of word-sized primes, precomputed powers of `p` 
in the range given by ``min`` and ``max``, and the printing 
mode.

.. function:: void padic_ctx_init(padic_ctx_t ctx, const fmpz_t p, slong min, slong max, enum padic_print_mode mode)

    Initialises the context ``ctx`` with the given data.

    Assumes that `p` is a prime.  This is not verified but the subsequent 
    behaviour is undefined if `p` is a composite number.

    Assumes that ``min`` and ``max`` are non-negative and that 
    ``min`` is at most ``max``, raising an ``abort`` signal 
    otherwise.

    Assumes that the printing mode is one of ``PADIC_TERSE``, 
    ``PADIC_SERIES``, or ``PADIC_VAL_UNIT``.  Using the example 
    `x = 7^{-1} 12` in `\mathbf{Q}_7`, these behave as follows:

    In ``PADIC_TERSE`` mode, a `p`-adic number is printed 
    in the same way as a rational number, e.g. ``12/7``.

    In ``PADIC_SERIES`` mode, a `p`-adic number is printed 
    digit by digit, e.g. ``5*7^-1 + 1``.

    In ``PADIC_VAL_UNIT`` mode, a `p`-adic number is 
    printed showing the valuation and unit parts separately, 
    e.g. ``12*7^-1``.

.. function:: void padic_ctx_clear(padic_ctx_t ctx)

    Clears all memory that has been allocated as part of the context.

.. function:: int _padic_ctx_pow_ui(fmpz_t rop, ulong e, const padic_ctx_t ctx)

    Sets ``rop`` to `p^e` as efficiently as possible, where 
    ``rop`` is expected to be an uninitialised ``fmpz_t``.

    If the return value is non-zero, it is the responsibility of 
    the caller to clear the returned integer.


Memory management
--------------------------------------------------------------------------------


.. function:: void padic_init(padic_t rop)

    Initialises the `p`-adic number with the precision set to 
    ``PADIC_DEFAULT_PREC``, which is defined as `20`.

.. function:: void padic_init2(padic_t rop, slong N)

    Initialises the `p`-adic number ``rop`` with precision `N`.

.. function:: void padic_clear(padic_t rop)

    Clears all memory used by the `p`-adic number ``rop``.

.. function:: void _padic_canonicalise(padic_t rop, const padic_ctx_t ctx)

    Brings the `p`-adic number ``rop`` into canonical form.

    That is to say, ensures that either `u = v = 0` or 
    `p \nmid u`.  There is no reduction modulo a power 
    of `p`.

.. function:: void _padic_reduce(padic_t rop, const padic_ctx_t ctx)

    Given a `p`-adic number ``rop`` in canonical form, 
    reduces it modulo `p^N`.

.. function:: void padic_reduce(padic_t rop, const padic_ctx_t ctx)

    Ensures that the `p`-adic number ``rop`` is reduced.


Randomisation
--------------------------------------------------------------------------------


.. function:: void padic_randtest(padic_t rop, flint_rand_t state, const padic_ctx_t ctx)

    Sets ``rop`` to a random `p`-adic number modulo `p^N` with valuation 
    in the range `[- \lceil N/10\rceil, N)`, `[N - \lceil -N/10\rceil, N)`, or `[-10, 0)` 
    as `N` is positive, negative or zero, whenever ``rop`` is non-zero.

.. function:: void padic_randtest_not_zero(padic_t rop, flint_rand_t state, const padic_ctx_t ctx)

    Sets ``rop`` to a random non-zero `p`-adic number modulo `p^N`, 
    where the range of the valuation is as for the function 
    :func:`padic_randtest`.

.. function:: void padic_randtest_int(padic_t rop, flint_rand_t state, const padic_ctx_t ctx)

    Sets ``rop`` to a random `p`-adic integer modulo `p^N`.

    Note that whenever `N \leq 0`, ``rop`` is set to zero.


Assignments and conversions
--------------------------------------------------------------------------------

All assignment functions set the value of ``rop`` from ``op``, 
reduced to the precision of ``rop``.

.. function:: void padic_set(padic_t rop, const padic_t op, const padic_ctx_t ctx)

    Sets ``rop`` to the `p`-adic number ``op``.

.. function:: void padic_set_si(padic_t rop, slong op, const padic_ctx_t ctx)

    Sets the `p`-adic number ``rop`` to the 
    ``slong`` integer ``op``.

.. function:: void padic_set_ui(padic_t rop, ulong op, const padic_ctx_t ctx)

    Sets the `p`-adic number ``rop`` to the ``ulong`` 
    integer ``op``.

.. function:: void padic_set_fmpz(padic_t rop, const fmpz_t op, const padic_ctx_t ctx)

    Sets the `p`-adic number ``rop`` to the integer ``op``.

.. function:: void padic_set_fmpq(padic_t rop, const fmpq_t op, const padic_ctx_t ctx)

    Sets ``rop`` to the rational ``op``.

.. function:: void padic_set_mpz(padic_t rop, const mpz_t op, const padic_ctx_t ctx)

    Sets the `p`-adic number ``rop`` to the MPIR integer ``op``.

.. function:: void padic_set_mpq(padic_t rop, const mpq_t op, const padic_ctx_t ctx)

    Sets ``rop`` to the MPIR rational ``op``.

.. function:: void padic_get_fmpz(fmpz_t rop, const padic_t op, const padic_ctx_t ctx)

    Sets the integer ``rop`` to the exact `p`-adic integer ``op``.

    If ``op`` is not a `p`-adic integer, raises an ``abort`` signal.

.. function:: void padic_get_fmpq(fmpq_t rop, const padic_t op, const padic_ctx_t ctx)

    Sets the rational ``rop`` to the `p`-adic number ``op``.

.. function:: void padic_get_mpz(mpz_t rop, const padic_t op, const padic_ctx_t ctx)

    Sets the MPIR integer ``rop`` to the `p`-adic integer ``op``.

    If ``op`` is not a `p`-adic integer, raises an ``abort`` signal.

.. function:: void padic_get_mpq(mpq_t rop, const padic_t op, const padic_ctx_t ctx)

    Sets the MPIR rational ``rop`` to the value of ``op``.

.. function:: void padic_swap(padic_t op1, padic_t op2)

    Swaps the two `p`-adic numbers ``op1`` and ``op2``.

    Note that this includes swapping the precisions.  In particular, this 
    operation is not equivalent to swapping ``op1`` and ``op2`` 
    using :func:`padic_set` and an auxiliary variable whenever the 
    precisions of the two elements are different.

.. function:: void padic_zero(padic_t rop)

    Sets the `p`-adic number ``rop`` to zero.

.. function:: void padic_one(padic_t rop)

    Sets the `p`-adic number ``rop`` to one, reduced modulo the 
    precision of ``rop``.


Comparison
--------------------------------------------------------------------------------


.. function:: int padic_is_zero(const padic_t op)

    Returns whether ``op`` is equal to zero.

.. function:: int padic_is_one(const padic_t op)

    Returns whether ``op`` is equal to one, that is, whether 
    `u = 1` and `v = 0`.

.. function:: int padic_equal(const padic_t op1, const padic_t op2)

    Returns whether ``op1`` and ``op2`` are equal, that is, 
    whether `u_1 = u_2` and `v_1 = v_2`.


Arithmetic operations
--------------------------------------------------------------------------------


.. function:: slong * _padic_lifts_exps(slong *n, slong N)

    Given a positive integer `N` define the sequence 
    `a_0 = N, a_1 = \lceil a_0/2\rceil, \dotsc, a_{n-1} = \lceil a_{n-2}/2\rceil = 1`.
    Then `n = \lceil\log_2 N\rceil + 1`.

    This function sets `n` and allocates and returns the array `a`.

.. function:: void _padic_lifts_pows(fmpz *pow, const slong *a, slong n, const fmpz_t p)

    Given an array `a` as computed above, this function 
    computes the corresponding powers of `p`, that is, 
    ``pow[i]`` is equal to `p^{a_i}`.

.. function:: void padic_add(padic_t rop, const padic_t op1, const padic_t op2, const padic_ctx_t ctx)

    Sets ``rop`` to the sum of ``op1`` and ``op2``.

.. function:: void padic_sub(padic_t rop, const padic_t op1, const padic_t op2, const padic_ctx_t ctx)

    Sets ``rop`` to the difference of ``op1`` and ``op2``.

.. function:: void padic_neg(padic_t rop, const padic_t op, const padic_ctx_t ctx)

    Sets ``rop`` to the additive inverse of ``op``.

.. function:: void padic_mul(padic_t rop, const padic_t op1, const padic_t op2, const padic_ctx_t ctx)

    Sets ``rop`` to the product of ``op1`` and ``op2``.

.. function:: void padic_shift(padic_t rop, const padic_t op, slong v, const padic_ctx_t ctx)

    Sets ``rop`` to the product of ``op`` and `p^v`.

.. function:: void padic_div(padic_t rop, const padic_t op1, const padic_t op2, const padic_ctx_t ctx)

    Sets ``rop`` to the quotient of ``op1`` and ``op2``.

.. function:: void _padic_inv_precompute(padic_inv_t S, const fmpz_t p, slong N)

    Pre-computes some data and allocates temporary space for 
    `p`-adic inversion using Hensel lifting.

.. function:: void _padic_inv_clear(padic_inv_t S)

    Frees the memory used by `S`.

.. function:: void _padic_inv_precomp(fmpz_t rop, const fmpz_t op, const padic_inv_t S)

    Sets ``rop`` to the inverse of ``op`` modulo `p^N`, 
    assuming that ``op`` is a unit and `N \geq 1`.

    In the current implementation, allows aliasing, but this might 
    change in future versions.

    Uses some data `S` precomputed by calling the function 
    :func:`_padic_inv_precompute`.  Note that this object 
    is not declared ``const`` and in fact it carries a field 
    providing temporary work space.  This allows repeated calls of 
    this function to avoid repeated memory allocations, as used 
    e.g. by the function :func:`padic_log`.

.. function:: void _padic_inv(fmpz_t rop, const fmpz_t op, const fmpz_t p, slong N)

    Sets ``rop`` to the inverse of ``op`` modulo `p^N`, 
    assuming that ``op`` is a unit and `N \geq 1`.

    In the current implementation, allows aliasing, but this might 
    change in future versions.

.. function:: void padic_inv(padic_t rop, const padic_t op, const padic_ctx_t ctx)

    Computes the inverse of ``op`` modulo `p^N`.

    Suppose that ``op`` is given as `x = u p^v`. 
    Raises an ``abort`` signal if `v < -N`.  Otherwise, 
    computes the inverse of `u` modulo `p^{N+v}`.

    This function employs Hensel lifting of an inverse modulo `p`.

.. function:: int padic_sqrt(padic_rop, const padic_t op, const padic_ctx_t ctx)

    Returns whether ``op`` is a `p`-adic square.  If this is 
    the case, sets ``rop`` to one of the square roots;  otherwise, 
    the value of ``rop`` is undefined.

    We have the following theorem:

    Let `u \in \mathbf{Z}^{\times}`.  Then `u` is a 
    square if and only if `u \bmod p` is a square in 
    `\mathbf{Z} / p \mathbf{Z}`, for `p > 2`, or if 
    `u \bmod 8` is a square in `\mathbf{Z} / 8 \mathbf{Z}`, 
    for `p = 2`.

.. function:: void padic_pow_si(padic_t rop, const padic_t op, slong e, const padic_ctx_t ctx)

    Sets ``rop`` to ``op`` raised to the power `e`, 
    which is defined as one whenever `e = 0`.

    Assumes that some computations involving `e` and the 
    valuation of ``op`` do not overflow in the ``slong`` 
    range.

    Note that if the input `x = p^v u` is defined modulo `p^N` 
    then `x^e = p^{ev} u^e` is defined modulo `p^{N + (e - 1) v}`, 
    which is a precision loss in case `v < 0`.


Exponential
--------------------------------------------------------------------------------


.. function:: slong _padic_exp_bound(slong v, slong N, const fmpz_t p)

    Returns an integer `i` such that for all `j \geq i` we have 
    `\operatorname{ord}_p(x^j / j!) \geq N`, where `\operatorname{ord}_p(x) = v`.

    When `p` is a word-sized prime, 
    returns `\left\lceil \frac{(p-1)N - 1}{(p-1)v - 1}\right\rceil`.
    Otherwise, returns `\lceil N/v\rceil`.

    Assumes that `v < N`.  Moreover, `v` has to be at least `2` or `1`, 
    depending on whether `p` is `2` or odd.

.. function:: void _padic_exp_rectangular(fmpz_t rop, const fmpz_t u, slong v, const fmpz_t p, slong N)
              void _padic_exp_balanced(fmpz_t rop, const fmpz_t u, slong v, const fmpz_t p, slong N)
              void _padic_exp(fmpz_t rop, const fmpz_t u, slong v, const fmpz_t p, slong N)

    Sets ``rop`` to the `p`-exponential function evaluated at 
    `x = p^v u`, reduced modulo `p^N`.

    Assumes that `x \neq 0`, that `\operatorname{ord}_p(x) < N` and that 
    `\exp(x)` converges, that is, that `\operatorname{ord}_p(x)` is at least 
    `2` or `1` depending on whether the prime `p` is `2` or odd.

    Supports aliasing between ``rop`` and `u`.

.. function:: int padic_exp(padic_t y, const padic_t x, const padic_ctx_t ctx)

    Returns whether the `p`-adic exponential function converges at 
    the `p`-adic number `x`, and if so sets `y` to its value.

    The `p`-adic exponential function is defined by the usual series 

    .. math ::


        \exp_p(x) = \sum_{i = 0}^{\infty} \frac{x^i}{i!}


    but this only converges only when `\operatorname{ord}_p(x) > 1 / (p - 1)`.  For 
    elements `x \in \mathbf{Q}_p`, this means that `\operatorname{ord}_p(x) \geq 1` 
    when `p \geq 3` and `\operatorname{ord}_2(x) \geq 2` when `p = 2`.

.. function:: int padic_exp_rectangular(padic_t y, const padic_t x, const padic_ctx_t ctx)

    Returns whether the `p`-adic exponential function converges at 
    the `p`-adic number `x`, and if so sets `y` to its value.

    Uses a rectangular splitting algorithm to evaluate the series 
    expression of `\exp(x) \bmod{p^N}`.

.. function:: int padic_exp_balanced(padic_t y, const padic_t x, const padic_ctx_t ctx)

    Returns whether the `p`-adic exponential function converges at 
    the `p`-adic number `x`, and if so sets `y` to its value.

    Uses a balanced approach, balancing the size of chunks of `x` 
    with the valuation and hence the rate of convergence, which 
    results in a quasi-linear algorithm in `N`, for fixed `p`.


Logarithm
--------------------------------------------------------------------------------


.. function:: slong _padic_log_bound(slong v, slong N, const fmpz_t p)

    Returns `b` such that for all `i \geq b` we have 

    .. math ::


        i v - \operatorname{ord}_p(i) \geq N


    where `v \geq 1`.

    Assumes that `1 \leq v < N` or `2 \leq v < N` when `p` is 
    odd or `p = 2`, respectively, and also that `N < 2^{f-2}` 
    where `f` is ``FLINT_BITS``.

.. function:: void _padic_log(fmpz_t z, const fmpz_t y, slong v, const fmpz_t p, slong N)
              void _padic_log_rectangular(fmpz_t z, const fmpz_t y, slong v, const fmpz_t p, slong N)
              void _padic_log_satoh(fmpz_t z, const fmpz_t y, slong v, const fmpz_t p, slong N)
              void _padic_log_balanced(fmpz_t z, const fmpz_t y, slong v, const fmpz_t p, slong N)

    Computes 

    .. math ::

        z = - \sum_{i = 1}^{\infty} \frac{y^i}{i} \pmod{p^N},

    reduced modulo `p^N`.

    Note that this can be used to compute the `p`-adic logarithm 
    via the equation 

    .. math ::

        \log(x) & = \sum_{i=1}^{\infty} (-1)^{i-1} \frac{(x-1)^i}{i} \\
                & = - \sum_{i=1}^{\infty} \frac{(1-x)^i}{i}.

    Assumes that `y = 1 - x` is non-zero and that `v = \operatorname{ord}_p(y)` 
    is at least `1` when `p` is odd and at least `2` when `p = 2` 
    so that the series converges.

    Assumes that `v < N`, and hence in particular `N \geq 2`.

    Does not support aliasing between `y` and `z`.

.. function:: int padic_log(padic_t rop, const padic_t op, const padic_ctx_t ctx)

    Returns whether the `p`-adic logarithm function converges at 
    the `p`-adic number ``op``, and if so sets ``rop`` to its 
    value.

    The `p`-adic logarithm function is defined by the usual series 

    .. math ::

        \log_p(x) = \sum_{i=1}^{\infty} (-1)^{i-1} \frac{(x-1)^i}{i}

    but this only converges when `\operatorname{ord}_p(x - 1)` is at least `2`
    or `1` when `p = 2` or `p > 2`, respectively.

.. function:: int padic_log_rectangular(padic_t rop, const padic_t op, const padic_ctx_t ctx)

    Returns whether the `p`-adic logarithm function converges at 
    the `p`-adic number ``op``, and if so sets ``rop`` to its 
    value.

    Uses a rectangular splitting algorithm to evaluate the series 
    expression of `\log(x) \bmod{p^N}`.

.. function:: int padic_log_satoh(padic_t rop, const padic_t op, const padic_ctx_t ctx)

    Returns whether the `p`-adic logarithm function converges at 
    the `p`-adic number ``op``, and if so sets ``rop`` to its 
    value.

    Uses an algorithm based on a result of Satoh, Skjernaa and Taguchi 
    that `\operatorname{ord}_p\bigl(a^{p^k} - 1\bigr) > k`, which implies that 

    .. math ::

        \log(a) \equiv p^{-k} \Bigl( \log\bigl(a^{p^k}\bigr) \pmod{p^{N+k}} 
                                                          \Bigr) \pmod{p^N}.


.. function:: int padic_log_balanced(padic_t rop, const padic_t op, const padic_ctx_t ctx)

    Returns whether the `p`-adic logarithm function converges at 
    the `p`-adic number ``op``, and if so sets ``rop`` to its 
    value.


Special functions
--------------------------------------------------------------------------------


.. function:: void _padic_teichmuller(fmpz_t rop, const fmpz_t op, const fmpz_t p, slong N)

    Computes the Teichm\"uller lift of the `p`-adic unit ``op``, 
    assuming that `N \geq 1`.

    Supports aliasing between ``rop`` and ``op``.

.. function:: void padic_teichmuller(padic_t rop, const padic_t op, const padic_ctx_t ctx)

    Computes the Teichm\"uller lift of the `p`-adic unit ``op``.

    If ``op`` is a `p`-adic integer divisible by `p`, sets ``rop`` 
    to zero, which satisfies `t^p - t = 0`, although it is clearly not 
    a `(p-1)`-st root of unity.

    If ``op`` has negative valuation, raises an ``abort`` signal.

.. function:: ulong padic_val_fac_ui_2(ulong n)

    Computes the `2`-adic valuation of `n!`.

    Note that since `n` fits into an ``ulong``, so does 
    `\operatorname{ord}_2(n!)` since `\operatorname{ord}_2(n!) \leq (n - 1) / (p - 1) = n - 1`.

.. function:: ulong padic_val_fac_ui(ulong n, const fmpz_t p)

    Computes the `p`-adic valuation of `n!`.

    Note that since `n` fits into an ``ulong``, so does 
    `\operatorname{ord}_p(n!)` since `\operatorname{ord}_p(n!) \leq (n - 1) / (p - 1)`.

.. function:: void padic_val_fac(fmpz_t rop, const fmpz_t op, const fmpz_t p)

    Sets ``rop`` to the `p`-adic valuation of the factorial 
    of ``op``, assuming that ``op`` is non-negative.


Input and output
--------------------------------------------------------------------------------


.. function:: char * padic_get_str(char * str, const padic_t op, const padic_ctx_t ctx)

    Returns the string representation of the `p`-adic number ``op``
    according to the printing mode set in the context.

    If ``str`` is ``NULL`` then a new block of memory is allocated 
    and a pointer to this is returned.  Otherwise, it is assumed that 
    the string ``str`` is large enough to hold the representation and 
    it is also the return value.

.. function:: int _padic_fprint(FILE * file, const fmpz_t u, slong v, const padic_ctx_t ctx)
              int padic_fprint(FILE * file, const padic_t op, const padic_ctx_t ctx)

    Prints the string representation of the `p`-adic number ``op`` 
    to the stream ``file``.

    In the current implementation, always returns `1`.

.. function:: int _padic_print(const fmpz_t u, slong v, const padic_ctx_t ctx)
              int padic_print(const padic_t op, const padic_ctx_t ctx)

    Prints the string representation of the `p`-adic number ``op`` 
    to the stream ``stdout``.

    In the current implementation, always returns `1`.

.. function:: void padic_debug(const padic_t op)

    Prints debug information about ``op`` to the stream ``stdout``, 
    in the format ``"(u v N)"``.