gr.h

Returns ctx->sizeof_elem, the size in bytes of an element of ctx.

Returns sizeof(gr_ctx_struct), for interfaces that allocate context objects without access to the C type.

Return a pointer to the data field of ctx, respectively the pointer stored at the start of the data field (the value of GR_CTX_DATA_AS_PTR(ctx)), for rings whose parameters are kept in a separately allocated structure.

Kleene's three-valued conjunction, disjunction and negation: for example truth_and returns T_FALSE if either argument is T_FALSE and T_UNKNOWN if neither is T_FALSE and one is T_UNKNOWN.

Prints T_TRUE, T_FALSE or T_UNKNOWN followed by a newline.

Converts a status into the truth of "the result is defined": T_TRUE for GR_SUCCESS, T_FALSE when GR_DOMAIN is set and GR_UNABLE is not, and T_UNKNOWN otherwise.

Converts a truth value into a status: T_TRUE to GR_SUCCESS, T_FALSE to GR_DOMAIN and T_UNKNOWN to GR_UNABLE.

Clears the context object, freeing any memory it owns. All elements of the ring must be cleared before the context; a ring built on top of a base ring (for example a polynomial ring) must be cleared before its base ring.

Write a description of the ring, such as Integers mod 7 (_gr_nmod), to a stream, print it to standard output (with a newline for gr_ctx_println), or set *s to a newly allocated string that must be freed with flint_free. The format specifier %{gr_ctx} of flint_printf does the same (Formatted output).

Returns a pointer to the context of the base ring if ctx is constructed over one (polynomials, matrices, series, fractions, quotients); otherwise returns NULL.

Set the name of the generator, for rings with one generator (polynomial rings, finite fields, series), or the names of the generators of a multivariate ring. The names are used for printing and parsing. Return GR_UNABLE if the ring has no named generators.

Set *ngens to the number of generators (0 by default), respectively set *name to a newly allocated copy of the name of generator i, which must be freed with flint_free.

Sets ctx to a placeholder context that can be printed and cleared but supports no other operation; initialising an element throws an exception. Wrapper code uses it for a context whose constructor failed (for example gr_ctx_init_mpn_mod with an unsupported modulus), so that it can still be cleared.

Return whether the structure has the mathematical property. Rings with inexact elements answer for the ring they represent, so real balls form a field. Floating-point contexts are not rings and return T_FALSE for the ring properties.

Returns whether the structure \tilde R implemented by ctx is an approximate version of a commutative ring R: the axioms need only hold up to a small perturbation, |\tilde a - \tilde b| < \varepsilon in place of a = b. Polynomials with floating-point coefficients form an approximate commutative ring; 2 \times 2 matrices with floating-point entries do not. Every commutative ring is an approximate commutative ring.

Return whether every element is represented exactly (no balls, no truncated series, no rounding), respectively whether every element has a unique representation, so that equality can be decided by comparing representations.

Returns whether different threads may operate simultaneously on different elements of the ring with the same context; T_TRUE by default. Contexts that cache data without locking (for example gr_ctx_init_real_ca) return T_FALSE, and parallel generic algorithms then run serially.

Return whether ctx, or a base ring of it, approximates real or complex numbers with a working precision (ball arithmetic as well as floating-point), and set or get that precision in bits. The setters return GR_UNABLE for rings without a precision.

Declares whether the ring is a field. For \mathbb{Z}/n\mathbb{Z} this declares whether n is prime: gr_ctx_init_nmod tests primality when asked, while the contexts with large moduli (gr_ctx_init_fmpz_mod, gr_ctx_init_mpn_mod) report T_UNKNOWN until the user declares it, which enables algorithms for fields. For gr_ctx_init_gr_poly_quotient it declares that the modulus is irreducible. The declaration is not checked. Returns GR_UNABLE for rings that do not support it.

Let a ring that is not known to be a field compute as if it were one, in the style of dynamic evaluation [DDDD1985]. While the pretence is on, an inversion or division that meets a nonzero non-invertible element fails with GR_UNABLE (not GR_DOMAIN, which keeps its meaning of division by zero) and records that zero divisor in the context; gr_ctx_recover_zero_divisor sets res to the first recorded zero divisor, or returns GR_UNABLE if there is none.

