.. _qqbar:

**qqbar.h** -- algebraic numbers represented by minimal polynomials
===============================================================================

A :type:`qqbar_t` represents a real or complex algebraic number
(an element of `\overline{\mathbb{Q}}`) by its unique reduced
minimal polynomial in `\mathbb{Z}[x]` and an isolating complex interval.
The precision of isolating intervals is maintained automatically to
ensure that all operations on :type:`qqbar_t` instances are exact.

This representation is useful for working with
individual algebraic numbers of moderate degree (up to 100, say).
Arithmetic in this representation is expensive: an arithmetic operation
on numbers of degrees *m* and *n* involves computing and then factoring an
annihilating polynomial of degree *mn* and potentially also performing
numerical root-finding. For doing repeated arithmetic, it is generally
more efficient to work with the :type:`ca_t` type in a fixed
number field.
The :type:`qqbar_t` type is used internally by the :type:`ca_t` type
to represent the embedding of number fields in `\mathbb{R}` or
`\mathbb{C}` and to decide predicates for algebraic numbers.


Types and macros
-------------------------------------------------------------------------------

.. type:: qqbar_struct

.. type:: qqbar_t

    A *qqbar_struct* consists of an *fmpz_poly_struct* and an *acb_struct*.
    A *qqbar_t* is defined as an array of length one of type
    *qqbar_struct*, permitting a *qqbar_t* to be passed by
    reference.

.. type:: qqbar_ptr

    Alias for ``qqbar_struct *``, used for *qqbar* vectors.

.. type:: qqbar_srcptr

    Alias for ``const qqbar_struct *``, used for *qqbar* vectors
    when passed as readonly input to functions.

.. macro:: QQBAR_POLY(x)

    Macro returning a pointer to the minimal polynomial of *x* which can be used as an *fmpz_poly_t*.

.. macro:: QQBAR_COEFFS(x)

    Macro returning a pointer to the array of *fmpz* coefficients of the
    minimal polynomial of *x*.

.. macro:: QQBAR_ENCLOSURE(x)

    Macro returning a pointer to the enclosure of *x* which can be used as an *acb_t*.

Memory management
-------------------------------------------------------------------------------

.. function:: void qqbar_init(qqbar_t res)

    Initializes the variable *res* for use, and sets its value to zero.

.. function:: void qqbar_clear(qqbar_t res)

    Clears the variable *res*, freeing or recycling its allocated memory.

.. function:: qqbar_ptr _qqbar_vec_init(slong len)

    Returns a pointer to an array of *len* initialized *qqbar_struct*:s.

.. function:: void _qqbar_vec_clear(qqbar_ptr vec, slong len)

    Clears all *len* entries in the vector *vec* and frees the
    vector itself.

Assignment
-------------------------------------------------------------------------------

.. function:: void qqbar_swap(qqbar_t x, qqbar_t y)

    Swaps the values of *x* and *y* efficiently.

.. function:: void qqbar_set(qqbar_t res, const qqbar_t x)
              void qqbar_set_si(qqbar_t res, slong x)
              void qqbar_set_ui(qqbar_t res, ulong x)
              void qqbar_set_fmpz(qqbar_t res, const fmpz_t x)
              void qqbar_set_fmpq(qqbar_t res, const fmpq_t x)

    Sets *res* to the value *x*.

.. function:: void qqbar_set_re_im(qqbar_t res, const qqbar_t x, const qqbar_t y)

    Sets *res* to the value `x + yi`.

.. function:: int qqbar_set_d(qqbar_t res, double x)
              int qqbar_set_re_im_d(qqbar_t res, double x, double y)

    Sets *res* to the value *x* or `x + yi` respectively. These functions
    performs error handling: if *x* and *y* are finite, the conversion succeeds
    and the return flag is 1. If *x* or *y* is non-finite (infinity or NaN),
    the conversion fails and the return flag is 0.

Properties
-------------------------------------------------------------------------------

.. function:: slong qqbar_degree(const qqbar_t x)

    Returns the degree of *x*, i.e. the degree of the minimal polynomial.

.. function:: int qqbar_is_rational(const qqbar_t x)

    Returns whether *x* is a rational number.

.. function:: int qqbar_is_integer(const qqbar_t x)

    Returns whether *x* is an integer (an element of `\mathbb{Z}`).

.. function:: int qqbar_is_algebraic_integer(const qqbar_t x)

    Returns whether *x* is an algebraic integer, i.e. whether its minimal
    polynomial has leading coefficient 1.

.. function:: int qqbar_is_zero(const qqbar_t x)
              int qqbar_is_one(const qqbar_t x)
              int qqbar_is_neg_one(const qqbar_t x)

    Returns whether *x* is the number `0`, `1`, `-1`.

.. function:: int qqbar_is_i(const qqbar_t x)
              int qqbar_is_neg_i(const qqbar_t x)

    Returns whether *x* is the imaginary unit `i` (respectively `-i`).

.. function:: int qqbar_is_real(const qqbar_t x)

    Returns whether *x* is a real number.

.. function:: void qqbar_height(fmpz_t res, const qqbar_t x)

    Sets *res* to the height of *x* (the largest absolute value of the
    coefficients of the minimal polynomial of *x*).

.. function:: slong qqbar_height_bits(const qqbar_t x)

    Returns the height of *x* (the largest absolute value of the
    coefficients of the minimal polynomial of *x*) measured in bits.

.. function:: int qqbar_within_limits(const qqbar_t x, slong deg_limit, slong bits_limit)

    Checks if *x* has degree bounded by *deg_limit* and height
    bounded by *bits_limit* bits, returning 0 (false) or 1 (true).
    If *deg_limit* is set to 0, the degree check is skipped,
    and similarly for *bits_limit*.

