qqbar.h

Initialises res and sets it to zero.

Clears res, freeing its memory.

Allocates an array of len algebraic numbers initialised to zero, or clears the len entries of vec and frees the array.

Swaps x and y in constant time.

Sets res to x. A rational number p/q in lowest terms with q > 0 has the minimal polynomial q t - p and an exact enclosure.

Sets res to x + yi for real x and y (not checked).

Sets res to the exact value of the double x, or of x + yi, and returns 1. If an input is infinite or NaN, returns 0 and leaves res unchanged.

Returns the degree of x, that is, of its minimal polynomial.

Returns whether x is a rational number (degree 1), an integer, or an algebraic integer (its minimal polynomial is monic).

Returns whether x is 0, 1, -1, i or -i. These inspect the minimal polynomial (and the sign of the imaginary part of the enclosure for \pm i) and are therefore very fast.

Returns whether x is real. This is decided exactly, see qqbar_sgn_im.

Sets res to the height of x, the largest absolute value of a coefficient of its minimal polynomial, or returns the number of bits of the height.

Returns whether x has degree at most deg_limit and height of at most bits_limit bits. A limit of 0 means no limit.

Returns whether the trivial bounds for the result of a binary operation on x and y are within the limits: the product of the degrees must be at most deg_limit and the sum of the height bits at most bits_limit. The degree bound is rigorous, the height bound only a heuristic. A limit of 0 means no limit.

Sets the output to the rational number x (as a numerator and denominator for the underscore version), or to the integer x. Throws an exception if x is not rational, respectively not an integer.

Sets res to 0, 1, the imaginary unit i, or the golden ratio \varphi = \frac{1}{2}(1 + \sqrt{5}).

Prints x to standard output in a form intended for debugging: the degree, the coefficients of the minimal polynomial (from the constant term upwards) and the enclosure, for example deg 2 [-1, -1, 1] [1.61803398874989484820458683436563811772 +/- 6.00e-39] for \varphi.

Prints a decimal approximation of x with n significant digits to standard output, such as 1.41421 - 1.73205*I; qqbar_printnd appends the degree, as in 1.41421 - 1.73205*I (deg 4).

Returns a string with the output of qqbar_printnd. The caller must free it with flint_free.

Sets res to a random algebraic number, a random real algebraic number, or a random nonreal algebraic number, with degree at most deg and height of at most bits bits. For qqbar_randtest_nonreal, deg must be at least 2.

Returns whether x = y: the minimal polynomials must be equal and the enclosures must contain a common root, which is decided by refining them until they are disjoint or their union is proved to contain a single root.

Returns whether x = f(y). This is faster than computing f(y) with qqbar_evaluate_fmpq_poly: the value f(y) is first compared numerically with x, and only if they cannot be separated is P(f(y)) = 0 checked exactly in \mathbb{Q}(y), where P is the minimal polynomial of x.

Compares the real parts, or the imaginary parts, of x and y, returning -1, 0 or 1.

Compares the absolute values of the real parts, of the imaginary parts, or of x and y themselves, returning -1, 0 or 1.

Compares x and y in the order used to sort roots of polynomials, returning -1, 0 or 1: real numbers come first, in decreasing order; nonreal numbers follow, by decreasing real part, then by increasing absolute value of the imaginary part, then with positive imaginary part first. Complex conjugates are therefore adjacent, the one in the upper half-plane first.

Returns a hash of x. Currently only the minimal polynomial is hashed, so conjugates have equal hashes, and similar polynomials give similar hash values; apply an integer hash function to the result if all bits must look random.

Sets res to the complex conjugate of x (the minimal polynomial is unchanged).

Sets res to the real part or the imaginary part of x, or res1 and res2 to both, computed as (x + \overline{x})/2 and (x - \overline{x})/(2i).

Sets res to |x| or |x|^2 = x \overline{x}.

Sets res to the complex sign of x: 0 if x = 0, otherwise x/|x|.

Returns the sign (-1, 0 or 1) of the real or imaginary part of x.

Returns the extension of the real sign function that is 1 in the open right half-plane, -1 in the open left half-plane, the sign of the imaginary part on the imaginary axis, and 0 at 0; equivalently \operatorname{csgn}(x) = x / \sqrt{x^2} for x \ne 0.

Sets res to \lfloor x \rfloor or \lceil x \rceil; for nonreal x, of its real part.

Sets res to -x.

Sets res to x + y.

Sets res to x - y.

Sets res to x y.

Sets res to x \cdot 2^e.

Sets res to x^2.

Sets res to 1/x, whose minimal polynomial is the reversal of that of x. Throws an exception (FLINT_DIVZERO) if x = 0.

Sets res to x / y. Throws an exception (FLINT_DIVZERO) if y = 0.

Sets res to (a x + b)/c in one operation, for integers a, b and c \ne 0, by transforming the minimal polynomial and the enclosure. Throws an exception if c = 0.

Sets res to the principal square root of x.

