fmpz.h

Macros converting between an fmpz that holds a pointer and the mpz_ptr itself. PTR_TO_COEFF shifts the pointer right by two bits and sets the tag bits $01$; this relies on mpz_structs being aligned to at least four bytes. COEFF_TO_PTR must only be applied to values for which COEFF_IS_MPZ is true.

Initialises $f$ to zero. This only stores a zero word and allocates nothing.

Initialises $f$ to zero with space for limbs limbs. If limbs is zero, this is fmpz_init; otherwise an mpz is attached and grown to limbs limbs, so that $f$ is temporarily not in canonical form (its value is 0 in an mpz) until the first assignment. Only useful to avoid reallocations when the final size is known.

Releases the memory used by $f$. A large value gives its mpz back to the memory manager (see Memory management); a small value needs no work.

Initialise $f$ and set it to $g$.

Sets $f$ to $g$.

Swaps $f$ and $g$ by exchanging the two words; no limbs are copied.

Set $f$ to 0 and 1. A large value of $f$ is released.

Set $f$ to val, and fmpz_neg_ui to $-$val.

Set $f$ to $h 2^{\mathtt{FLINT\_BITS}} + l$, respectively to its negative, where $h$ and $l$ are the unsigned words hi and lo.

Set $r$ to the integer whose two's complement representation with $2\mathtt{FLINT\_BITS}$ (respectively $3\mathtt{FLINT\_BITS}$) bits is hi, lo (respectively hi, mid, lo), the most significant word first. These convert the results of double-word signed arithmetic such as smul_ppmm.

Set out to the integer with the $n \ge 1$ limbs in[0], ..., in[n-1], least significant first: interpreted as an unsigned integer, or as a two's complement integer of $n \mathtt{FLINT\_BITS}$ bits.

Write the $n \ge 1$ limbs of in to out, least significant first. The unsigned version requires $0 \le$ in $< 2^{n \mathtt{FLINT\_BITS}}$; the signed version writes in modulo $2^{n \mathtt{FLINT\_BITS}}$, which is its two's complement representation if it fits in $n \mathtt{FLINT\_BITS}$ bits.

Sets $z$ to the integer with the $n$ limbs src, negated if negative is

1. Requires $n \ge 2$ and src[n-1] nonzero, so that the value does not fit inline; use fmpz_set_ui and fmpz_neg_ui for one limb, or fmpz_set_ui_array in general.

Return $f$ as an slong, respectively an ulong. The result is unspecified if $f$ does not fit (use fmpz_fits_si and fmpz_abs_fits_ui to check); currently fmpz_get_ui returns the low limb of $|f|$, so a negative $f$ is not reduced modulo $2^{\mathtt{FLINT\_BITS}}$.

Sets *hi and *low to the high and low limbs of $f$, for $0 \le f < 2^{2\mathtt{FLINT\_BITS}}$.

Sets *hi and *lo to the two limbs of $x$ modulo $2^{2\mathtt{FLINT\_BITS}}$, its two's complement representation if $x$ fits in $2\mathtt{FLINT\_BITS}$ bits.

Returns $f \bmod n$ in $[0, n)$ for the modulus $n$ of mod, for any $f$.

Returns $f$ as a double, rounded towards zero if it is not exactly representable. The result is undefined if $|f|$ exceeds the range of double; use fmpz_get_d_2exp for large values.

Sets $f$ to $c$ rounded towards zero. The result is undefined if $c$ is infinite or a NaN.

Returns a double $d$ with $0.5 \le |d| < 1$ and sets *exp to $e$ such that $d 2^e$ approximates $f$; $d$ is $f 2^{-e}$ truncated to 53 bits. For $f = 0$ it returns 0 and sets *exp to 0.

Sets $f$ to $d 2^{\mathit{exp}}$ rounded towards zero, so that $0.75 \cdot 2^0$ gives 0.