.. function:: int qqbar_binop_within_limits(const qqbar_t x, const qqbar_t y, slong deg_limit, slong bits_limit)

    Checks if `x + y`, `x - y`, `x \cdot y` and `x / y` certainly have
    degree bounded by *deg_limit* (by multiplying the degrees for *x* and *y*
    to obtain a trivial bound). For *bits_limits*, the sum of the bit heights
    of *x* and *y* is checked against the bound (this is only a heuristic).
    If *deg_limit* is set to 0, the degree check is skipped,
    and similarly for *bits_limit*.

Conversions
-------------------------------------------------------------------------------

.. function:: void _qqbar_get_fmpq(fmpz_t num, fmpz_t den, const qqbar_t x)

    Sets *num* and *den* to the numerator and denominator of *x*.
    Aborts if *x* is not a rational number.

.. function:: void qqbar_get_fmpq(fmpq_t res, const qqbar_t x)

    Sets *res* to *x*. Aborts if *x* is not a rational number.

.. function:: void qqbar_get_fmpz(fmpz_t res, const qqbar_t x)

    Sets *res* to *x*. Aborts if *x* is not an integer.

Special values
-------------------------------------------------------------------------------

.. function:: void qqbar_zero(qqbar_t res)

    Sets *res* to the number 0.

.. function:: void qqbar_one(qqbar_t res)

    Sets *res* to the number 1.

.. function:: void qqbar_i(qqbar_t res)

    Sets *res* to the imaginary unit `i`.

.. function:: void qqbar_phi(qqbar_t res)

    Sets *res* to the golden ratio `\varphi = \tfrac{1}{2}(\sqrt{5} + 1)`.

Input and output
-------------------------------------------------------------------------------

.. function:: void qqbar_print(const qqbar_t x)

    Prints *res* to standard output. The output shows the degree
    and the list of coefficients
    of the minimal polynomial followed by a decimal representation of
    the enclosing interval. This function is mainly intended for debugging.

.. function:: void qqbar_printn(const qqbar_t x, slong n)

    Prints *res* to standard output. The output shows a decimal
    approximation to *n* digits.

.. function:: void qqbar_printnd(const qqbar_t x, slong n)

    Prints *res* to standard output. The output shows a decimal
    approximation to *n* digits, followed by the degree of the number.

For example, *print*, *printn* and *printnd* with `n = 6` give
the following output for the numbers 0, 1, `i`, `\varphi`, `\sqrt{2}-\sqrt{3} i`:

.. code::

    deg 1 [0, 1] 0
    deg 1 [-1, 1] 1.00000
    deg 2 [1, 0, 1] 1.00000*I
    deg 2 [-1, -1, 1] [1.61803398874989484820458683436563811772 +/- 6.00e-39]
    deg 4 [25, 0, 2, 0, 1] [1.4142135623730950488016887242096980786 +/- 8.67e-38] + [-1.732050807568877293527446341505872367 +/- 1.10e-37]*I

    0
    1.00000
    1.00000*I
    1.61803
    1.41421 - 1.73205*I

    0 (deg 1)
    1.00000 (deg 1)
    1.00000*I (deg 2)
    1.61803 (deg 2)
    1.41421 - 1.73205*I (deg 4)


Random generation
-------------------------------------------------------------------------------

.. function:: void qqbar_randtest(qqbar_t res, flint_rand_t state, slong deg, slong bits)

    Sets *res* to a random algebraic number with degree up to *deg* and
    with height (measured in bits) up to *bits*.

.. function:: void qqbar_randtest_real(qqbar_t res, flint_rand_t state, slong deg, slong bits)

    Sets *res* to a random real algebraic number with degree up to *deg* and
    with height (measured in bits) up to *bits*.

.. function:: void qqbar_randtest_nonreal(qqbar_t res, flint_rand_t state, slong deg, slong bits)

    Sets *res* to a random nonreal algebraic number with degree up to *deg* and
    with height (measured in bits) up to *bits*. Since all algebraic numbers
    of degree 1 are real, *deg* must be at least 2.

Comparisons
-------------------------------------------------------------------------------

.. function:: int qqbar_equal(const qqbar_t x, const qqbar_t y)

    Returns whether *x* and *y* are equal.

.. function:: int qqbar_equal_fmpq_poly_val(const qqbar_t x, const fmpq_poly_t f, const qqbar_t y)

    Returns whether *x* is equal to `f(y)`. This function is more efficient
    than evaluating `f(y)` and comparing the results.

.. function:: int qqbar_cmp_re(const qqbar_t x, const qqbar_t y)

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

.. function:: int qqbar_cmp_im(const qqbar_t x, const qqbar_t y)

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

.. function:: int qqbar_cmpabs_re(const qqbar_t x, const qqbar_t y)

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

.. function:: int qqbar_cmpabs_im(const qqbar_t x, const qqbar_t y)

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

.. function:: int qqbar_cmpabs(const qqbar_t x, const qqbar_t y)

    Compares the absolute values of *x* and *y*, returning -1, 0 or +1.

.. function:: int qqbar_cmp_root_order(const qqbar_t x, const qqbar_t y)

    Compares *x* and *y* using an arbitrary but convenient ordering
    defined on the complex numbers. This is useful for sorting the
    roots of a polynomial in a canonical order.

    We define the root order as follows: real roots come first, in
    descending order. Nonreal roots are subsequently ordered first by
    real part in descending order, then in ascending order by the
    absolute value of the imaginary part, and then in descending
    order of the sign. This implies that complex conjugate roots
    are adjacent, with the root in the upper half plane first.