Initialise res, which must point to ctx->sizeof_elem bytes of memory, to the zero element of the ring; respectively clear it, freeing any memory the element owns but not the memory it occupies.

Swaps x and y efficiently, without copying owned data.

Copies the bytes of x to res (by default with memcpy), so that both share any memory owned by x. res must not be initialised or cleared independently afterwards; this is for building temporary views.

Allocate one element on the heap with flint_malloc and initialise it to zero; clear and free an element allocated this way.

Allocate an array of len contiguous elements on the heap, initialised to zero; clear the len elements and free the array.

Sets res to a random element of the ring.

Sets res to a random element that is not zero. Returns GR_DOMAIN in the zero ring.

Sets res to a random invertible element. The default tries gr_randtest and gr_randtest_small a few times each and falls back to \pm 1.

Sets res to a small random element, for tests where large elements would make operations expensive. The default is a g + b for small integers a, b and the generator g (if any), sometimes divided by a small integer.

Initialise a stream writing to fp, respectively to a new string that the caller takes over as out->s and frees with flint_free. gr_stream_init_file is declared only if stdio.h was included before gr.h.

Write a string, an integer in decimal, or a string allocated with flint_malloc that is freed afterwards.

Write x to a stream, print it to standard output (with a newline for gr_println), or set *s to a newly allocated string that must be freed with flint_free.

As gr_write and gr_get_str, rounding real and complex numbers (also inside polynomials, matrices, ...) to n significant digits. Exact rings ignore n.

Sets res to the value of the expression x, parsed by gr_generic_set_str unless the ring overrides it. Expressions may use integer and decimal literals (2.5e-3, converted with gr_set_fmpz_10exp_fmpz), + - * / ^, parentheses, the generators of the ring and its base rings by name, the constants pi, i, inf and nan, functions such as sqrt, exp, log and gamma, ball notation m +/- r, and O(x^n) in series rings; see gr_generic_set_str_expr. Returns GR_UNABLE if the string cannot be parsed and propagates the status of the arithmetic (for example GR_DOMAIN for "1/2" in \mathbb{Z}).

Convert between elements and symbolic expressions (fexpr). The serialize version may produce an expression of the internal representation that is not meant to be read by humans, but that gr_set_fexpr converts back exactly. gr_set_fexpr evaluates the expression in the ring; inputs and outputs are a dictionary of symbols and their values (initially empty, also used as scratch space). These functions are declared only if fexpr.h was included before gr.h.

Sets res to a copy of x.

Set res to the image of the integer, rational or double x in the ring.

Sets res to the element x of another ring x_ctx converted to ctx.

Convert x to a C or FLINT type: an integer, a rational number, or a double (rounded).

Set res to the dyadic number a \cdot 2^b, respectively write a dyadic x as m \cdot 2^e with m odd (or m = e = 0).

Sets res to the decimal number a \cdot 10^b.

Writes a real x approximately as m 2^e with 0.5 \le |m| < 1 (or m = e = 0), which works when x is outside the range of a double.

Set res to 0, 1 or -1. gr_one fails with GR_DOMAIN in structures without a unit element (for example the domain of matrices of all shapes created by gr_ctx_init_matrix_domain).

Sets res to the generator of the ring: x in R[x] or R[[x]], the generator of the defining polynomial in a finite field or number field, the image of x in a quotient ring R[x]/(m). Returns GR_UNABLE for rings without a distinguished generator.

Set res to the vector of generators of the ring (empty by default), for example x_1, \ldots, x_n in a multivariate polynomial ring. The recursive version also includes the generators of the base rings, recursively, embedded in ctx: in (\mathbb{Z}[x])[y] it gives x, y. gr_set_str recognises the names of all these generators.

Return whether x is equal to 0, 1 or -1.

Return whether x and y are equal, respectively different, as mathematical elements of the ring; for inexact representations the answer is T_UNKNOWN unless it can be decided from the enclosures.

Sets res to -x.

Set res to x + y.

Set res to x - y.

Set res to x y.

Set res to \mathit{res} + x y, respectively \mathit{res} - x y. The default forms the product in a temporary; rings may fuse the operation, avoiding the temporary or an intermediate rounding. For sums of many products use the dot products of gr_vec (_gr_vec_dot), which rings optimise further.

Set res to 2x, respectively x^2; by default x + x and x \cdot x.