Convert between fmpz_t and an initialised GMP mpz_t, copying the value. Declared only if gmp.h is included before the FLINT headers.

Convert between fmpz_t and GMP's mpf_t; fmpz_set_mpf truncates a fractional value towards zero. Declared only if gmp.h is included first.

Sets the MPFR number $x$ to $f$, rounded in the direction rnd to the precision of $x$. Declared only if mpfr.h is included before the FLINT headers.

Allocates an array with flint_malloc, stores the limbs of $|n_{in}|$ in it, sets *n to it and returns the number of limbs (at least 1). The caller frees the array with flint_free. For $n_{in} = 0$ the array has one limb, which is 0.

flint_mpz_init_set_readonly sets the uninitialised mpz_t $z$ to the value of $f$, sharing the limbs of $f$ if it is large; $z$ must not be modified, $f$ must not change while $z$ is in use, and $z$ is released with flint_mpz_clear_readonly.

fmpz_init_set_readonly sets the uninitialised fmpz_t $f$ to the value of $z$, sharing the limbs of $z$ if the value is large; $f$ must not be modified, $z$ must not change while $f$ is in use, and $f$ is released with fmpz_clear_readonly.

Returns the representation of $f$ in base $b$, $2 \le b \le 62$, with a leading minus sign if $f < 0$. If str is NULL, the string is allocated with flint_malloc and must be freed with flint_free; otherwise it is written to str, which must have room for fmpz_sizeinbase(f, b) + 2 characters.

Sets $f$ to the integer written in base $b$, $2 \le b \le 62$, in the null-terminated string str, and returns 0. White space before and after the number and a minus sign are accepted. Returns $-1$ if the string is not a valid integer, in which case $f$ is undefined.

Print $x$ in decimal to file or to stdout, with a minus sign if negative and no newline. Return the number of characters written, or a nonpositive value on error.

Read a decimal integer (optional white space and minus sign, then digits) from file or from stdin into $f$. Return a positive value on success and 0 on failure, following mpz_inp_str.

Write $x$ to, respectively read it from, a stream in GMP's portable binary format: four bytes holding the signed number of bytes, then the bytes of $|x|$, most significant first. Files are interchangeable with mpz_out_raw and mpz_inp_raw. Return the number of bytes written or read, and 0 on error.

Set $f$ to a uniformly random integer with exactly bits bits (its top bit set), nonnegative for the unsigned version and with a random sign otherwise. For bits $= 0$ the result is 0.

Set $f$ to a random integer whose absolute value has a random number of bits between 0 and bits, nonnegative for the unsigned version. The values are biased towards sparse binary representations, 0, 1 and COEFF_MAX, which exercise special cases in tests.

As fmpz_randtest, but never 0. Requires bits $\ge 1$.

Sets $f$ to a uniformly random integer in $[0, m)$ for $m > 0$, and in $(m, 0]$ for $m < 0$.

Sets $f$ to a uniformly random integer in $[1, m)$. Requires $m \ge 2$.

Set $f$ to a random integer in $[0, m)$, respectively $(-m/2, m/2]$, for $m > 0$, with an increased probability of values near the ends of the range (and near zero for the signed version).

Sets $f$ to a random prime with exactly bits $\ge 2$ bits: the next prime after a random integer of that size, retried until it has the right size, so the distribution is not exactly uniform over primes. If proved is nonzero the result is proved prime, otherwise it is a probable prime as in fmpz_nextprime.

Returns $-1$, $0$ or $1$ according to the sign of $f$.

Return whether $f = 0$, $f = 1$ and $f = \pm 1$.

Return whether $f$ is even, respectively odd.

Return 1 if $f = g$ and 0 otherwise.

Return a negative value, zero or a positive value according to whether $f < g$, $f = g$ or $f > g$.

Compare $|f|$ with $|g|$, respectively with $|2g|$, returning a negative value, zero or a positive value.

Return the number of bits, respectively limbs, of $|f|$; both are 0 for $f = 0$.