.. function:: ulong qqbar_hash(const qqbar_t x)

    Returns a hash of *x*. As currently implemented, this function
    only hashes the minimal polynomial of *x*. The user should
    mix in some bits based on the numerical value if it is critical
    to distinguish between conjugates of the same minimal polynomial.
    This function is also likely to produce serial runs of values for
    lexicographically close minimal polynomials. This is not
    necessarily a problem for use in hash tables, but if it is
    important that all bits in the output are random,
    the user should apply an integer hash function to the output.

Complex parts
-------------------------------------------------------------------------------

.. function:: void qqbar_conj(qqbar_t res, const qqbar_t x)

    Sets *res* to the complex conjugate of *x*.

.. function:: void qqbar_re(qqbar_t res, const qqbar_t x)

    Sets *res* to the real part of *x*.

.. function:: void qqbar_im(qqbar_t res, const qqbar_t x)

    Sets *res* to the imaginary part of *x*.

.. function:: void qqbar_re_im(qqbar_t res1, qqbar_t res2, const qqbar_t x)

    Sets *res1* to the real part of *x* and *res2* to the imaginary part of *x*.

.. function:: void qqbar_abs(qqbar_t res, const qqbar_t x)

    Sets *res* to the absolute value of *x*:

.. function:: void qqbar_abs2(qqbar_t res, const qqbar_t x)

    Sets *res* to the square of the absolute value of *x*.

.. function:: void qqbar_sgn(qqbar_t res, const qqbar_t x)

    Sets *res* to the complex sign of *x*, defined as 0 if *x* is zero
    and as `x / |x|` otherwise.

.. function:: int qqbar_sgn_re(const qqbar_t x)

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

.. function:: int qqbar_sgn_im(const qqbar_t x)

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

.. function:: int qqbar_csgn(const qqbar_t x)

    Returns the extension of the real sign function taking the
    value 1 for *x* strictly in the right half plane, -1 for *x* strictly
    in the left half plane, and the sign of the imaginary part when *x* is on
    the imaginary axis. Equivalently, `\operatorname{csgn}(x) = x / \sqrt{x^2}`
    except that the value is 0 when *x* is zero.

Integer parts
-------------------------------------------------------------------------------

.. function:: void qqbar_floor(fmpz_t res, const qqbar_t x)

    Sets *res* to the floor function of *x*. If *x* is not real, the
    value is defined as the floor function of the real part of *x*.

.. function:: void qqbar_ceil(fmpz_t res, const qqbar_t x)

    Sets *res* to the ceiling function of *x*. If *x* is not real, the
    value is defined as the ceiling function of the real part of *x*.

Arithmetic
-------------------------------------------------------------------------------

.. function:: void qqbar_neg(qqbar_t res, const qqbar_t x)

    Sets *res* to the negation of *x*.

.. function:: void qqbar_add(qqbar_t res, const qqbar_t x, const qqbar_t y)
              void qqbar_add_fmpq(qqbar_t res, const qqbar_t x, const fmpq_t y)
              void qqbar_add_fmpz(qqbar_t res, const qqbar_t x, const fmpz_t y)
              void qqbar_add_ui(qqbar_t res, const qqbar_t x, ulong y)
              void qqbar_add_si(qqbar_t res, const qqbar_t x, slong y)

    Sets *res* to the sum of *x* and *y*.

.. function:: void qqbar_sub(qqbar_t res, const qqbar_t x, const qqbar_t y)
              void qqbar_sub_fmpq(qqbar_t res, const qqbar_t x, const fmpq_t y)
              void qqbar_sub_fmpz(qqbar_t res, const qqbar_t x, const fmpz_t y)
              void qqbar_sub_ui(qqbar_t res, const qqbar_t x, ulong y)
              void qqbar_sub_si(qqbar_t res, const qqbar_t x, slong y)
              void qqbar_fmpq_sub(qqbar_t res, const fmpq_t x, const qqbar_t y)
              void qqbar_fmpz_sub(qqbar_t res, const fmpz_t x, const qqbar_t y)
              void qqbar_ui_sub(qqbar_t res, ulong x, const qqbar_t y)
              void qqbar_si_sub(qqbar_t res, slong x, const qqbar_t y)

    Sets *res* to the difference of *x* and *y*.

.. function:: void qqbar_mul(qqbar_t res, const qqbar_t x, const qqbar_t y)
              void qqbar_mul_fmpq(qqbar_t res, const qqbar_t x, const fmpq_t y)
              void qqbar_mul_fmpz(qqbar_t res, const qqbar_t x, const fmpz_t y)
              void qqbar_mul_ui(qqbar_t res, const qqbar_t x, ulong y)
              void qqbar_mul_si(qqbar_t res, const qqbar_t x, slong y)

    Sets *res* to the product of *x* and *y*.

.. function:: void qqbar_mul_2exp_si(qqbar_t res, const qqbar_t x, slong e)

    Sets *res* to *x* multiplied by `2^e`.

.. function:: void qqbar_sqr(qqbar_t res, const qqbar_t x)

    Sets *res* to the square of *x*.

.. function:: void qqbar_inv(qqbar_t res, const qqbar_t x)

    Sets *res* to the multiplicative inverse of *y*.
    Division by zero calls *flint_abort*.

.. function:: void qqbar_div(qqbar_t res, const qqbar_t x, const qqbar_t y)
              void qqbar_div_fmpq(qqbar_t res, const qqbar_t x, const fmpq_t y)
              void qqbar_div_fmpz(qqbar_t res, const qqbar_t x, const fmpz_t y)
              void qqbar_div_ui(qqbar_t res, const qqbar_t x, ulong y)
              void qqbar_div_si(qqbar_t res, const qqbar_t x, slong y)
              void qqbar_fmpq_div(qqbar_t res, const fmpq_t x, const qqbar_t y)
              void qqbar_fmpz_div(qqbar_t res, const fmpz_t x, const qqbar_t y)
              void qqbar_ui_div(qqbar_t res, ulong x, const qqbar_t y)
              void qqbar_si_div(qqbar_t res, slong x, const qqbar_t y)

    Sets *res* to the quotient of *x* and *y*.
    Division by zero calls *flint_abort*.