Set res to x \cdot 2^y. For negative y this divides by 2^{-y} (failing with GR_DOMAIN if the division is not possible), so it also works in rings where 2^y is not representable as an element but the quotient is.

Return whether x is a unit, respectively set res to x^{-1}, failing with GR_DOMAIN if x is not invertible.

Set res to the quotient q = x / y, the unique q with q y = x in the ring. Fail with GR_DOMAIN if there is no such q or it is not unique (for example 0/0, 1/2 in \mathbb{Z}, 3/2 in \mathbb{Z}/6\mathbb{Z}).

gr_div_nonunique sets res to some q with q y = x, failing with GR_DOMAIN only if no such q exists; gr_divides returns whether x \mid y, that is, whether y = q x for some q.

Set res to x / y assuming that the division is exact. The ring may skip the verification: if the division is not exact, the result may be meaningless even when GR_SUCCESS is returned.

Euclidean division x = q y + r with remainder, setting res (or res1) to q and res (or res2) to r; division by zero fails with GR_DOMAIN. The choice of quotient is defined by the ring: the floor quotient in \mathbb{Z} (as fmpz_fdiv_qr), a nearest quotient in \mathbb{Z}[i], polynomial division in F[x]. Rings without a Euclidean structure return GR_UNABLE (no default implementation).

Set res to x^y. Fail with GR_DOMAIN if the power has no value in the ring (for example 0^{-1}, 2^{-1} in \mathbb{Z}, (-1)^{1/2} in \mathbb{R}).

Sets res to the derivative of x with respect to the generator of index var of the ring (for polynomial and series rings).

Returns whether x is a square in the ring.

Set res to a square root \sqrt{x}, respectively 1/\sqrt{x}. Fail with GR_DOMAIN if x is not a square (and for gr_rsqrt if x = 0) and with GR_UNABLE if this cannot be decided, for example for a real ball containing zero.

Set res to a greatest common divisor, respectively least common multiple, of x and y. These are unique only up to units; the ring chooses a representative, typically the canonical associate (nonnegative in \mathbb{Z}, monic in F[x], 1 or 0 in a field).

Sets res1 to a canonical representative u x of the class of x under multiplication by units and res2 to the unit u. For x = 0 sets res1 to 0 and res2 to 1. Fraction fields use it to normalise denominators.

Computes a factorisation x = c f_1^{e_1} \cdots f_n^{e_n} into distinct irreducible (or prime) factors f_k with positive exponents. factors and exponents are resized to length n.

Set res to a numerator p, respectively a denominator q, with x = p / q, both in the same ring as x. Fraction fields return the reduced numerator and the canonical denominator; the default is p = x and q = 1.

Set res to the integer obtained by rounding x towards -\infty, +\infty, zero, or to the nearest integer with ties to even. For complex balls (acb) the real part is rounded and the result is real.

Sets res to the absolute value of x, in an ordered ring or a subring of \mathbb{C}.

Sets res to the imaginary unit i; GR_DOMAIN in real rings.

Set res to the complex conjugate, the real part, the imaginary part, the sign x / |x| (0 for x = 0), the real-valued sign used for branch cuts (csgn: the sign of \operatorname{Re}(x), or of \operatorname{Im}(x) when the real part is zero), and the argument in (-\pi, \pi].

Set res to +\infty, -\infty, the unsigned infinity \tilde \infty, the value Undefined or the value Unknown. Only extended structures such as gr_ctx_init_complex_extended_ca and the floating-point contexts have such elements; other rings return GR_DOMAIN or GR_UNABLE.

Set *res to -1, 0 or 1 according to whether x < y, x = y or x > y. Fail with GR_DOMAIN if the ring is not ordered and with GR_UNABLE if the comparison cannot be decided (overlapping balls).

As gr_cmp, comparing the absolute values |x| and |y|; this is defined also for complex numbers.

Return the truth of x \le y, x < y, x \ge y, x > y and of the same relations between |x| and |y|. They call gr_cmp or gr_cmpabs and return T_UNKNOWN if it fails.

Set res to the minimum or maximum of x and y. Ball arithmetic returns a ball enclosing the minimum or maximum of all points in the input balls.

In ball representations of real numbers, sets res to the ball m \pm r.