Returns the number of digits of $|f|$ in base $b$, $2 \le b \le 62$, and 1 for $f = 0$. Unlike GMP's mpz_sizeinbase, the result is exact for all bases.

Returns the exponent of the largest power of 2 dividing $x$ (the number of trailing zero bits), and 0 for $x = 0$.

Return whether $|f|$ fits in an ulong, respectively whether $f$ fits in an slong.

For $x \ne 0$ and $1 \le$ bits $\le \mathtt{FLINT\_BITS}$, return a mantissa $m$ with exactly bits bits and set *exp to $e$ such that $m 2^e \le |x|$ (lower bound, $m$ is $|x|$ truncated), respectively $m 2^e \ge |x|$ (upper bound, $m$ is $|x|$ rounded up, which may increase $e$ by one if the rounding carries).

Returns an approximation of $\log x$ for $x > 0$, with a relative error of a few units in the last place of a double.

Return $\lfloor \log_b x \rfloor$ and $\lceil \log_b x \rceil$, computed exactly. Require $x \ge 1$ and $b \ge 2$.

Set $f_1$ to $-f_2$, respectively $|f_2|$.

Set $f$ to $g + h$, respectively $g - h$ (with $x$ in place of $h$).

Set $f$ to $g h$ (with $x$ in place of $h$). Two small operands are multiplied inline; large ones go to flint_mpn_mul or flint_mpn_sqr, which switch from basecase code through Karatsuba and GMP's Toom–Cook algorithms to FFT multiplication (Multiplying integers).

Sets $f$ to $g h_1 h_2$.

Set $f$ to $f + g h$, respectively $f - g h$ (with $x$ in place of $h$), without a temporary for the product when the operands are small.

Set $f$ to $ab + cd$, respectively $ab - cd$.

Set $f$ to $g 2^{\mathit{exp}}$, respectively $2^{\mathit{exp}}$. fmpz_mul_2exp assumes that $\mathit{exp} + \mathtt{FLINT\_BITS}$ does not overflow an ulong.

Set $f$ to $g h / 2^{\mathit{exp}}$ (with $x$ in place of $h$), rounded towards zero.

Set $f$ to $g^{\mathit{exp}}$, respectively $x$ to $b^e$, with $0^0 = 1$.

Sets $a$ to $b^e$ with $0^0 = 1$ and returns 1. For $|b| \ge 2$ and an exponent $e$ that does not fit in an slong (the result would not fit in memory), returns 0 and leaves $a$ unchanged. Throws an exception if $e < 0$.

Set $f$ to $\lfloor \sqrt g \rfloor$ and $r$ to $g - f^2$, for $g \ge 0$. Throw an exception if $g < 0$. In fmpz_sqrtrem, $f$ and $r$ must be distinct objects.

If $a$ is a perfect square, sets $s$ to $\sqrt a \ge 0$ and returns 1; otherwise returns 0 and leaves $s$ undefined. Faster than fmpz_is_square followed by fmpz_sqrt.

Returns whether $f$ is a perfect square ($f \ge 0$).

Sets $r$ to the $n$-th root of $f$ rounded towards zero and returns 1 if it is exact and 0 otherwise. Requires $n \ge 1$, and $f \ge 0$ if $n$ is even; otherwise an exception is raised.

If $f = r^k$ for some $k \ge 2$, sets root to $r$ and returns $k$; otherwise returns 0. Negative $f$ are allowed (then $k$ is odd). The exponent is not necessarily the largest one: $2^{120}$ currently gives $k = 2$, and $-2^{120}$ gives $k = 3$. By convention 0 and 1 give $k = 2$ and $-1$ gives $k = 1$.

Set $f$ to the quotient $q$ of $g$ by $h$, rounded towards zero, $-\infty$ and $+\infty$ respectively, and $s$ to the remainder $g - qh$. The remainder has the sign of $g$ (tdiv), of $h$ (fdiv) or of $-h$ (cdiv), and $|s| < |h|$. Throw an exception if $h = 0$.