.. function:: void qqbar_scalar_op(qqbar_t res, const qqbar_t x, const fmpz_t a, const fmpz_t b, const fmpz_t c)

    Sets *res* to the rational affine transformation `(ax+b)/c`, performed as
    a single operation. There are no restrictions on *a*, *b* and *c*
    except that *c* must be nonzero. Division by zero calls *flint_abort*.

Powers and roots
-------------------------------------------------------------------------------

.. function:: void qqbar_sqrt(qqbar_t res, const qqbar_t x)
              void qqbar_sqrt_ui(qqbar_t res, ulong x)

    Sets *res* to the principal square root of *x*.

.. function:: void qqbar_rsqrt(qqbar_t res, const qqbar_t x)

    Sets *res* to the reciprocal of the principal square root of *x*.
    Division by zero calls *flint_abort*.

.. function:: void qqbar_pow_ui(qqbar_t res, const qqbar_t x, ulong n)
              void qqbar_pow_si(qqbar_t res, const qqbar_t x, slong n)
              void qqbar_pow_fmpz(qqbar_t res, const qqbar_t x, const fmpz_t n)
              void qqbar_pow_fmpq(qqbar_t res, const qqbar_t x, const fmpq_t n)

    Sets *res* to *x* raised to the *n*-th power.
    Raising zero to a negative power aborts.

.. function:: void qqbar_root_ui(qqbar_t res, const qqbar_t x, ulong n)
              void qqbar_fmpq_root_ui(qqbar_t res, const fmpq_t x, ulong n)

    Sets *res* to the principal *n*-th root of *x*. The order *n*
    must be positive.

.. function:: void qqbar_fmpq_pow_si_ui(qqbar_t res, const fmpq_t x, slong m, ulong n)

    Sets *res* to the principal branch of `x^{m/n}`. The order *n*
    must be positive. Division by zero calls *flint_abort*.

.. function:: int qqbar_pow(qqbar_t res, const qqbar_t x, const qqbar_t y)

    General exponentiation: if `x^y` is an algebraic number, sets *res*
    to this value and returns 1. If `x^y` is transcendental or
    undefined, returns 0. Note that this function returns 0 instead of
    aborting on division zero.

Numerical enclosures
-------------------------------------------------------------------------------

The following functions guarantee a polished output in which both the real
and imaginary parts are accurate to *prec* bits and exact when exactly
representable (that is, when a real or imaginary part is a sufficiently
small dyadic number).
In some cases, the computations needed to polish the output may be
expensive. When polish is unnecessary, :func:`qqbar_enclosure_raw`
may be used instead. Alternatively, :func:`qqbar_cache_enclosure`
can be used to avoid recomputations.

.. function:: void qqbar_get_acb(acb_t res, const qqbar_t x, slong prec)

    Sets *res* to an enclosure of *x* rounded to *prec* bits.

.. function:: void qqbar_get_arb(arb_t res, const qqbar_t x, slong prec)

    Sets *res* to an enclosure of *x* rounded to *prec* bits, assuming that
    *x* is a real number. If *x* is not real, *res* is set to
    `[\operatorname{NaN} \pm \infty]`.

.. function:: void qqbar_get_arb_re(arb_t res, const qqbar_t x, slong prec)

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

.. function:: void qqbar_get_arb_im(arb_t res, const qqbar_t x, slong prec)

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

.. function:: void qqbar_cache_enclosure(qqbar_t res, slong prec)

    Polishes the internal enclosure of *res* to at least *prec* bits
    of precision in-place. Normally, *qqbar* operations that need
    high-precision enclosures compute them on the fly without caching the results;
    if *res* will be used as an invariant operand for many operations,
    calling this function as a precomputation step can improve performance.

Numerator and denominator
-------------------------------------------------------------------------------

.. function:: void qqbar_denominator(fmpz_t res, const qqbar_t y)

    Sets *res* to the denominator of *y*, i.e. the leading coefficient
    of the minimal polynomial of *y*.

.. function:: void qqbar_numerator(qqbar_t res, const qqbar_t y)

    Sets *res* to the numerator of *y*, i.e. *y* multiplied by
    its denominator.

Conjugates
-------------------------------------------------------------------------------

.. function:: void qqbar_conjugates(qqbar_ptr res, const qqbar_t x)

    Sets the entries of the vector *res* to the *d* algebraic conjugates of
    *x*, including *x* itself, where *d* is the degree of *x*. The output
    is sorted in a canonical order (as defined by :func:`qqbar_cmp_root_order`).

Polynomial evaluation
-------------------------------------------------------------------------------

.. function:: void _qqbar_evaluate_fmpq_poly(qqbar_t res, const fmpz * poly, const fmpz_t den, slong len, const qqbar_t x)
              void qqbar_evaluate_fmpq_poly(qqbar_t res, const fmpq_poly_t poly, const qqbar_t x)
              void _qqbar_evaluate_fmpz_poly(qqbar_t res, const fmpz * poly, slong len, const qqbar_t x)
              void qqbar_evaluate_fmpz_poly(qqbar_t res, const fmpz_poly_t poly, const qqbar_t x)

    Sets *res* to the value of the given polynomial *poly* evaluated at
    the algebraic number *x*. These methods detect simple special cases and
    automatically reduce *poly* if its degree is greater or equal
    to that of the minimal polynomial of *x*. In the generic case, evaluation
    is done by computing minimal polynomials of representation matrices.