Sets res to m \pm \infty, the whole real line for a real ball. In vector spaces over the reals the infinite radius is a real constant, so only the real part of a complex number, or the constant coefficient of a polynomial, gets an infinite radius, as with gr_set_interval_mid_rad.

Sets m and r to the midpoint and radius of x as exact elements of the ring, so that gr_set_interval_mid_rad with m and r reproduces x; radii of vector spaces are split as in the setter. The default, used by exact rings, sets m = x and r = 0.

Sets res to the error term O(x^n), where x is the generator of a power series ring or the base p of a p-adic ring. Returns GR_UNABLE in rings that cannot represent such a term (for example an exact polynomial ring).

Set the characteristic p, the degree d over the prime field and the order q = p^d of the finite field \mathbb{F}_q.

Sets res to x^{p^e}, the image of x under the e-th power of the Frobenius automorphism.

Set res to the multiplicative order of x (GR_DOMAIN for x = 0), respectively return whether x generates the multiplicative group \mathbb{F}_q^\times.

Set res to the norm or the trace of x over the prime field, as an integer in [0, p).

Sets res to the unique p-th root of x.

Constructs a ring of transformed polynomials over base admitting lengths up to len_bound and up to terms_bound accumulated elementary products per element, for the estimated workload (which may be NULL, though implementations then usually judge the switch unprofitable). Returns GR_UNABLE if the base ring provides no transformed representation (the method GR_METHOD_CTX_INIT_TRANSFORMED_POLY_REPR, implemented for nmod and mpn_mod base rings) or judges the switch unprofitable.

Constructs a ring of transformed polynomials modulo x^L - 1 over base, in which products wrap around. The implementation may round the requested cyclic length *len up (for example to a power of two) and writes the actual L back. Conversions in require length at most L; conversions out give the coefficients of the reduced representative. This is the CTX_INIT_TRANSFORMED_POLY_CYCLIC_REPR method of the base ring (GR_UNABLE by default); it is used for middle products and for products whose high part is known, such as the remainder step of division by a precomputed modulus.

The implementations of the two constructors for nmod base rings, installed in their method table, and the destructive windowed conversion of the resulting ring, which writes the coefficients [z_l, z_h) of x to cc and consumes x.

Constructs the ring of transformed big integers: bilinear expressions over \mathbb{Z} whose value is below 2^{\mathit{bits\_bound}} in absolute value, with at most terms_bound accumulated elementary products and multiplicative depth two. Elements carry a sign bit when is_signed is nonzero; mixed-sign accumulations switch the pointwise additions and subtractions, and the sign of a mixed result is resolved at conversion out.

As gr_ctx_init_transformed_mpn, for products of which only the limbs [\mathit{lo}, \mathit{hi}) are wanted. The plan is the window plan of fft_small_plan_init_mpn_window: when the window allows it, the transforms are cyclic of a length shorter than the products, and a product whose slots then alias can be converted only through gr_transformed_mpn_get_window with a window inside [\mathit{lo}, \mathit{hi}); the other conversions of such a product return GR_UNABLE. Elements that do not alias (operands, and products short enough) convert as usual.

Switches a context created with GR_TRANSFORMED_MPN_ALLOC_MALLOC to the reserved-slab strategy for num_live simultaneously live elements, as if it had been created that way. This serves callers whose live count depends on quantities derived from the constructed context, such as a blocking decision based on the element size. Returns GR_UNABLE, leaving separate allocation in place, if the reservation cannot be made.

Conversions by limb arrays with an explicit sign. gr_transformed_mpn_set converts the integer \pm(a_0, \ldots, a_{an-1}) in, failing with GR_DOMAIN if it does not fit the context. The get functions write the absolute value to z, its length to *zn_out and the sign to *sign; the destructive form may consume the element, skipping a copy of the transform. gr_transformed_mpn_get_limbs returns the number of limbs the reconstruction of x needs, which exceeds the length of the value by the length of the top CRT coefficient, and gr_transformed_mpn_get_limbs_bound an upper bound over every element of the context.

Truncated conversion out: the limbs of the value starting at limb lo, with an error against the exact value within (-1.5, +0.5) units of the lowest returned limb, equivalently at most 1 from the floor of the truncated value. The export includes every CRT slot whose coefficient span can reach the first returned limb, with carries propagated, so the error is the truncation itself (one-sided, below one unit) plus the total of the wholly dropped slots (under half a unit either way). gr_transformed_mpn_get_limbs_trunc returns the number of limbs needed.