Sets res to 1/\sqrt{x}. Throws an exception if x = 0.

Sets res to x^n; for rational n = p/q the principal branch (x^{1/q})^p. x^0 = 1 for all x. Raising zero to a negative power throws an exception, and so does a rational exponent whose numerator or denominator does not fit in a word.

Sets res to the principal n-th root of x, for n \ge 1. The minimal polynomial is found among the factors of P(t^n), where P is the minimal polynomial of x; principal roots of positive rational numbers and roots of roots of unity are computed directly.

Sets res to the principal branch of x^{m/n} for a rational x and n \ge 1. Throws an exception if x = 0 and m < 0.

General exponentiation: if x^y is an algebraic number, sets res to it and returns 1; if x^y is transcendental or undefined, returns 0. By the Gelfond–Schneider theorem, x^y for algebraic x \notin \{0, 1\} and irrational algebraic y is transcendental, so the result is algebraic only if y is rational, x \in \{0, 1\} or y = 0. Unlike the other functions, this one returns 0 instead of throwing for 0^y with \operatorname{Re}(y) \le 0, y \ne 0.

Sets res to an enclosure of x rounded to prec bits. For qqbar_get_arb, if x is not real, res is set to [\mathrm{NaN} \pm \infty].

Sets res to an enclosure of the real or imaginary part of x rounded to prec bits.

Refines the enclosure stored in res to somewhat more than prec bits (at least QQBAR_DEFAULT_PREC). Operations normally refine enclosures in temporary variables without storing the result; calling this function first helps when res is used as an operand many times.

Sets res to the leading coefficient d of the minimal polynomial of y, a denominator in the sense that d y is an algebraic integer.

Sets res to d y, where d is given by qqbar_denominator.

Sets the entries of the array res to the d conjugates of x (including x), where d is the degree of x, sorted as by qqbar_cmp_root_order.

Sets res to f(x) for the polynomial f given by poly (with denominator den for the underscore fmpq version). The polynomial is first reduced modulo the minimal polynomial of x if its degree is too large; constant and linear polynomials and rational x are handled directly. In general, the minimal polynomial of f(x) is the minimal polynomial of the matrix of multiplication by f(x) in \mathbb{Q}(x), see Arithmetic with algebraic numbers.

Sets res to the value of the multivariate polynomial poly at the algebraic numbers x (one per variable of ctx) and returns 1. If a temporary result (not necessarily the final value, in case of cancellation) exceeds deg_limit or bits_limit in the sense of qqbar_binop_within_limits, the evaluation is aborted and 0 is returned. The evaluation uses the generic multivariate Horner scheme gr_fmpz_mpoly_evaluate_horner over the \overline{\mathbb{Q}} context (gr_fmpz_mpoly_evaluate_iter for a single term).

Sets the entries of the array res to the d = \deg(\mathit{poly}) roots of poly, repeated according to multiplicity. Unless QQBAR_ROOTS_UNSORTED is given, the roots are sorted by qqbar_cmp_root_order; copies of a repeated root are always consecutive. See Roots of polynomials and eigenvalues.

Sets the first entries of res to the real roots of poly, repeated according to multiplicity, and returns their number. The array must have room for \deg(\mathit{poly}) entries. Unless QQBAR_ROOTS_UNSORTED is given, the roots are in decreasing order, so that the output agrees with the first entries of the output of qqbar_roots_fmpz_poly. This is faster than computing all roots, since nonreal roots are never isolated and factors without real roots are skipped.

Sets the entries of res to the eigenvalues of the square matrix mat, repeated according to algebraic multiplicity, by computing the characteristic polynomial and calling qqbar_roots_fmpz_poly with the same flags.

Sets roots to the d = \mathit{len} - 1 roots of the squarefree polynomial f = a_0 + \cdots + a_d x^d with algebraic coefficients coeffs (a_d \ne 0), and returns 1; returns 0 if a limit is exceeded.

Sets res to the root of unity e^{2 \pi i p / q} or e^{\pi i p / q}. The minimal polynomial is a cyclotomic polynomial.

Returns whether x is a root of unity, that is, whether its minimal polynomial is cyclotomic. If so and if p and q are not NULL, sets them to the integers with 0 \le p < q and \gcd(p, q) = 1 such that x = e^{2 \pi i p / q}.

Sets res to \cos(\pi x), \sin(\pi x), \tan(\pi x), \cot(\pi x), \sec(\pi x) or \csc(\pi x) for x = p/q. The functions with an int return value return 1, or 0 if x is a pole. The cosine uses the minimal polynomial of \cos(2 \pi / n) (fmpz_poly_cos_minpoly), and the other functions are reduced to it.

If y = \log(x) / (\pi i) is algebraic, which happens exactly when x is a root of unity and then y is rational, sets p/q to y in lowest terms with -1 < y \le 1 and returns 1; otherwise returns 0.