.. function:: int qqbar_evaluate_fmpz_mpoly_iter(qqbar_t res, const fmpz_mpoly_t poly, qqbar_srcptr x, slong deg_limit, slong bits_limit, const fmpz_mpoly_ctx_t ctx)
              int qqbar_evaluate_fmpz_mpoly_horner(qqbar_t res, const fmpz_mpoly_t poly, qqbar_srcptr x, slong deg_limit, slong bits_limit, const fmpz_mpoly_ctx_t ctx)
              int qqbar_evaluate_fmpz_mpoly(qqbar_t res, const fmpz_mpoly_t poly, qqbar_srcptr x, slong deg_limit, slong bits_limit, const fmpz_mpoly_ctx_t ctx)

    Sets *res* to the value of *poly* evaluated at the algebraic numbers
    given in the vector *x*. The number of variables is defined by
    the context object *ctx*.

    The parameters *deg_limit* and *bits_limit*
    define evaluation limits: if any temporary result exceeds these limits
    (not necessarily the final value, in case of cancellation), the
    evaluation is aborted and 0 (failure) is returned. If evaluation
    succeeds, 1 is returned.

    The *iter* version iterates over all terms in succession and computes
    the powers that appear. The *horner* version uses a multivariate
    implementation of the Horner scheme. The default algorithm currently
    uses the Horner scheme.

Polynomial roots
-------------------------------------------------------------------------------

.. function:: void qqbar_roots_fmpz_poly(qqbar_ptr res, const fmpz_poly_t poly, int flags)
              void qqbar_roots_fmpq_poly(qqbar_ptr res, const fmpq_poly_t poly, int flags)

    Sets the entries of the vector *res* to the *d* roots of the polynomial
    *poly*. Roots with multiplicity appear with repetition in the
    output array. By default, the roots will be sorted in a
    convenient canonical order (as defined by :func:`qqbar_cmp_root_order`).
    Instances of a repeated root always appear consecutively.

    The following *flags* are supported:

    - QQBAR_ROOTS_IRREDUCIBLE - if set, *poly* is assumed to be
      irreducible (it may still have constant content), and no polynomial
      factorization is performed internally.

    - QQBAR_ROOTS_UNSORTED - if set, the roots will not be guaranteed
      to be sorted (except for repeated roots being listed
      consecutively).

.. function:: void qqbar_eigenvalues_fmpz_mat(qqbar_ptr res, const fmpz_mat_t mat, int flags)
              void qqbar_eigenvalues_fmpq_mat(qqbar_ptr res, const fmpq_mat_t mat, int flags)

    Sets the entries of the vector *res* to the eigenvalues of the
    square matrix *mat*. These functions compute the characteristic polynomial
    of *mat* and then call :func:`qqbar_roots_fmpz_poly` with the same
    flags.

.. function:: int _qqbar_roots_poly_squarefree(qqbar_ptr roots, qqbar_srcptr coeffs, slong len, slong deg_limit, slong bits_limit)

    Writes to the vector *roots* the `d` roots of the polynomial
    with algebraic number coefficients *coeffs* of length *len* (`d = len - 1`).

    Given the polynomial `f = a_0 + \ldots + a_d x^d` with coefficients in
    `\overline{\mathbb{Q}}`, we construct an annihilating polynomial with
    coefficients in `\mathbb{Q}` as
    `g = \prod (\tilde a_0 + \ldots + \tilde a_d x^d)`
    where the product is taken over all
    combinations of algebraic conjugates `\tilde a_k` of the input
    coefficients.
    The polynomial `g` is subsequently factored to find candidate
    roots.

    The leading coefficient `a_d` must be nonzero and the polynomial `f`
    polynomial must be squarefree.
    To compute roots of a general polynomial which may have repeated roots,
    it is necessary to perform a squarefree factorization before calling
    this function.
    An option is to call :func:`gr_poly_roots` with a ``qqbar`` context object,
    which wraps this function
    and takes care of the initial squarefree factorization.

    Since the product `g` can explode in size very quickly, the *deg_limit*
    and *bits_limit* parameters allow bounding the degree and working precision.
    The function returns 1 on success and 0 on failure indicating that
    such a limit has been exceeded.
    Setting nonpositive values for the limits removes the restrictions;
    however, the function can still fail and return 0 in that case if `g`
    exceeds machine size.

Note: to compute algebraic number roots of polynomials of various other
types, use :func:`gr_poly_roots_other`.

Roots of unity and trigonometric functions
-------------------------------------------------------------------------------

The following functions use word-size integers *p* and *q*
instead of *fmpq_t* instances to express rational numbers.
This is to emphasize that
the computations are feasible only with small *q* in this representation
of algebraic numbers since the
associated minimal polynomials have degree `O(q)`.
The input *p* and *q* do not need to be reduced *a priori*,
but should not be close to the word boundaries (they may be added
and subtracted internally).

.. function:: void qqbar_root_of_unity(qqbar_t res, slong p, ulong q)

    Sets *res* to the root of unity `e^{2 \pi i p / q}`.

.. function:: int qqbar_is_root_of_unity(slong * p, ulong * q, const qqbar_t x)

    If *x* is not a root of unity, returns 0.
    If *x* is a root of unity, returns 1.
    If *p* and *q* are not *NULL* and *x* is a root of unity,
    this also sets *p* and *q* to the minimal integers with `0 \le p < q`
    such that `x = e^{2 \pi i p / q}`.

.. function:: void qqbar_exp_pi_i(qqbar_t res, slong p, ulong q)

    Sets *res* to the root of unity `e^{\pi i p / q}`.