Sets $q$ to $a/b$ rounded to the nearest integer, ties to even, and $r$ to $a - qb$, so that $|r| \le |b|/2$. Throws an exception if $b = 0$.

Set $f$ to the quotient of $g$ by $h$, rounded towards zero, $-\infty$ and $+\infty$ respectively. Throw an exception if $h = 0$.

Sets $f$ to the remainder of fmpz_fdiv_qr, which has the sign of $h$. Throws an exception if $h = 0$.

Set $f$ to the quotient, respectively the remainder, of $g$ by $2^{\mathit{exp}}$ with the rounding of the prefix. fmpz_fdiv_q_2exp is an arithmetic right shift and fmpz_fdiv_r_2exp the reduction to $[0, 2^{\mathit{exp}})$.

Return the absolute value of the remainder of $g$ by $h$ with the rounding of the prefix. fmpz_fdiv_ui thus returns $g \bmod h$ in $[0, h)$. Throw an exception if $h = 0$.

Set $f$ to $g / h$, assuming that $h$ divides $g$. This is not checked; if the division is not exact the result is meaningless. Faster than the other divisions, since it uses 2-adic (Hensel) division. Throw an exception if $h = 0$.

Sets $f$ to $g / (h_1 h_2)$, assuming that $h_1 h_2$ divides $g$. Throws an exception if $h_1$ or $h_2$ is 0.

Checked exact division: if $h$ divides $g$, set $q = g/h$ and return 1; otherwise set $q = 0$ and return 0. Division by zero counts as exact only for $g = 0$ (with $q = 0$).

Older name for fmpz_div.

Returns whether $g$ divides $f$, that is, whether $f = qg$ for an integer $q$. Every $g$ divides 0, and 0 divides only 0.

Return whether $g$ divides $f$. As for fmpz_divisible, every $g$ divides 0, and 0 divides only 0.

Compute a precomputed inverse of $f \ne 0$, respectively release it.

As fmpz_fdiv_qr and fmpz_fdiv_r, using the precomputed inverse inv of $h$, for many divisions by the same multi-limb $h$.

Sets $f$ to $g \bmod h$ in $[0, |h|)$. Requires $h \ne 0$, which is not checked (a zero divisor crashes with a division by zero).

Sets $f$ to $g \bmod h$ in $[0, h)$ and also returns it. Throws an exception if $h = 0$.

Sets $f$ to the symmetric remainder $y \equiv g \pmod h$ with $-|h|/2 < y \le |h|/2$. Requires $h \ne 0$ (not checked).

Sets $f$ to the symmetric remainder $y \equiv x \pmod m$ with $-m/2 < y \le m/2$, for $0 \le x < m$ (not checked).

Sets $r$ to $-a$ modulo mod for $0 \le a <$ mod (not checked).

If $\gcd(g, h) = 1$, sets $f$ to the inverse of $g$ modulo $h$ in $[0, |h|)$ and returns 1; otherwise returns 0 and $f$ is undefined. Every $g$ is invertible modulo $h = \pm 1$, with inverse 0. Throws an exception if $h = 0$.

Set $f$ to $g^e \bmod m$ in $[0, m)$, for $m \ge 1$ (an exception is raised otherwise). For $m = 1$ the result is 0, and otherwise $g^0 = 1$. fmpz_powm accepts $e < 0$ if $g$ is invertible modulo $m$ and raises an exception if it is not.

For a prime $p$: if $a$ is a square modulo $p$, sets $b$ to a square root and returns 1, otherwise sets $b$ to 0 and returns 0. Primality of $p$ is not checked; for composite $p$ a return value of 1 means nothing.

Sets rop to op with all factors $f$ removed and returns their number, the largest $v$ with $f^v \mid$ op. Requires $f \ge 2$ (an exception is raised otherwise). For op $= 0$, rop is set to 0 and 0 is returned.

