padic_radix.h

Initialises ctx for \mathbf{Q}_p with default relative precision prec_rel and absolute precision prec_abs, either of which may be PADIC_RADIX_PREC_INF, and the given combination of the flags below. Negative relative precisions are raised to 0, and finite precisions are clamped to \pmPADIC_RADIX_ERR_MAX. That p is prime is only checked in builds with assertions. Returns GR_SUCCESS. The context is a field in the sense of gr_ctx_is_field, and is exact if and only if both precisions are infinite.

Initialises ctx with a random prime and a random configuration for testing: absolute precision only, relative precision only, both (with precisions in [1, \mathtt{maxprec}]) or neither, and random flags PADIC_RADIX_SIGNED and PADIC_RADIX_TEST_LIMITS.

Implementations of gr_ctx_clear and gr_ctx_write; the description written has the form Radix 7-adic numbers (rel prec 10, abs prec inf).

Initialise to the exact zero, clear, swap in constant time, and copy the structure without copying the limbs.

Return the precision N of x (PADIC_RADIX_EXACT for an exact element), respectively whether x is exact.

Sets res to a random element with small valuation, exact or with a random error term (never with an error term in an exact context).

Writes x in the form (u) * p^v + O(p^N), omitting the power of p when v = 0 and the error term for exact elements, for example 188316833 + O(7^10). The unit is written by radix_get_str_sum, or as a decimal integer if the context has the flag PADIC_RADIX_DECIMAL. Strings of this form, including O(p^n), are accepted by gr_set_str.

Set res to the exact zero, respectively to one, which becomes 0 + O(p^{t}) if t = \min(a, r) is not positive for the context precisions a and r.

Sets res to x, truncated to the context precision.

Set res to the integer x, truncated to the context precision. A negative x in a context without PADIC_RADIX_SIGNED is stored as an inexact residue, or gives GR_UNABLE if the context precision is infinite.

Set res to the exact integer x, ignoring the context precision; the unit may be negative regardless of the flags.

Sets res to the value of x if x is an exact integer. Returns GR_DOMAIN if v < 0 and GR_UNABLE if x is inexact or its valuation exceeds the size limit of the context.

Set res to -x, x + y, x - y and xy. The error term of a sum is O(p^{\min(N_x, N_y)}) and that of a product O(p^{\min(N_x + v_y, N_y + v_x)}); the result is then truncated to the context precision. An exact zero factor gives an exact zero.

Set res to 1/x, respectively x/y. The relative precision of the result is the smaller relative precision of the operands, capped by the context. Exact operands give an exact result when the quotient terminates (for example 1/49 or 6/3). Return GR_DOMAIN when dividing by an exact zero, and GR_UNABLE when the divisor is not known to be nonzero or when the context is exact and the quotient has an infinite expansion.

Returns whether x is nonzero: T_TRUE if it is exact and nonzero or its leading digit is known, T_FALSE for an exact zero and T_UNKNOWN otherwise.

Set res to a square root \sqrt x, respectively 1/\sqrt x, with relative precision equal to that of x (one digit less for p = 2), capped by the context. The root is a fixed canonical branch, so that a result at lower precision is the truncation of the result at higher precision, and rsqrt gives the reciprocal of sqrt. An exact perfect square gives its exact root. Return GR_DOMAIN if x has odd valuation or its unit is not a square (and for rsqrt if x is an exact zero), and GR_UNABLE if x is not known to be nonzero, if p = 2 and the unit is known to fewer than 3 digits, or if the context is exact and the root is irrational. sqrt of an exact zero is zero.

Returns whether x is a square: decided by the valuation and the unit modulo p (modulo 8 for p = 2), and T_UNKNOWN for an inexact zero or, for p = 2, a unit known to fewer than 3 digits.

Ball predicates: T_TRUE only for exact elements with the property, T_FALSE if no value in the ball has it (for equality, if the balls are disjoint), and T_UNKNOWN otherwise.

Set res to s \pm \sum_{i < len} a_i b_i with a_i = vec1[i * stride1], b_i = vec2[i * stride2], s = initial (zero if initial is NULL) and the sign - if subtract is nonzero. The naive version calls padic_radix_mul and padic_radix_add in a loop. The delayed version finds the minimum valuation and the precision of the result first, then accumulates the limb products of all terms in three-word accumulators, grouped by the residue of the digit offset modulo e and by sign, and propagates carries, shifts and divisions by p^e once at the end. The default uses the naive version for len \le 7.

The contiguous dot product and the dot product with vec2 reversed, as wrappers of padic_radix_dot_strided. These implement the generic dot product methods, which gr_mat_mul and the gr_poly products use.

Returns the number n of terms after which the exponential series for an argument of valuation v can be truncated modulo p^N, n = \max(1, \lceil ((p-1)N - 1)/((p-1)v - 1) \rceil). Assumes that the series converges (v \ge 1, or v \ge 2 for p = 2).

Set rop to the nonnegative residue of \exp(u p^v) modulo p^N, for v \ge 1 (v \ge 2 if p = 2), not checked. The rectangular version uses rectangular splitting, the balanced version the p-adic bit-burst method with binary splitting. _padic_radix_exp uses the rectangular version for N below a cutoff between 80 and 200 that decreases with the size of p.

Set res to \exp(x), with precision \min(N_x, a, r) for the context precisions a and r (the result is a unit). Return GR_DOMAIN if the series diverges, and GR_UNABLE if convergence cannot be decided (an inexact zero of too low precision) or the context precision is infinite.

Returns the least b \ge 2 such that iv - \operatorname{ord}_p(i) \ge N for all i \ge b, so that the series for \log(1 - y) with \operatorname{ord}_p(y) = v can be truncated after b - 1 terms.

Set rop to the residue of \log(1 - y) modulo p^N for an integer y of valuation at least 1 (not checked). _padic_radix_log uses the rectangular version for N below a cutoff between 80 and 350 that decreases with the size of p.

Set res to \log(x), with absolute precision \min(N_x, a, r). Return GR_DOMAIN unless x \equiv 1 \pmod p (for every p, including p = 2), and GR_UNABLE if this cannot be decided or if x is exact and the context precision infinite.

Canonicalises a freshly computed element (moving factors of p from the unit to the valuation), enforces the representability bounds of PADIC_RADIX_ERR_MAX and truncates to the context precision. Returns GR_UNABLE if the valuation or precision cannot be represented.

Simple reference implementations of addition (x + y, or x - y if sub is nonzero) and multiplication, used to test the optimised functions.