.. function:: void qqbar_cos_pi(qqbar_t res, slong p, ulong q)
              void qqbar_sin_pi(qqbar_t res, slong p, ulong q)
              int qqbar_tan_pi(qqbar_t res, slong p, ulong q)
              int qqbar_cot_pi(qqbar_t res, slong p, ulong q)
              int qqbar_sec_pi(qqbar_t res, slong p, ulong q)
              int qqbar_csc_pi(qqbar_t res, slong p, ulong q)

    Sets *res* to the trigonometric function `\cos(\pi x)`,
    `\sin(\pi x)`, etc., with `x = \tfrac{p}{q}`.
    The functions tan, cot, sec and csc return the flag 1 if the value exists,
    and return 0 if the evaluation point is a pole of the function.

.. function:: int qqbar_log_pi_i(slong * p, ulong * q, const qqbar_t x)

    If `y = \operatorname{log}(x) / (\pi i)` is algebraic, and hence
    necessarily rational, sets `y = p / q` to the reduced such
    fraction with `-1 < y \le 1` and returns 1.
    If *y* is not algebraic, returns 0.

.. function:: int qqbar_atan_pi(slong * p, ulong * q, const qqbar_t x)

    If `y = \operatorname{atan}(x) / \pi` is algebraic, and hence
    necessarily rational, sets `y = p / q` to the reduced such
    fraction with `|y| < \tfrac{1}{2}` and returns 1.
    If *y* is not algebraic, returns 0.

.. function:: int qqbar_asin_pi(slong * p, ulong * q, const qqbar_t x)

    If `y = \operatorname{asin}(x) / \pi` is algebraic, and hence
    necessarily rational, sets `y = p / q` to the reduced such
    fraction with `|y| \le \tfrac{1}{2}` and returns 1.
    If *y* is not algebraic, returns 0.

.. function:: int qqbar_acos_pi(slong * p, ulong * q, const qqbar_t x)

    If `y = \operatorname{acos}(x) / \pi` is algebraic, and hence
    necessarily rational, sets `y = p / q` to the reduced such
    fraction with `0 \le y \le 1` and returns 1.
    If *y* is not algebraic, returns 0.

.. function:: int qqbar_acot_pi(slong * p, ulong * q, const qqbar_t x)

    If `y = \operatorname{acot}(x) / \pi` is algebraic, and hence
    necessarily rational, sets `y = p / q` to the reduced such
    fraction with `-\tfrac{1}{2} < y \le \tfrac{1}{2}` and returns 1.
    If *y* is not algebraic, returns 0.

.. function:: int qqbar_asec_pi(slong * p, ulong * q, const qqbar_t x)

    If `y = \operatorname{asec}(x) / \pi` is algebraic, and hence
    necessarily rational, sets `y = p / q` to the reduced such
    fraction with `0 \le y \le 1` and returns 1.
    If *y* is not algebraic, returns 0.

.. function:: int qqbar_acsc_pi(slong * p, ulong * q, const qqbar_t x)

    If `y = \operatorname{acsc}(x) / \pi` is algebraic, and hence
    necessarily rational, sets `y = p / q` to the reduced such
    fraction with `-\tfrac{1}{2} \le y \le \tfrac{1}{2}` and returns 1.
    If *y* is not algebraic, returns 0.


Guessing and simplification
-------------------------------------------------------------------------------

.. function:: int qqbar_guess(qqbar_t res, const acb_t z, slong max_deg, slong max_bits, int flags, slong prec)

    Attempts to find an algebraic number *res* of degree at most *max_deg* and
    height at most *max_bits* bits matching the numerical enclosure *z*.
    The return flag indicates success.
    This is only a heuristic method, and the return flag neither implies a
    rigorous proof that *res* is the correct result, nor a rigorous proof
    that no suitable algebraic number with the given *max_deg* and *max_bits*
    exists. (Proof of nonexistence could in principle be computed,
    but this is not yet implemented.)

    The working precision *prec* should normally be the same as the precision
    used to compute *z*. It does not make much sense to run this algorithm
    with precision smaller than O(*max_deg* · *max_bits*).

    This function does a single iteration at the target *max_deg*, *max_bits*,
    and *prec*. For best performance, one should invoke this function
    repeatedly with successively larger parameters when the size of the
    intended solution is unknown or may be much smaller than a worst-case bound.

.. function:: int qqbar_express_in_field(fmpq_poly_t res, const qqbar_t alpha, const qqbar_t x, slong max_bits, int flags, slong prec)

    Attempts to express *x* in the number field generated by *alpha*, returning
    success (0 or 1). On success, *res* is set to a polynomial *f* of degree
    less than the degree of *alpha* and with height (counting both the numerator
    and the denominator, when the coefficients of *g* are
    put on a common denominator) bounded by *max_bits* bits, such that
    `f(\alpha) = x`.

    (Exception: the *max_bits* parameter is currently ignored if *x* is
    rational, in which case *res* is just set to the value of *x*.)

    This function looks for a linear relation heuristically using a working
    precision of *prec* bits. If *x* is expressible in terms of *alpha*,
    then this function is guaranteed to succeed when *prec* is taken
    large enough. The identity `f(\alpha) = x` is checked
    rigorously, i.e. a return value of 1 implies a proof of correctness.
    In principle, choosing a sufficiently large *prec* can be used to
    prove that *x* does not lie in the field generated by *alpha*,
    but the present implementation does not support doing so automatically.

    This function does a single iteration at the target *max_bits* and
    and *prec*. For best performance, one should invoke this function
    repeatedly with successively larger parameters when the size of the
    intended solution is unknown or may be much smaller than a worst-case bound.


Symbolic expressions and conversion to radicals
-------------------------------------------------------------------------------

