Precision in the padic module

A padic_t holds an integer $u$, a valuation $v$ and a precision $N$, and represents the class of $x = p^v u$ modulo $p^N$. The precision is a property of the variable, like the precision of an MPFR variable: it is chosen when the variable is initialised and stays fixed. Every function treats the stored values of its inputs as exact elements of $\mathbb{Z}[1/p] \subset \mathbf{Q}_p$, computes the exact result, and reduces it modulo $p^N$ for the precision $N$ of the output. The precisions of the inputs play no role.

A first program#

The program works in $\mathbf{Q}_7$. It stores $1/3$ and $12/49$ to precision 5, multiplies them into a variable of precision 3, inverts $1/3$ and converts back to a rational number.

#include <flint/flint.h>
#include <flint/fmpq.h>
#include <flint/padic.h>

int main(void)
{
    fmpz_t p;
    fmpq_t q;
    padic_ctx_t ctx;
    padic_t x, y, z;

    fmpz_init_set_ui(p, 7);
    padic_ctx_init(ctx, p, 0, 10, PADIC_SERIES);
    fmpq_init(q);

    padic_init2(x, 5);              /* x is stored modulo 7^5 */
    padic_init2(y, 5);
    padic_init2(z, 3);              /* z is stored modulo 7^3 */

    fmpq_set_si(q, 1, 3);
    padic_set_fmpq(x, q, ctx);      /* 1/3 mod 7^5 */
    flint_printf("x = "); padic_print(x, ctx); flint_printf("\n");

    fmpq_set_si(q, 12, 49);
    padic_set_fmpq(y, q, ctx);      /* 12/49 = 12 * 7^-2 */
    flint_printf("y = "); padic_print(y, ctx);
    flint_printf("   (u = "); fmpz_print(padic_unit(y));
    flint_printf(", v = %wd)\n", padic_val(y));

    padic_mul(z, x, y, ctx);        /* exact product, reduced mod 7^3 */
    flint_printf("x*y mod 7^3 = "); padic_print(z, ctx); flint_printf("\n");

    padic_inv(z, x, ctx);
    flint_printf("1/x mod 7^3 = "); padic_print(z, ctx); flint_printf("\n");

    ctx->mode = PADIC_TERSE;
    padic_get_fmpq(q, y, ctx);
    flint_printf("y as a rational: "); fmpq_print(q); flint_printf("\n");
    flint_printf("x in terse mode: "); padic_print(x, ctx); flint_printf("\n");

    padic_clear(x); padic_clear(y); padic_clear(z);
    fmpq_clear(q);
    padic_ctx_clear(ctx);
    fmpz_clear(p);
    return 0;
}

x = 5 + 4*7^1 + 4*7^2 + 4*7^3 + 4*7^4
y = 5*7^-2 + 1*7^-1   (u = 12, v = -2)
x*y mod 7^3 = 4*7^-2
1/x mod 7^3 = 3
y as a rational: 12/49
x in terse mode: 11205

The context stores the powers $p^0, \ldots, p^9$, which covers every reduction in this program; other powers would be computed on demand. The value of $y$ is exact, since $12/49 = 12 \cdot 7^{-2}$ terminates. In terse mode $x$ prints as the integer $11205 \equiv 1/3 \pmod{7^5}$, the representative actually stored, not as $1/3$.

Canonical and reduced form#

A value $p^v u$ is canonical if $p \nmid u$ or $u = v = 0$; the valuation of a nonzero canonical element is then $v$. It is reduced if in addition $0 < u < p^{N - v}$, so that it is the smallest nonnegative representative of its class modulo $p^N$. The functions of the module return reduced values and accept any canonical values. Code that writes the fields directly, through padic_unit, padic_val and padic_prec, must restore this with padic_reduce (or _padic_canonicalise and _padic_reduce).

Since the unit is reduced modulo $p^{N - v}$, the number of stored digits depends on the valuation: an element of valuation $-10$ in a variable of precision 5 stores 15 digits. Conversely, any element of valuation at least $N$ is stored as zero, and padic_one gives zero in a variable of precision $N \le 0$.

Precision is not tracked#

Because the inputs are treated as exact, the module never reports a loss of precision. If $x$ and $y$ agree modulo $p^{20}$ and are stored to precision 20, padic_sub returns $x - y$ reduced to the precision of the output, which may be 20 as well, although in a computation with genuine $p$-adic numbers only the class of $x - y$ modulo $p^{20}$ is known, and its leading digits are meaningless. In the same way an inverse $1/(p^v u)$ with $v > 0$ is only determined modulo $p^{N - 2v}$ by its input modulo $p^N$, but padic_inv returns it to the full precision of the output. The rules for how much precision each operation preserves are given in Precision and representation of p-adic numbers; following them is the responsibility of the caller. The module padic_radix.h does track error bounds and should be preferred when this matters.

A related consequence is that padic_equal compares stored values. Two variables of different precisions holding the same $p$-adic number compare equal only if their stored representatives coincide; reducing both to the smaller precision first gives the expected comparison.

Choosing the context#

The context stores a table of $p^e$ for $\mathtt{min} \le e < \mathtt{max}$. Almost every function reduces modulo $p^{N - v}$, and a power found in the table saves an exponentiation, so the table should cover the precisions in use, for example $\mathtt{min} = 0$ and $\mathtt{max}$ a little larger than the largest $N$. The printing mode is a field of the context that may be changed at any time, as in the program above. A context may be shared by any number of variables of different precisions, and is read-only after initialisation.