If y = f(x) / \pi is algebraic, where f is the principal branch of the inverse trigonometric function, sets p/q to y (necessarily rational) in lowest terms and returns 1; otherwise returns 0. The ranges are |y| < \frac{1}{2} for atan, |y| \le \frac{1}{2} for asin and acsc, 0 \le y \le 1 for acos and asec, and -\frac{1}{2} < y \le \frac{1}{2} for acot.

Tries to find an algebraic number of degree at most max_deg and height of at most max_bits bits contained in the ball z, using LLL to find an integer relation between 1, z, \ldots, z^{\mathit{max\_deg}} at working precision prec. Returns 1 and sets res on success. The result is only a heuristic: success does not prove that the number behind z equals res, and failure does not prove that no such algebraic number exists.

Tries to express x in the number field \mathbb{Q}(\alpha): on success, returns 1 and sets res to a polynomial f of degree less than \deg \alpha with f(\alpha) = x. The identity is verified exactly, so success is proved. Failure does not prove that x \notin \mathbb{Q}(\alpha).

For x of degree 1 or 2, computes integers a, b, c, q with x = (a + b \sqrt{c})/q, q > 0, \gcd(a, b, q) = 1 and c not a perfect square; for rational x, b = c = 0.

Sets res to the algebraic number given by the expression expr and returns 1, or returns 0 if expr is not understood.

Sets res to AlgebraicNumberSerialized(List(coeffs), enclosure), which reflects the internal representation exactly. It can be read back with qqbar_set_fexpr cheaply and is the recommended format for serialisation, although it is not meant for human readers.

Sets res to PolynomialRootNearest(List(coeffs), point), where the decimal point is closer to x than to any other root, or to PolynomialRootIndexed(List(coeffs), index), where index (starting from 1) is the position of x among the roots in the order of qqbar_cmp_root_order. Both describe x unambiguously and readably, and can be read back with qqbar_set_fexpr, at the cost of root isolation.

Tries to write x as a closed-form expression with arithmetic operations, radicals and possibly exponentials or trigonometric functions, without PolynomialRootNearest or PolynomialRootIndexed. Returns 1 on success and 0 on failure. flags selects the methods (with flags = 0 only rational numbers are handled).

For nonconstant A and B, sets res to a polynomial whose roots are a + b (op = 0), a - b (1), a b (2) or a / b (3) for all roots a of A and b of B, with multiplicity. For op = 3, B must not have the root zero. The polynomial is computed from power sums with power series arithmetic over \mathbb{Q}, see Arithmetic with algebraic numbers.

For A of degree d \ge 2 with roots a_1, \ldots, a_d, sets res to a nonzero integer multiple of the polynomial of degree d(d-1)/2 with roots a_i + a_j (op = 0), (a_i - a_j)^2 (op = 1) or a_i a_j (op = 2) for 1 \le i < j \le d. For two distinct roots x, y of an irreducible A (such as complex conjugates), this annihilates x + y, (x - y)^2 or x y with half the degree of the polynomial from qqbar_fmpz_poly_composed_op.

Sets res to x + y, x - y, x y or x / y for op = 0, 1, 2, 3. Trivial cases such as rational operands are not handled here (the public arithmetic functions do that), but structure is exploited to avoid factoring a composed polynomial of degree \deg x \deg y when possible.

Given a ball z known to contain at least one root of poly, tries to prove that it contains exactly one, by one step of the interval Newton method on a slightly enlarged ball. On success sets res to the resulting (possibly smaller) enclosure of the root and returns 1; otherwise returns 0. The working precision is chosen from the accuracy of z, up to max_prec bits (a value of 0 selects it automatically). Uniqueness on the enlarged ball implies uniqueness on z but not existence, which must be known beforehand.

Like _qqbar_validate_uniqueness, but for an arbitrary ball z: proves that z contains exactly one root of poly (one interval Newton step whose result lies in the interior of z). For a real (or purely imaginary) ball the step is done on the real line (or imaginary axis), which proves that the root lies there.

Sets res to an enclosure of the root of poly isolated by z (or of x) with about prec bits of accuracy, by interval Newton steps with doubling precision; if a step fails to improve the accuracy enough, the roots are recomputed from scratch at higher precision. If z is already accurate enough, it is returned without rounding. The result is not polished as by qqbar_get_acb.

Tries to find an integer vector rel with \sum_i \mathit{rel}_i \mathit{vec}_i \approx 0 using LLL. The working precision is the smaller of prec and the relative accuracy of vec; 95% of the bits go into the LLL matrix and the remaining 5% are used to check the relation by evaluating it in ball arithmetic. If check is set, the return value says whether this check passed; otherwise it says whether the algorithm ran normally (it fails, for example, for non-finite input). A passed check is a heuristic filter against spurious relations, not a proof.

Returns 1 if x is cheaply recognised, from its minimal polynomial q t^d - p and its enclosure, as the principal root (p/q)^{1/d} of a positive rational number with d \ge 2, and 0 otherwise (0 does not prove the contrary). Used to speed up qqbar_root_ui.