.. function:: void qqbar_get_quadratic(fmpz_t a, fmpz_t b, fmpz_t c, fmpz_t q, const qqbar_t x, int factoring)

    Assuming that *x* has degree 1 or 2, computes integers *a*, *b*, *c*
    and *q* such that

        .. math::

            x = \frac{a + b \sqrt{c}}{q}

    and such that *c* is not a perfect square, *q* is positive, and
    *q* has no content in common with both *a* and *b*. In other words,
    this determines a quadratic field `\mathbb{Q}(\sqrt{c})` containing
    *x*, and then finds the canonical reduced coefficients *a*, *b* and
    *q* expressing *x* in this field.
    For convenience, this function supports rational *x*,
    for which *b* and *c* will both be set to zero.
    The following remarks apply to irrationals.

    The radicand *c* will not be a perfect square, but will not
    automatically be squarefree since this would require factoring the
    discriminant. As a special case, *c* will be set to `-1` if *x*
    is a Gaussian rational number. Otherwise, behavior is controlled
    by the *factoring* parameter.

    * If *factoring* is 0, no factorization is performed apart from
      removing powers of two.

    * If *factoring* is 1, a complete factorization is performed (*c*
      will be minimal). This can be very expensive if the discriminant
      is large.

    * If *factoring* is 2, a smooth factorization is performed to remove
      small factors from *c*. This is a tradeoff that provides pretty
      output in most cases while avoiding extreme worst-case slowdown.
      The smooth factorization guarantees finding all small factors
      (up to some trial division limit determined internally by FLINT),
      but large factors are only found heuristically.

.. function:: int qqbar_set_fexpr(qqbar_t res, const fexpr_t expr)

    Sets *res* to the algebraic number represented by the symbolic
    expression *expr*, returning 1 on success and 0 on failure.

    This function performs a "static" evaluation using *qqbar* arithmetic,
    supporting only closed-form expressions with explicitly algebraic
    subexpressions. It can be used to recover values generated by
    :func:`qqbar_get_expr_formula` and variants.
    For evaluating more complex expressions involving other
    types of values or requiring symbolic simplifications,
    the user should preprocess *expr* so that it is in a form
    which can be parsed by :func:`qqbar_set_fexpr`.

    The following expressions are supported:

    * Integer constants
    * Arithmetic operations with algebraic operands
    * Square roots of algebraic numbers
    * Powers with algebraic base and exponent an explicit rational number
    * NumberI, GoldenRatio, RootOfUnity
    * Floor, Ceil, Abs, Sign, Csgn, Conjugate, Re, Im, Max, Min
    * Trigonometric functions with argument an explicit rational number times Pi
    * Exponentials with argument an explicit rational number times Pi * NumberI
    * The Decimal() constructor
    * AlgebraicNumberSerialized() (assuming valid data, which is not checked)
    * PolynomialRootIndexed()
    * PolynomialRootNearest()

    Examples of formulas that are not supported, despite the value being
    an algebraic number:

    * ``Pi - Pi``                 (general transcendental simplifications are not performed)
    * ``1 / Infinity``            (only numbers are handled)
    * ``Sum(n, For(n, 1, 10))``   (only static evaluation is performed)


.. function:: void qqbar_get_fexpr_repr(fexpr_t res, const qqbar_t x)

    Sets *res* to a symbolic expression reflecting the exact internal
    representation of *x*. The output will have the form
    ``AlgebraicNumberSerialized(List(coeffs), enclosure)``.
    The output can be converted back to a ``qqbar_t`` value using
    :func:`qqbar_set_fexpr`. This is the recommended format for
    serializing algebraic numbers as it requires minimal computation,
    but it has the disadvantage of not being human-readable.

.. function:: void qqbar_get_fexpr_root_nearest(fexpr_t res, const qqbar_t x)

    Sets *res* to a symbolic expression unambiguously describing *x*
    in the form ``PolynomialRootNearest(List(coeffs), point)``
    where *point* is an approximation of *x* guaranteed to be closer
    to *x* than any conjugate root.
    The output can be converted back to a ``qqbar_t`` value using
    :func:`qqbar_set_fexpr`. This is a useful format for human-readable
    presentation, but serialization and deserialization can be expensive.

.. function:: void qqbar_get_fexpr_root_indexed(fexpr_t res, const qqbar_t x)

    Sets *res* to a symbolic expression unambiguously describing *x*
    in the form ``PolynomialRootIndexed(List(coeffs), index)``
    where *index* is the index of *x* among its conjugate roots
    in the builtin root sort order.
    The output can be converted back to a ``qqbar_t`` value using
    :func:`qqbar_set_fexpr`. This is a useful format for human-readable
    presentation when the numerical value is important, but serialization
    and deserialization can be expensive.