Residue conversion out: z receives the value modulo 2^{\mathtt{FLINT\_BITS} \cdot \mathit{zn}} as a two's-complement residue of exactly zn limbs, with no sign, whatever the size of the value. Only the CRT slots starting below limb zn are reconstructed, so this costs a fraction of a full conversion when zn is a fraction of the length of the value.

Window conversion out, for signed contexts: z receives the limbs [\mathit{lo}, \mathit{lo} + \mathit{zn}) of the value as a two's-complement window, within one unit of \lfloor x / B^{lo} \rfloor (two when the element carries a small side value, which is folded in exactly only for \mathit{lo} = 0) and exact for \mathit{lo} = 0; the value need not fit. The sign is applied in transform space, so the window is that of the signed value. This is the conversion for windowed contexts with cyclic plans. Returns GR_UNABLE for unsigned contexts.

Converts x into f, consuming it. The width the reconstruction needs is taken from the element and f is grown to match, so the conversion writes straight into the limbs of f, with neither staging nor a copy. A nonzero lo_limbs selects the truncated conversion, with the error described for gr_transformed_mpn_get_trunc. This is the conversion to use whenever the destination is an fmpz.

Returns the size in bytes of the transform storage of one element. A context with reserved slabs occupies num_live times this, plus the conversion staging region when it is not taken from a slab.

Initialises the method table methods: every entry is first set to gr_not_implemented, then the defaults of gr_generic are installed, and finally the entries listed in tab overwrite them. The table is built in a temporary and copied at the end, so that concurrent initialisation of the same table by several threads is harmless.

Overwrites the entries listed in tab in an initialised table, for rings that share most methods with another table.

Do nothing and return GR_UNABLE, respectively GR_DOMAIN. The first fills the entries of methods without an implementation; the second can be installed for an operation that never makes sense in the ring, such as the constant \pi in \mathbb{Q}.

Context predicates that return T_UNKNOWN, T_TRUE and T_FALSE, for filling the GR_METHOD_CTX_IS_* entries of a method table.

Tests the ring R, running each test iters times (vector tests iters / 10 + 1 times): conversions and printing, the ring axioms (associativity, commutativity if gr_ctx_is_commutative_ring is T_TRUE, distributivity), aliasing of the arithmetic functions, consistency of the type variants (_ui, _si, _fmpz, _fmpq, _other), division, inversion and exact division, powering, square roots, ordering, GCD, LCM and factorisation when the ring is a unique factorisation domain, vector operations, dot products and classical matrix multiplication. Throws an exception on the first failure.

Tests R as a multiplicative group: gr_one, associativity and aliasing of gr_mul, commutativity if the group is commutative, division, inversion and powering.

Tests a floating-point context, for which the ring axioms hold only approximately: initialisation, printing and parsing, commutativity of addition, aliasing of the arithmetic functions, vector operations and conversions.

Compares the comparison function op (such as gr_cmp) on random elements of R with the same function on the elements converted to the reference ring R_ref.

Tests for approximate (floating-point) rings: compute an operation, its type variants, or a dot product of length at most maxlen in R and in a more precise reference ring R_ref (for example balls), and check that the relative error is at most rel_tol, an element of R_ref. For the type variants, fused selects the addmul-type signature and small_test_values restricts the scalar operands to small values. These functions abort on failure.

Tests gr_factor on a small random element, sometimes a product of two: the lengths of factors and exponents agree and c \prod f_k^{e_k} equals the input. GR_DOMAIN is accepted only for the input zero.

Single tests of gr_pow_ui and gr_pow_fmpz: x^{a+b} = x^a x^b, (c x)^a = c^a x^a for an integer c, (xy)^a = x^a y^a (for commutative rings), and aliasing of input and output. They return GR_TEST_FAIL on failure and otherwise the status of the operations.

Returns the working precision of ctx, or 0 if it has none.

Calls the internal _GR_METHOD_LENGTH method of the ring (a size measure of x, 0 by default) and discards the result.

Lock and unlock the global mutex that serialises the recording of zero divisors by rings pretending to be fields (no-ops in builds without threads).