gr.h – generic structures and their elements

Introduction

Parents and elements

To work with an element \(x \in R\) of a particular mathematical structure R, we use a context object to represent R (the “parent” of \(x\)). Elements are passed around as pointers. Note:

• Parents are not stored as part of the elements; the user must track the context objects for all variables.

• Operations are strictly type-stable: elements only change parent when performing an explicit conversion.

The structure R will typically be a ring, but the framework supports general objects (including groups, monoids, and sets without any particular structure whatsoever). We use these terms in a strict mathematical sense: a “ring” must exactly satisfy the ring axioms. It can have inexact representations, but this inexactness must be handled rigorously.

To give an idea of how the interface works, this example program computes \(3^{100}\) in the ring of integers and prints the value:

#include "gr.h"

int main()
{
    int status;
    gr_ctx_t ZZ:             /* a parent (context object) */
    gr_ptr x;                /* an element */

    gr_ctx_init_fmpz(ZZ);    /* ZZ = ring of integers with fmpz_t elements */
    GR_TMP_INIT(x, ctx)      /* allocate element on the stack */

    status = gr_set_ui(x, 3, ctx);           /* x = 3 */
    status |= gr_pow_ui(x, x, 100, ctx);     /* x = x ^ 100 */
    status |= gr_println(x, ctx);

    GR_TMP_CLEAR(x, ctx)
    gr_ctx_clear(ZZ);

    return status;
}

Parent and element types

type gr_ptr

Pointer to a ring element or array of contiguous ring elements. This is an alias for void * so that it can be used with any C type.

type gr_srcptr

Pointer to a read-only ring element or read-only array of contiguous ring elements. This is an alias for const void * so that it can be used with any C type.

type gr_ctx_struct

type gr_ctx_t

A context object representing a mathematical structure R. It contains the following data:

• The size (number of bytes) of each element.

• A pointer to a method table.

• Optionally a pointer to data defining parameters of the ring (e.g. modulus of a residue ring; element ring and dimensions of a matrix ring; precision of an inexact ring).

A gr_ctx_t is defined as an array of length one of type gr_ctx_struct, permitting a gr_ctx_t to be passed by reference. Context objects are not normally passed as const in order to allow storing mutable caches, additional debugging information, etc.

type gr_ctx_ptr

Pointer to a context object.

There is no type to represent a single generic element as a struct since we do not know the size of a generic element at compile time. Memory for single elements can either be allocated on the stack with the special macros provided below, or as usual with malloc. Methods can also be used with particular C types like fmpz_t when the user knows the type. Users may wish to define their own union types when only some particular types will appear in an application.

Error handling