Returns the Jacobi symbol $\left(\frac{a}{p}\right)$ for any $a$ and odd $p > 0$. The conditions on $p$ are not checked.

Returns the Kronecker symbol $\left(\frac{a}{n}\right)$ for any $a$ and $n$.

Sets the outputs so that the solutions $x \in [0, n)$ of $ax \equiv b \pmod n$ are exactly $\mathit{xstart} + i \cdot \mathit{xstride}$ for $0 \le i < \mathit{xlength}$; there are none if xlength is 0. Requires $n > 0$; the outputs must be distinct objects.

Sets rop to the inverse of op modulo $2^N$. Throws an exception if op is even.

Hensel division: sets rop to the unique $q \in [0, 2^N)$ with $qb \equiv a \pmod{2^N}$. Throws an exception if $b$ is even.

If op is an odd square modulo $2^N$ (for $N \ge 3$: op $\equiv 1 \pmod 8$), set rop to a square root $y$, respectively an inverse square root ($\mathit{op}\, y^2 \equiv 1$), modulo $2^N$, and return 1; otherwise return 0. The root returned is the one congruent to 1 modulo 4, reduced modulo $2^N$. Even op is not supported (0 is returned).

Set $f$ to $\gcd(g, h) \ge 0$, with $\gcd(0, 0) = 0$.

Sets $f$ to $\gcd(a, b, c) \ge 0$. Faster than two calls to fmpz_gcd when one operand is small or the GCD of the two shortest operands is 1.

Sets $f$ to the least common multiple of $g$ and $h$, which is nonnegative, and 0 if $g$ or $h$ is 0.

Sets $d = \gcd(f, g) \ge 0$ and cofactors $a$, $b$ with $af + bg = d$. The outputs must be distinct objects.

As fmpz_xgcd, but the cofactors are the canonical Bézout coefficients defined on GCD, LCM and Bézout coefficients: the minimal ones, with fixed choices in the degenerate cases. Usually faster than fmpz_xgcd.

For $0 \le f < g$, sets $d = \gcd(f, g)$ and $a$ to a cofactor in $[0, g)$ with $af \equiv d \pmod g$, so that $a = f^{-1} \bmod g$ if $d = 1$. For $f = 0$ it sets $d = g$ and $a = 0$. The outputs must be distinct objects.

Runs the extended Euclidean algorithm on $r_2 > r_1 > 0$ until the remainder drops to at most $L$, with Lehmer's acceleration. On return $r_2$ and $r_1$ are the last two remainders and co2, co1 the corresponding cofactors, with co2$\cdot r_1 -$ co1$\cdot r_2 = \pm r_{2,\mathrm{orig}}$. No aliasing is allowed.

Set out to the unique $x \equiv r_1 \pmod{m_1}$, $x \equiv r_2 \pmod {m_2}$ in $[0, m_1 m_2)$ if sign is 0, and in $(-m_1 m_2/2, m_1 m_2/2]$ otherwise. Require coprime $m_1, m_2 > 0$, $-m_1 \le r_1 < m_1$ and $0 \le r_2 < m_2$; only the coprimality is checked (by fmpz_CRT, which raises an exception).

As fmpz_CRT_ui with precomputed data: m2inv $=$ n_preinvert_limb(m2), m1m2 $= m_1 m_2$ and $c = m_1^{-1} \bmod m_2$. Used when the same pair of moduli recurs.

Initialise C for the $\mathit{num\_primes} \ge 1$ pairwise coprime nonzero word-size moduli in primes (they need not be prime; the array is copied), respectively release it. fmpz_comb_init2 precomputes only what the operations in flags (FMPZ_COMB_MOD, FMPZ_COMB_CRT or both) need.

Allocate, respectively free, scratch space for calls with C. A scratch space is not thread-safe; each thread needs its own.

Sets out[i] to in modulo the $i$-th modulus of C, in $[0, m_i)$, for any in.