.. function:: int qqbar_get_fexpr_formula(fexpr_t res, const qqbar_t x, ulong flags)

    Attempts to express the algebraic number *x* as a closed-form expression
    using arithmetic operations, radicals, and possibly exponentials
    or trigonometric functions, but without using ``PolynomialRootNearest``
    or ``PolynomialRootIndexed``.
    Returns 0 on failure and 1 on success.

    The *flags* parameter toggles different methods for generating formulas.
    It can be set to any combination of the following. If *flags* is 0,
    only rational numbers will be handled.

    .. macro:: QQBAR_FORMULA_ALL

        Toggles all methods (potentially expensive).

    .. macro:: QQBAR_FORMULA_GAUSSIANS

        Detect Gaussian rational numbers `a + bi`.

    .. macro:: QQBAR_FORMULA_QUADRATICS

        Solve quadratics in the form `a + b \sqrt{d}`.

    .. macro:: QQBAR_FORMULA_CYCLOTOMICS

        Detect elements of cyclotomic fields. This works by trying plausible
        cyclotomic fields (based on the degree of the input), using LLL
        to find candidate number field elements, and certifying candidates
        through an exact computation. Detection is heuristic and
        is not guaranteed to find all cyclotomic numbers.

    .. macro:: QQBAR_FORMULA_CUBICS
               QQBAR_FORMULA_QUARTICS
               QQBAR_FORMULA_QUINTICS

        Solve polynomials of degree 3, 4 and (where applicable) 5 using
        cubic, quartic and quintic formulas (not yet implemented).

    .. macro:: QQBAR_FORMULA_DEPRESSION

        Use depression to try to generate simpler numbers.

    .. macro:: QQBAR_FORMULA_DEFLATION

        Use deflation to try to generate simpler numbers.
        This allows handling number of the form `a^{1/n}` where *a* can
        be represented in closed form.

    .. macro:: QQBAR_FORMULA_SEPARATION

        Try separating real and imaginary parts or sign and magnitude of
        complex numbers. This allows handling numbers of the form `a + bi`
        or `m \cdot s` (with `m > 0, |s| = 1`) where *a* and *b* or *m* and *s* can be
        represented in closed form. This is only attempted as a fallback after
        other methods fail: if an explicit Cartesian or magnitude-sign
        represented is desired, the user should manually separate the number
        into complex parts before calling :func:`qqbar_get_fexpr_formula`.

    .. macro:: QQBAR_FORMULA_EXP_FORM
               QQBAR_FORMULA_TRIG_FORM
               QQBAR_FORMULA_RADICAL_FORM
               QQBAR_FORMULA_AUTO_FORM

        Select output form for cyclotomic numbers. The *auto* form (equivalent
        to no flags being set) results in radicals for numbers of low degree,
        trigonometric functions for real numbers, and complex exponentials
        for nonreal numbers. The other flags (not fully implemented) can be
        used to force exponential form, trigonometric form, or radical form.

Internal functions
-------------------------------------------------------------------------------

.. function:: void qqbar_fmpz_poly_composed_op(fmpz_poly_t res, const fmpz_poly_t A, const fmpz_poly_t B, int op)

    Given nonconstant polynomials *A* and *B*, sets *res* to a polynomial
    whose roots are `a+b`, `a-b`, `ab` or `a/b` for all roots *a* of *A*
    and all roots *b* of *B*. The parameter *op* selects the arithmetic
    operation: 0 for addition, 1 for subtraction, 2 for multiplication
    and 3 for division. If *op* is 3, *B* must not have zero as a root.

.. function:: void qqbar_binary_op(qqbar_t res, const qqbar_t x, const qqbar_t y, int op)

    Performs a binary operation using a generic algorithm. This does not
    check for special cases.

.. function:: int _qqbar_validate_uniqueness(acb_t res, const fmpz_poly_t poly, const acb_t z, slong max_prec)

    Given *z* known to be an enclosure of at least one root of *poly*,
    certifies that the enclosure contains a unique root, and in that
    case sets *res* to a new (possibly improved) enclosure for the same
    root, returning 1. Returns 0 if uniqueness cannot be certified.

    The enclosure is validated by performing a single step with the
    interval Newton method. The working precision is determined from the
    accuracy of *z*, but limited by *max_prec* bits.

    This method slightly inflates the enclosure *z* to improve the chances
    that the interval Newton step will succeed. Uniqueness on this larger
    interval implies uniqueness of the original interval, but not
    existence; when existence has not been ensured a priori,
    :func:`_qqbar_validate_existence_uniqueness` should be used instead.

.. function:: int _qqbar_validate_existence_uniqueness(acb_t res, const fmpz_poly_t poly, const acb_t z, slong max_prec)

    Given any complex interval *z*, certifies that the enclosure contains a
    unique root of *poly*, and in that case sets *res* to a new (possibly
    improved) enclosure for the same root, returning 1. Returns 0 if
    existence and uniqueness cannot be certified.

    The enclosure is validated by performing a single step with the
    interval Newton method. The working precision is determined from the
    accuracy of *z*, but limited by *max_prec* bits.

.. function:: void _qqbar_enclosure_raw(acb_t res, const fmpz_poly_t poly, const acb_t z, slong prec)
              void qqbar_enclosure_raw(acb_t res, const qqbar_t x, slong prec)

    Sets *res* to an enclosure of *x* accurate to about *prec* bits
    (the actual accuracy can be slightly lower, or higher).

    This function uses repeated interval Newton steps to polish the initial
    enclosure *z*, doubling the working precision each time. If any step
    fails to improve the accuracy significantly, the root is recomputed
    from scratch to higher precision.

    If the initial enclosure is accurate enough, *res* is set to this value
    without rounding and without further computation.

.. function:: int _qqbar_acb_lindep(fmpz * rel, acb_srcptr vec, slong len, int check, slong prec)

    Attempts to find an integer vector *rel* giving a linear relation between
    the elements of the real or complex vector *vec*, using the LLL algorithm.

    The working precision is set to the minimum of *prec* and the relative
    accuracy of *vec* (that is, the difference between the largest magnitude
    and the largest error magnitude within *vec*). 95% of the bits within the
    working precision are used for the LLL matrix, and the remaining 5% bits
    are used to validate the linear relation by evaluating the linear
    combination and checking that the resulting interval contains zero.
    This validation does not prove the existence or nonexistence
    of a linear relation, but it provides a quick heuristic way to eliminate
    spurious relations.

    If *check* is set, the return value indicates whether the validation
    was successful; otherwise, the return value simply indicates whether
    the algorithm was executed normally (failure may occur, for example,
    if the input vector is non-finite).

    In principle, this method can be used to produce a proof that no linear
    relation exists with coefficients up to a specified bit size, but this has
    not yet been implemented.


.. raw:: latex

    \newpage