To compute over a structure \(R\), it is useful to conceptually extend to a larger set \(R' = R \cup \{ \text{undefined}, \text{unknown} \}\).

• Adding an undefined (error) value allows us to extend partial functions to total functions.

• An unknown value is useful in cases where a result may exist in principle but cannot be computed.

An alternative to having an undefined value is to choose some arbitrary default value in \(R\), say \(\text{undefined} = 0\) in a ring. This is often done in proof assistants, but in a regular programming environment, we typically want some way to detect domain errors.

Representing \(R'\) as a type-level extension of \(R\) is tricky in C since we would either have to wrap elements in a larger structure or reserve bit patterns in each type for special values. In any case, it is useful to assume in low-level code that elements really represent elements of the intended structure so that there are fewer special cases to handle. We also need some form of error handling for conversions to standard C types. For these reasons, we handle special values (undefined, unknown) using return codes.

Functions can return a combination of the following status flags:

GR_SUCCESS

The operation finished as expected, i.e. the result is a correct element of the target type.

GR_DOMAIN

The result does not have a value in the domain of the target ring or type, i.e. the result is mathematically undefined. This occurs, for example, on division by zero or when attempting to compute the square root of a non-square. It also occurs when attempting to convert a too large value to a bounded type (example: get_ui() with input \(n \ge 2^{64}\)).

GR_UNABLE

The operation could not be performed because of limitations of the implementation or the data representation, i.e. the result is unknown. Typical reasons:

• The result would be too large to fit in memory

• The inputs are inexact and an exact comparison is needed

• The computation would take too long

• An algorithm is not yet implemented for this case

If this flag is set, there is also potentially a domain error (but this is unknown).

GR_TEST_FAIL

Test failure. This is only used in test code.

When the status code is any other value than GR_SUCCESS, any output variables may be set to meaningless values.

C functions that return a status code are marked with the WARN_UNUSED_RESULT attribute. This allows compilers to emit warnings when the status code is ignored.

Flags can be OR’ed and checked only at the top level of a computation to avoid complex control flow:

status = GR_SUCCESS;
gr |= gr_add(res, a, b, ctx);
gr |= gr_pow_ui(res, res, 2, ctx);
...

If we do not care about recovering from undefined/unknown results, the following macro is useful:

GR_MUST_SUCCEED(expr)

Evaluates expr and asserts that the return value is GR_SUCCESS. On failure, calls flint_abort().

For uniformity, most operations return a status code, even operations that are not typically expected to fail. Exceptions include the following:

• Pure “container” operations like init, clear and swap do not return a status code.

• Pure predicate functions (see below) return T_TRUE / T_FALSE / T_UNKNOWN instead of computing a separate boolean value and error code.

Predicates

We use the following type (borrowed from Calcium) instead of a C int to represent boolean results, allowing the possibility that the value is not computable:

enum truth_t

Represents one of the following truth values:

T_TRUE

T_FALSE

T_UNKNOWN

Warning: the constants T_TRUE and T_FALSE do not correspond to 1 and 0. It is erroneous to write, for example !t if t is a truth_t. One should instead write t != T_TRUE, t == T_FALSE, etc. depending on whether the unknown case should be included or excluded.

Context operations

slong gr_ctx_sizeof_elem(gr_ctx_t ctx)

Return sizeof(type) where type is the underlying C type for elements of ctx.

int gr_ctx_clear(gr_ctx_t ctx)

Clears the context object ctx, freeing any memory allocated by this object.

Some context objects may require that no elements are cleared after calling this method, and may leak memory if not all elements have been cleared when calling this method.

If ctx is derived from a base ring, the base ring context may also be required to stay alive until after this method is called.

int gr_ctx_write(gr_stream_t out, gr_ctx_t ctx)

int gr_ctx_print(gr_ctx_t ctx)

int gr_ctx_println(gr_ctx_t ctx)

int gr_ctx_get_str(char **s, gr_ctx_t ctx)

Writes a description of the structure ctx to the stream out, prints it to stdout, or sets s to a pointer to a heap-allocated string of the description (the user must free the string with flint_free). The println version prints a trailing newline.

Element operations

Memory management

void gr_init(gr_ptr res, gr_ctx_t ctx)

Initializes res to a valid variable and sets it to the zero element of the ring ctx.

void gr_clear(gr_ptr res, gr_ctx_t ctx)

Clears res, freeing any memory allocated by this object.

void gr_swap(gr_ptr x, gr_ptr y, gr_ctx_t ctx)

Swaps x and y efficiently.

void gr_set_shallow(gr_ptr res, gr_ptr x, gr_ctx_t ctx)

Sets res to a shallow copy of x, copying the struct data.

gr_ptr gr_heap_init(gr_ctx_t ctx)

Return a pointer to a single new heap-allocated element of ctx set to 0.

void gr_heap_clear(gr_ptr x, gr_ctx_t ctx)

Free the single heap-allocated element x of ctx which should have been created with gr_heap_init().

The following macros support allocating temporary variables efficiently. Data will be allocated on the stack using alloca unless the size is excessive (risking stack overflow), in which case the implementation transparently switches to malloc/free instead. The usage pattern is as follows:

{
    gr_ptr x, y;
    GR_TMP_INIT2(x1, x2, ctx);

    /* do computations with x1, x2 */

    GR_TMP_CLEAR2(x1, x2, ctx);
}

Init and clear macros must match exactly, as variables may be allocated contiguously in a block.

Warning: never use these macros directly inside a loop. This is likely to overflow the stack, as memory will not be reclaimed until the function exits. Instead, allocate the needed space before entering any loops, move the loop body to a separate function, or allocate the memory on the heap if needed.

GR_TMP_INIT_VEC(vec, len, ctx)

GR_TMP_CLEAR_VEC(vec, len, ctx)

Allocates and frees a vector of len contiguous elements, all initialized to the value 0, assigning the first element to the pointer vec.

GR_TMP_INIT(x1, ctx)

GR_TMP_INIT2(x1, x2, ctx)

GR_TMP_INIT3(x1, x2, x3, ctx)

GR_TMP_INIT4(x1, x2, x3, x4, ctx)

GR_TMP_INIT5(x1, x2, x3, x4, x5, ctx)

Allocates one or several temporary elements, all initialized to the value 0, assigning the elements to the pointers x1, x2, etc.

GR_TMP_CLEAR(x1, ctx)

GR_TMP_CLEAR2(x1, x2, ctx)

GR_TMP_CLEAR3(x1, x2, x3, ctx)

GR_TMP_CLEAR4(x1, x2, x3, x4, ctx)

GR_TMP_CLEAR5(x1, x2, x3, x4, x5, ctx)

Corresponding macros to clear temporary variables.

Random elements

int gr_randtest(gr_ptr res, flint_rand_t state, gr_ctx_t ctx)

Sets res to a random element of the domain ctx. The distribution is determined by the implementation. Typically the distribution is non-uniform in order to find corner cases more easily in test code.

int gr_randtest_not_zero(gr_ptr res, flint_rand_t state, gr_ctx_t ctx)

Sets res to a random nonzero element of the domain ctx. This operation will fail and return GR_DOMAIN in the zero ring.

Input, output and string conversion

int gr_write(gr_stream_t out, gr_srcptr x, gr_ctx_t ctx)

int gr_print(gr_srcptr x, gr_ctx_t ctx)

int gr_println(gr_srcptr x, gr_ctx_t ctx)

int gr_get_str(char **s, gr_srcptr x, gr_ctx_t ctx)

Writes a description of the element x to the stream out, or prints it to stdout, or sets s to a pointer to a heap-allocated string of the description (the user must free the string with flint_free). The println version prints a trailing newline.

int gr_set_str(gr_ptr res, const char *x, gr_ctx_t ctx)

Sets res to the string description in x.

Assignment and conversions

int gr_zero(gr_ptr res, gr_ctx_t ctx)

int gr_one(gr_ptr res, gr_ctx_t ctx)

int gr_neg_one(gr_ptr res, gr_ctx_t ctx)

Sets res to the ring element 0, 1 or -1.

int gr_set(gr_ptr res, gr_srcptr x, gr_ctx_t ctx)

Sets res to a copy of the element x.

int gr_set_other(gr_ptr res, gr_srcptr x, gr_ctx_t x_ctx, gr_ctx_t ctx)

Sets res to the element x of the structure x_ctx which may be different from ctx. This returns the GR_DOMAIN flag if x is not an element of ctx or cannot be converted unambiguously to ctx. The GR_UNABLE flag is returned if the conversion is not implemented.

int gr_set_ui(gr_ptr res, ulong x, gr_ctx_t ctx)

int gr_set_si(gr_ptr res, slong x, gr_ctx_t ctx)

int gr_set_fmpz(gr_ptr res, const fmpz_t x, gr_ctx_t ctx)

int gr_set_fmpq(gr_ptr res, const fmpq_t x, gr_ctx_t ctx)

int gr_set_d(gr_ptr res, double x, gr_ctx_t ctx)

Sets res to the value x. If no reasonable conversion to the domain ctx is possible, returns GR_DOMAIN.

int gr_get_si(slong *res, gr_srcptr x, gr_ctx_t ctx)

int gr_get_ui(ulong *res, gr_srcptr x, gr_ctx_t ctx)

int gr_get_fmpz(fmpz_t res, gr_srcptr x, gr_ctx_t ctx)

int gr_get_fmpq(fmpq_t res, gr_srcptr x, gr_ctx_t ctx)

int gr_get_d(double *res, gr_srcptr x, gr_ctx_t ctx)

Sets res to the value x. This returns the GR_DOMAIN flag if x cannot be converted to the target type. For floating-point output types, the output may be rounded.

int gr_set_fmpz_2exp_fmpz(gr_ptr res, const fmpz_t x, const fmpz_t y, gr_ctx_t ctx)

int gr_get_fmpz_2exp_fmpz(fmpz_t res1, fmpz_t res2, gr_srcptr x, gr_ctx_t ctx)

Set or retrieve a dyadic number.

Basic properties

truth_t gr_is_zero(gr_srcptr x, gr_ctx_t ctx)

truth_t gr_is_one(gr_srcptr x, gr_ctx_t ctx)

truth_t gr_is_neg_one(gr_srcptr x, gr_ctx_t ctx)

Returns whether x is equal to the ring element 0, 1 or -1, respectively.

truth_t gr_equal(gr_srcptr x, gr_srcptr y, gr_ctx_t ctx)

Returns whether the elements x and y are equal.

truth_t gr_is_integer(gr_srcptr x, gr_ctx_t ctx)

Returns whether x represents an integer.

truth_t gr_is_rational(gr_srcptr x, gr_ctx_t ctx)

Returns whether x represents a rational number.

Arithmetic

User-defined rings should supply neg, add, sub and mul methods; the variants with other operand types have generic fallbacks that may be overridden for performance. The fmpq versions may return GR_DOMAIN if the denominator is not invertible. The other versions accept operands belonging to a different domain, attempting to perform a coercion into the target domain.

int gr_neg(gr_ptr res, gr_srcptr x, gr_ctx_t ctx)

Sets res to \(-x\).

int gr_add(gr_ptr res, gr_srcptr x, gr_srcptr y, gr_ctx_t ctx)

int gr_add_ui(gr_ptr res, gr_srcptr x, ulong y, gr_ctx_t ctx)

int gr_add_si(gr_ptr res, gr_srcptr x, slong y, gr_ctx_t ctx)

int gr_add_fmpz(gr_ptr res, gr_srcptr x, const fmpz_t y, gr_ctx_t ctx)

int gr_add_fmpq(gr_ptr res, gr_srcptr x, const fmpq_t y, gr_ctx_t ctx)

int gr_add_other(gr_ptr res, gr_srcptr x, gr_srcptr y, gr_ctx_t y_ctx, gr_ctx_t ctx)

int gr_other_add(gr_ptr res, gr_srcptr x, gr_ctx_t x_ctx, gr_srcptr y, gr_ctx_t ctx)

Sets res to \(x + y\).

int gr_sub(gr_ptr res, gr_srcptr x, gr_srcptr y, gr_ctx_t ctx)

int gr_sub_ui(gr_ptr res, gr_srcptr x, ulong y, gr_ctx_t ctx)

int gr_sub_si(gr_ptr res, gr_srcptr x, slong y, gr_ctx_t ctx)

int gr_sub_fmpz(gr_ptr res, gr_srcptr x, const fmpz_t y, gr_ctx_t ctx)

int gr_sub_fmpq(gr_ptr res, gr_srcptr x, const fmpq_t y, gr_ctx_t ctx)

int gr_sub_other(gr_ptr res, gr_srcptr x, gr_srcptr y, gr_ctx_t y_ctx, gr_ctx_t ctx)

int gr_other_sub(gr_ptr res, gr_srcptr x, gr_ctx_t x_ctx, gr_srcptr y, gr_ctx_t ctx)

Sets res to \(x - y\).

int gr_mul(gr_ptr res, gr_srcptr x, gr_srcptr y, gr_ctx_t ctx)

int gr_mul_ui(gr_ptr res, gr_srcptr x, ulong y, gr_ctx_t ctx)

int gr_mul_si(gr_ptr res, gr_srcptr x, slong y, gr_ctx_t ctx)

int gr_mul_fmpz(gr_ptr res, gr_srcptr x, const fmpz_t y, gr_ctx_t ctx)

int gr_mul_fmpq(gr_ptr res, gr_srcptr x, const fmpq_t y, gr_ctx_t ctx)

int gr_mul_other(gr_ptr res, gr_srcptr x, gr_srcptr y, gr_ctx_t y_ctx, gr_ctx_t ctx)

int gr_other_mul(gr_ptr res, gr_srcptr x, gr_ctx_t x_ctx, gr_srcptr y, gr_ctx_t ctx)

Sets res to \(x \cdot y\).

int gr_addmul(gr_ptr res, gr_srcptr x, gr_srcptr y, gr_ctx_t ctx)

int gr_addmul_ui(gr_ptr res, gr_srcptr x, ulong y, gr_ctx_t ctx)

int gr_addmul_si(gr_ptr res, gr_srcptr x, slong y, gr_ctx_t ctx)

int gr_addmul_fmpz(gr_ptr res, gr_srcptr x, const fmpz_t y, gr_ctx_t ctx)

int gr_addmul_fmpq(gr_ptr res, gr_srcptr x, const fmpq_t y, gr_ctx_t ctx)

int gr_addmul_other(gr_ptr res, gr_srcptr x, gr_srcptr y, gr_ctx_t y_ctx, gr_ctx_t ctx)

Sets res to \(\mathrm{res } + x \cdot y\). Rings may override the default implementation to perform this operation in one step without allocating a temporary variable, without intermediate rounding, etc.

int gr_submul(gr_ptr res, gr_srcptr x, gr_srcptr y, gr_ctx_t ctx)

int gr_submul_ui(gr_ptr res, gr_srcptr x, ulong y, gr_ctx_t ctx)

int gr_submul_si(gr_ptr res, gr_srcptr x, slong y, gr_ctx_t ctx)

int gr_submul_fmpz(gr_ptr res, gr_srcptr x, const fmpz_t y, gr_ctx_t ctx)

int gr_submul_fmpq(gr_ptr res, gr_srcptr x, const fmpq_t y, gr_ctx_t ctx)

int gr_submul_other(gr_ptr res, gr_srcptr x, gr_srcptr y, gr_ctx_t y_ctx, gr_ctx_t ctx)

Sets res to \(\mathrm{res } - x \cdot y\). Rings may override the default implementation to perform this operation in one step without allocating a temporary variable, without intermediate rounding, etc.

int gr_mul_two(gr_ptr res, gr_srcptr x, gr_ctx_t ctx)

Sets res to \(2x\). The default implementation adds x to itself.

int gr_sqr(gr_ptr res, gr_srcptr x, gr_ctx_t ctx)

Sets res to \(x ^ 2\). The default implementation multiplies x with itself.

int gr_mul_2exp_si(gr_ptr res, gr_srcptr x, slong y, gr_ctx_t ctx)

int gr_mul_2exp_fmpz(gr_ptr res, gr_srcptr x, const fmpz_t y, gr_ctx_t ctx)

Sets res to \(x \cdot 2^y\). This may perform \(x \cdot 2^{-y}\) when y is negative, allowing exact division by powers of two even if \(2^{y}\) is not representable.

Iterated arithmetic operations are best performed using vector functions. See in particular _gr_vec_dot() and _gr_vec_dot_rev().

int _gr_fmpz_poly_evaluate_horner(gr_ptr res, const fmpz *f, slong len, gr_srcptr x, gr_ctx_t ctx)

int gr_fmpz_poly_evaluate_horner(gr_ptr res, const fmpz_poly_t f, gr_srcptr x, gr_ctx_t ctx)

int _gr_fmpz_poly_evaluate_rectangular(gr_ptr res, const fmpz *f, slong len, gr_srcptr x, gr_ctx_t ctx)

int gr_fmpz_poly_evaluate_rectangular(gr_ptr res, const fmpz_poly_t f, gr_srcptr x, gr_ctx_t ctx)

int _gr_fmpz_poly_evaluate(gr_ptr res, const fmpz *f, slong len, gr_srcptr x, gr_ctx_t ctx)

int gr_fmpz_poly_evaluate(gr_ptr res, const fmpz_poly_t f, gr_srcptr x, gr_ctx_t ctx)

Sets res to the value of the integer polynomial f evaluated at the argument x.

int gr_fmpz_mpoly_evaluate(gr_ptr res, const fmpz_mpoly_t f, gr_srcptr x, const fmpz_mpoly_ctx_t mctx, gr_ctx_t ctx)

Sets res to value of the multivariate polynomial f (with corresponding context object mctx) evaluated at the vector of arguments in x.

Division

The default implementations of the following methods check for divisors 0, 1, -1 and otherwise return GR_UNABLE. Particular rings should override the methods when an inversion or division algorithm is available.

int gr_div(gr_ptr res, gr_srcptr x, gr_srcptr y, gr_ctx_t ctx)

int gr_div_ui(gr_ptr res, gr_srcptr x, ulong y, gr_ctx_t ctx)

int gr_div_si(gr_ptr res, gr_srcptr x, slong y, gr_ctx_t ctx)

int gr_div_fmpz(gr_ptr res, gr_srcptr x, const fmpz_t y, gr_ctx_t ctx)

int gr_div_fmpq(gr_ptr res, gr_srcptr x, const fmpq_t y, gr_ctx_t ctx)

int gr_div_other(gr_ptr res, gr_srcptr x, gr_srcptr y, gr_ctx_t y_ctx, gr_ctx_t ctx)

int gr_other_div(gr_ptr res, gr_srcptr x, gr_ctx_t x_ctx, gr_srcptr y, gr_ctx_t ctx)

Sets res to the quotient \(x / y\) if such an element exists in the present ring. Returns the flag GR_DOMAIN if no such quotient exists. Returns the flag GR_UNABLE if the implementation is unable to perform the computation.

When the ring is not a field, the definition of division may vary depending on the ring. A ring implementation may define \(x / y = x y^{-1}\) and return GR_DOMAIN when \(y^{-1}\) does not exist; alternatively, it may attempt to solve the equation \(q y = x\) (which, for example, gives the usual exact division in \(\mathbb{Z}\)).

truth_t gr_is_invertible(gr_srcptr x, gr_ctx_t ctx)

Returns whether x has a multiplicative inverse in the present ring, i.e. whether x is a unit.

int gr_inv(gr_ptr res, gr_srcptr x, gr_ctx_t ctx)

Sets res to the multiplicative inverse of x in the present ring, if such an element exists. Returns the flag GR_DOMAIN if x is not invertible, or GR_UNABLE if the implementation is unable to perform the computation.

truth_t gr_divides(gr_srcptr x, gr_srcptr y, gr_ctx_t ctx)

Returns whether x divides y.

int gr_divexact(gr_ptr res, gr_srcptr x, gr_srcptr y, gr_ctx_t ctx)

int gr_divexact_ui(gr_ptr res, gr_srcptr x, ulong y, gr_ctx_t ctx)

int gr_divexact_si(gr_ptr res, gr_srcptr x, slong y, gr_ctx_t ctx)

int gr_divexact_fmpz(gr_ptr res, gr_srcptr x, const fmpz_t y, gr_ctx_t ctx)

int gr_divexact_other(gr_ptr res, gr_srcptr x, gr_srcptr y, gr_ctx_t y_ctx, gr_ctx_t ctx)

int gr_other_divexact(gr_ptr res, gr_srcptr x, gr_ctx_t x_ctx, gr_srcptr y, gr_ctx_t ctx)

Sets res to the quotient \(x / y\), assuming that this quotient is exact in the present ring. Rings may optimize this operation by not verifying that the division is possible. If the division is not actually exact, the implementation may set res to a nonsense value and still return the GR_SUCCESS flag.

int gr_euclidean_div(gr_ptr res, gr_srcptr x, gr_srcptr y, gr_ctx_t ctx)

int gr_euclidean_rem(gr_ptr res, gr_srcptr x, gr_srcptr y, gr_ctx_t ctx)

int gr_euclidean_divrem(gr_ptr res1, gr_ptr res2, gr_srcptr x, gr_srcptr y, gr_ctx_t ctx)

In a Euclidean ring, these functions perform some version of Euclidean division with remainder, where the choice of quotient is implementation-defined. For example, it is standard to use the round-to-floor quotient in \(\mathbb{Z}\) and a round-to-nearest quotient in \(\mathbb{Z}[i]\). In non-Euclidean rings, these functions may implement some generalization of Euclidean division with remainder.

Powering

int gr_pow(gr_ptr res, gr_srcptr x, gr_srcptr y, gr_ctx_t ctx)

int gr_pow_ui(gr_ptr res, gr_srcptr x, ulong y, gr_ctx_t ctx)

int gr_pow_si(gr_ptr res, gr_srcptr x, slong y, gr_ctx_t ctx)

int gr_pow_fmpz(gr_ptr res, gr_srcptr x, const fmpz_t y, gr_ctx_t ctx)

int gr_pow_fmpq(gr_ptr res, gr_srcptr x, const fmpq_t y, gr_ctx_t ctx)

int gr_pow_other(gr_ptr res, gr_srcptr x, gr_srcptr y, gr_ctx_t y_ctx, gr_ctx_t ctx)

int gr_other_pow(gr_ptr res, gr_srcptr x, gr_ctx_t x_ctx, gr_srcptr y, gr_ctx_t ctx)

Sets res to the power \(x ^ y\), the interpretation of which depends on the ring when \(y \not \in \mathbb{Z}\). Returns the flag GR_DOMAIN if this power cannot be assigned a meaningful value in the present ring, or GR_UNABLE if the implementation is unable to perform the computation.

For subrings of \(\mathbb{C}\), it is implied that the principal power \(x^y = \exp(y \log(x))\) is computed for \(x \ne 0\).

Default implementations of the powering methods support raising elements to integer powers using a generic implementation of exponentiation by squaring. Particular rings should override these methods with faster versions or to support more general notions of exponentiation when possible.

Square roots

The default implementations of the following methods check for the elements 0 and 1 and otherwise return GR_UNABLE. Particular rings should override the methods when a square root algorithm is available.

In subrings of \(\mathbb{C}\), it is implied that the principal square root is computed; in other cases (e.g. in finite fields), the choice of root is implementation-dependent.

truth_t gr_is_square(gr_srcptr x, gr_ctx_t ctx)

Returns whether x is a perfect square in the present ring.

int gr_sqrt(gr_ptr res, gr_srcptr x, gr_ctx_t ctx)

int gr_rsqrt(gr_ptr res, gr_srcptr x, gr_ctx_t ctx)

Sets res to a square root of x (respectively reciprocal square root) in the present ring, if such an element exists. Returns the flag GR_DOMAIN if x is not a perfect square (also for zero, when computing the reciprocal square root), or GR_UNABLE if the implementation is unable to perform the computation.

Greatest common divisors

int gr_gcd(gr_ptr res, gr_srcptr x, gr_srcptr y, gr_ctx_t ctx)

Sets res to a greatest common divisor (GCD) of x and y. Since the GCD is unique only up to multiplication by a unit, an implementation-defined representative is chosen.

int gr_lcm(gr_ptr res, gr_srcptr x, gr_srcptr y, gr_ctx_t ctx)

Sets res to a least common multiple (LCM) of x and y. Since the LCM is unique only up to multiplication by a unit, an implementation-defined representative is chosen.

Factorization

int gr_factor(gr_ptr c, gr_vec_t factors, gr_vec_t exponents, gr_srcptr x, int flags, gr_ctx_t ctx)

Given \(x \in R\), computes a factorization

\(x = c {f_1}^{e_1} \ldots {f_n}^{e_n}\)

where \(f_k\) will be irreducible or prime (depending on \(R\)).

The prefactor \(c\) stores a unit or sign, e.g.the sign \(-1\), \(0\) or \(+1\) in \(\mathbb{Z}\), or a sign multiplied by the coefficient content in \(\mathbb{Z}[x]\). Note that this function outputs \(c\) as an element of the same ring as the input: for example, in \(\mathbb{Z}[x]\), \(c\) will be a constant polynomial rather than an element of the coefficient ring. The exponents \(e_k\) are output as a vector of fmpz elements.

The factors \(f_k\) are guaranteed to be distinct, but they are not guaranteed to be sorted in any particular order.

Integer and complex parts

int gr_floor(gr_ptr res, gr_srcptr x, gr_ctx_t ctx)

int gr_ceil(gr_ptr res, gr_srcptr x, gr_ctx_t ctx)

int gr_trunc(gr_ptr res, gr_srcptr x, gr_ctx_t ctx)

int gr_nint(gr_ptr res, gr_srcptr x, gr_ctx_t ctx)

In the real and complex numbers, sets res to the integer closest to x, respectively rounding towards minus infinity, plus infinity, zero, or the nearest integer (with tie-to-even).

int gr_abs(gr_ptr res, gr_srcptr x, gr_ctx_t ctx)

Sets res to the absolute value of x, which maybe defined both in complex rings and in any ordered ring.

int gr_i(gr_ptr res, gr_ctx_t ctx)

Sets res to the imaginary unit.

int gr_conj(gr_ptr res, gr_srcptr x, gr_ctx_t ctx)

int gr_re(gr_ptr res, gr_srcptr x, gr_ctx_t ctx)

int gr_im(gr_ptr res, gr_srcptr x, gr_ctx_t ctx)

int gr_sgn(gr_ptr res, gr_srcptr x, gr_ctx_t ctx)

int gr_csgn(gr_ptr res, gr_srcptr x, gr_ctx_t ctx)

These methods may return the flag GR_DOMAIN (or GR_UNABLE) when the ring is not a subring of the real or complex numbers.

Ordering methods

int gr_cmp(int *res, gr_srcptr x, gr_srcptr y, gr_ctx_t ctx)

int gr_cmp_other(int *res, gr_srcptr x, gr_srcptr y, gr_ctx_t y_ctx, gr_ctx_t ctx)

Sets res to -1, 0 or 1 according to whether x is less than, equal or greater than the absolute value of y. This may return GR_DOMAIN if the ring is not an ordered ring.

int gr_cmpabs(int *res, gr_srcptr x, gr_srcptr y, gr_ctx_t ctx)

int gr_cmpabs_other(int *res, gr_srcptr x, gr_srcptr y, gr_ctx_t y_ctx, gr_ctx_t ctx)

Sets res to -1, 0 or 1 according to whether the absolute value of x is less than, equal or greater than the absolute value of y. This may return GR_DOMAIN if the ring is not an ordered ring.

Finite field methods

int gr_ctx_fq_prime(fmpz_t p, gr_ctx_t ctx)

int gr_ctx_fq_degree(slong *deg, gr_ctx_t ctx)

int gr_ctx_fq_order(fmpz_t q, gr_ctx_t ctx)

int gr_fq_gen(gr_ptr res, gr_ctx_t ctx)

int gr_fq_frobenius(gr_ptr res, gr_srcptr x, slong e, gr_ctx_t ctx)

int gr_fq_multiplicative_order(fmpz_t res, gr_srcptr x, gr_ctx_t ctx)

int gr_fq_norm(fmpz_t res, gr_srcptr x, gr_ctx_t ctx)

int gr_fq_trace(fmpz_t res, gr_srcptr x, gr_ctx_t ctx)

truth_t gr_fq_is_primitive(gr_srcptr x, gr_ctx_t ctx)

int gr_fq_pth_root(gr_ptr res, gr_srcptr x, gr_ctx_t ctx)