Data.Number.Flint.NF.QQbar

Algebraic numbers

A QQbar 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 QQbar 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 CA type in a fixed number field. The QQbar type is used internally by the CA type to represent the embedding of number fields in \(\mathbb{R}\) or \(\mathbb{C}\) and to decide predicates for algebraic numbers.

Algebraic numbers represented by minimal polynomials

Types

data QQbar

Constructors

QQbar !(ForeignPtr CQQbar)

Instances

Storable CQQbar

Defined in Data.Number.Flint.NF.QQbar.FFI

Methods

sizeOf :: CQQbar -> Int

alignment :: CQQbar -> Int

peekElemOff :: Ptr CQQbar -> Int -> IO CQQbar

pokeElemOff :: Ptr CQQbar -> Int -> CQQbar -> IO ()

peekByteOff :: Ptr b -> Int -> IO CQQbar

pokeByteOff :: Ptr b -> Int -> CQQbar -> IO ()

peek :: Ptr CQQbar -> IO CQQbar

poke :: Ptr CQQbar -> CQQbar -> IO ()

Num QQbar

Defined in Data.Number.Flint.NF.QQbar.Instances

Methods

(+) :: QQbar -> QQbar -> QQbar

(-) :: QQbar -> QQbar -> QQbar

(*) :: QQbar -> QQbar -> QQbar

negate :: QQbar -> QQbar

abs :: QQbar -> QQbar

signum :: QQbar -> QQbar

fromInteger :: Integer -> QQbar

Show QQbar

Defined in Data.Number.Flint.NF.QQbar.Instances

Methods

showsPrec :: Int -> QQbar -> ShowS

show :: QQbar -> String

showList :: [QQbar] -> ShowS

Eq QQbar

Defined in Data.Number.Flint.NF.QQbar.Instances

Methods

(==) :: QQbar -> QQbar -> Bool

(/=) :: QQbar -> QQbar -> Bool

type CQQbar = CFlint QQbar

newQQbar :: IO QQbar

Create a QQbar.

newQQbarFromFmpz :: Fmpz -> IO QQbar

Create a QQbar from Fmpz.

newQQbarFromFmpq :: Fmpq -> IO QQbar

Create a QQbar from Fmpq.

newQQbarFromDouble :: Real a => a -> IO QQbar

Create a QQbar from Double.

withQQbar :: QQbar -> (Ptr CQQbar -> IO a) -> IO (QQbar, a)

Use QQbar in f.

withNewQQbar :: (Ptr CQQbar -> IO a) -> IO (QQbar, a)

Apply f to new QQbar.

Memory management

_qqbar_vec_init :: CLong -> IO (Ptr CQQbar)

_qqbar_vec_init len

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

_qqbar_vec_clear :: Ptr CQQbar -> CLong -> IO ()

_qqbar_vec_clear vec len

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

Assignment

qqbar_swap :: Ptr CQQbar -> Ptr CQQbar -> IO ()

qqbar_swap x y

Swaps the values of x and y efficiently.

qqbar_set :: Ptr CQQbar -> Ptr CQQbar -> IO ()

qqbar_set res x

qqbar_set_si :: Ptr CQQbar -> CLong -> IO ()

qqbar_set_si res x

qqbar_set_ui :: Ptr CQQbar -> CULong -> IO ()

qqbar_set_ui res x

qqbar_set_fmpz :: Ptr CQQbar -> Ptr CFmpz -> IO ()

qqbar_set_fmpz res x

qqbar_set_fmpq :: Ptr CQQbar -> Ptr CFmpq -> IO ()

qqbar_set_fmpq res x

Sets res to the value x.

qqbar_set_re_im :: Ptr CQQbar -> Ptr CQQbar -> Ptr CQQbar -> IO ()

qqbar_set_re_im res x y

Sets res to the value \(x + yi\).

qqbar_set_d :: Ptr CQQbar -> CDouble -> IO CInt

qqbar_set_d res x

qqbar_set_re_im_d :: Ptr CQQbar -> CDouble -> CDouble -> IO CInt

qqbar_set_re_im_d res x 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

qqbar_degree :: Ptr CQQbar -> IO CLong

qqbar_degree x

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

qqbar_is_rational :: Ptr CQQbar -> IO CInt

qqbar_is_rational x

Returns whether x is a rational number.

qqbar_is_integer :: Ptr CQQbar -> IO CInt

qqbar_is_integer x

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

qqbar_is_algebraic_integer :: Ptr CQQbar -> IO CInt

qqbar_is_algebraic_integer x

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

qqbar_is_zero :: Ptr CQQbar -> IO CInt

qqbar_is_zero x

qqbar_is_one :: Ptr CQQbar -> IO CInt

qqbar_is_one x

qqbar_is_neg_one :: Ptr CQQbar -> IO CInt

qqbar_is_neg_one x

Returns whether x is the number \(0\), \(1\), \(-1\).

qqbar_is_i :: Ptr CQQbar -> IO CInt

qqbar_is_i x

qqbar_is_neg_i :: Ptr CQQbar -> IO CInt

qqbar_is_neg_i x

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

qqbar_is_real :: Ptr CQQbar -> IO CInt

qqbar_is_real x

Returns whether x is a real number.

qqbar_height :: Ptr CFmpz -> Ptr CQQbar -> IO ()

qqbar_height res x

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

qqbar_height_bits :: Ptr CQQbar -> IO CLong

qqbar_height_bits x

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

qqbar_within_limits :: Ptr CQQbar -> CLong -> CLong -> IO CInt

qqbar_within_limits x deg_limit 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.

qqbar_binop_within_limits :: Ptr CQQbar -> Ptr CQQbar -> CLong -> CLong -> IO CInt

qqbar_binop_within_limits x y deg_limit 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

_qqbar_get_fmpq :: Ptr CFmpz -> Ptr CFmpz -> Ptr CQQbar -> IO ()

_qqbar_get_fmpq num den x

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

qqbar_get_fmpq :: Ptr CFmpq -> Ptr CQQbar -> IO ()

qqbar_get_fmpq res x

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

qqbar_get_fmpz :: Ptr CFmpz -> Ptr CQQbar -> IO ()

qqbar_get_fmpz res x

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

Special values

qqbar_zero :: Ptr CQQbar -> IO ()

qqbar_zero res

Sets res to the number 0.

qqbar_one :: Ptr CQQbar -> IO ()

qqbar_one res

Sets res to the number 1.

qqbar_i :: Ptr CQQbar -> IO ()

qqbar_i res

Sets res to the imaginary unit \(i\).

qqbar_phi :: Ptr CQQbar -> IO ()

qqbar_phi res

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

Input and output

qqbar_get_str :: Ptr CQQbar -> IO CString

qqbar_get_strn :: Ptr CQQbar -> CLong -> IO CString

qqbar_get_strnd :: Ptr CQQbar -> CLong -> IO CString

qqbar_print :: Ptr CQQbar -> IO ()

qqbar_print 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.

qqbar_printn :: Ptr CQQbar -> CLong -> IO ()

qqbar_printn x n

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

qqbar_printnd :: Ptr CQQbar -> CLong -> IO ()

qqbar_printnd x n

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

Random generation

qqbar_randtest :: Ptr CQQbar -> Ptr CFRandState -> CLong -> CLong -> IO ()

qqbar_randtest res state deg bits

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

qqbar_randtest_real :: Ptr CQQbar -> Ptr CFRandState -> CLong -> CLong -> IO ()

qqbar_randtest_real res state deg bits

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

qqbar_randtest_nonreal :: Ptr CQQbar -> Ptr CFRandState -> CLong -> CLong -> IO ()

qqbar_randtest_nonreal res state deg 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

qqbar_equal :: Ptr CQQbar -> Ptr CQQbar -> IO CInt

qqbar_equal x y

Returns whether x and y are equal.

qqbar_equal_fmpq_poly_val :: Ptr CQQbar -> Ptr CFmpqPoly -> Ptr CQQbar -> IO CInt

qqbar_equal_fmpq_poly_val x f y

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

qqbar_cmp_re :: Ptr CQQbar -> Ptr CQQbar -> IO CInt

qqbar_cmp_re x y

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

qqbar_cmp_im :: Ptr CQQbar -> Ptr CQQbar -> IO CInt

qqbar_cmp_im x y

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

qqbar_cmpabs_re :: Ptr CQQbar -> Ptr CQQbar -> IO CInt

qqbar_cmpabs_re x y

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

qqbar_cmpabs_im :: Ptr CQQbar -> Ptr CQQbar -> IO CInt

qqbar_cmpabs_im x y

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

qqbar_cmpabs :: Ptr CQQbar -> Ptr CQQbar -> IO CInt

qqbar_cmpabs x y

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

qqbar_cmp_root_order :: Ptr CQQbar -> Ptr CQQbar -> IO CInt

qqbar_cmp_root_order x 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.

qqbar_hash :: Ptr CQQbar -> IO CULong

qqbar_hash 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

qqbar_conj :: Ptr CQQbar -> Ptr CQQbar -> IO ()

qqbar_conj res x

Sets res to the complex conjugate of x.

qqbar_re :: Ptr CQQbar -> Ptr CQQbar -> IO ()

qqbar_re res x

Sets res to the real part of x.

qqbar_im :: Ptr CQQbar -> Ptr CQQbar -> IO ()

qqbar_im res x

Sets res to the imaginary part of x.

qqbar_re_im :: Ptr CQQbar -> Ptr CQQbar -> Ptr CQQbar -> IO ()

qqbar_re_im res1 res2 x

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

qqbar_abs :: Ptr CQQbar -> Ptr CQQbar -> IO ()

qqbar_abs res x

Sets res to the absolute value of x:

qqbar_abs2 :: Ptr CQQbar -> Ptr CQQbar -> IO ()

qqbar_abs2 res x

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

qqbar_sgn :: Ptr CQQbar -> Ptr CQQbar -> IO ()

qqbar_sgn res x

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

qqbar_sgn_re :: Ptr CQQbar -> IO CInt

qqbar_sgn_re x

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

qqbar_sgn_im :: Ptr CQQbar -> IO CInt

qqbar_sgn_im x

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

qqbar_csgn :: Ptr CQQbar -> IO CInt

qqbar_csgn 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

qqbar_floor :: Ptr CFmpz -> Ptr CQQbar -> IO ()

qqbar_floor res 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.

qqbar_ceil :: Ptr CFmpz -> Ptr CQQbar -> IO ()

qqbar_ceil res 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

qqbar_neg :: Ptr CQQbar -> Ptr CQQbar -> IO ()

qqbar_neg res x

Sets res to the negation of x.

qqbar_add :: Ptr CQQbar -> Ptr CQQbar -> Ptr CQQbar -> IO ()

qqbar_add res x y

qqbar_add_fmpq :: Ptr CQQbar -> Ptr CQQbar -> Ptr CFmpq -> IO ()

qqbar_add_fmpq res x y

qqbar_add_fmpz :: Ptr CQQbar -> Ptr CQQbar -> Ptr CFmpz -> IO ()

qqbar_add_fmpz res x y

qqbar_add_ui :: Ptr CQQbar -> Ptr CQQbar -> CULong -> IO ()

qqbar_add_ui res x y

qqbar_add_si :: Ptr CQQbar -> Ptr CQQbar -> CLong -> IO ()

qqbar_add_si res x y

Sets res to the sum of x and y.

qqbar_sub :: Ptr CQQbar -> Ptr CQQbar -> Ptr CQQbar -> IO ()

qqbar_sub res x y

qqbar_sub_fmpq :: Ptr CQQbar -> Ptr CQQbar -> Ptr CFmpq -> IO ()

qqbar_sub_fmpq res x y

qqbar_sub_fmpz :: Ptr CQQbar -> Ptr CQQbar -> Ptr CFmpz -> IO ()

qqbar_sub_fmpz res x y

qqbar_sub_ui :: Ptr CQQbar -> Ptr CQQbar -> CULong -> IO ()

qqbar_sub_ui res x y

qqbar_sub_si :: Ptr CQQbar -> Ptr CQQbar -> CLong -> IO ()

qqbar_sub_si res x y

qqbar_fmpq_sub :: Ptr CQQbar -> Ptr CFmpq -> Ptr CQQbar -> IO ()

qqbar_fmpq_sub res x y

qqbar_fmpz_sub :: Ptr CQQbar -> Ptr CFmpz -> Ptr CQQbar -> IO ()

qqbar_fmpz_sub res x y

qqbar_ui_sub :: Ptr CQQbar -> CULong -> Ptr CQQbar -> IO ()

qqbar_ui_sub res x y

qqbar_si_sub :: Ptr CQQbar -> CLong -> Ptr CQQbar -> IO ()

qqbar_si_sub res x y

Sets res to the difference of x and y.

qqbar_mul :: Ptr CQQbar -> Ptr CQQbar -> Ptr CQQbar -> IO ()

qqbar_mul res x y

qqbar_mul_fmpq :: Ptr CQQbar -> Ptr CQQbar -> Ptr CFmpq -> IO ()

qqbar_mul_fmpq res x y

qqbar_mul_fmpz :: Ptr CQQbar -> Ptr CQQbar -> Ptr CFmpz -> IO ()

qqbar_mul_fmpz res x y

qqbar_mul_ui :: Ptr CQQbar -> Ptr CQQbar -> CULong -> IO ()

qqbar_mul_ui res x y

qqbar_mul_si :: Ptr CQQbar -> Ptr CQQbar -> CLong -> IO ()

qqbar_mul_si res x y

Sets res to the product of x and y.

qqbar_mul_2exp_si :: Ptr CQQbar -> Ptr CQQbar -> CLong -> IO ()

qqbar_mul_2exp_si res x e

Sets res to x multiplied by \(2^e\).

qqbar_sqr :: Ptr CQQbar -> Ptr CQQbar -> IO ()

qqbar_sqr res x

Sets res to the square of x.

qqbar_inv :: Ptr CQQbar -> Ptr CQQbar -> Ptr CQQbar -> IO ()

qqbar_inv res x y

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

qqbar_div :: Ptr CQQbar -> Ptr CQQbar -> Ptr CQQbar -> IO ()

qqbar_div res x y

qqbar_div_fmpq :: Ptr CQQbar -> Ptr CQQbar -> Ptr CFmpq -> IO ()

qqbar_div_fmpq res x y

qqbar_div_fmpz :: Ptr CQQbar -> Ptr CQQbar -> Ptr CFmpz -> IO ()

qqbar_div_fmpz res x y

qqbar_div_ui :: Ptr CQQbar -> Ptr CQQbar -> CULong -> IO ()

qqbar_div_ui res x y

qqbar_div_si :: Ptr CQQbar -> Ptr CQQbar -> CLong -> IO ()

qqbar_div_si res x y

qqbar_fmpq_div :: Ptr CQQbar -> Ptr CFmpq -> Ptr CQQbar -> IO ()

qqbar_fmpq_div res x y

qqbar_fmpz_div :: Ptr CQQbar -> Ptr CFmpz -> Ptr CQQbar -> IO ()

qqbar_fmpz_div res x y

qqbar_ui_div :: Ptr CQQbar -> CULong -> Ptr CQQbar -> IO ()

qqbar_ui_div res x y

qqbar_si_div :: Ptr CQQbar -> CLong -> Ptr CQQbar -> IO ()

qqbar_si_div res x y

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

qqbar_scalar_op :: Ptr CQQbar -> Ptr CQQbar -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> IO ()

qqbar_scalar_op res x a b 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

qqbar_sqrt :: Ptr CQQbar -> Ptr CQQbar -> IO ()

qqbar_sqrt res x

qqbar_sqrt_ui :: Ptr CQQbar -> CULong -> IO ()

qqbar_sqrt_ui res x

Sets res to the principal square root of x.

qqbar_rsqrt :: Ptr CQQbar -> Ptr CQQbar -> IO ()

qqbar_rsqrt res x

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

qqbar_pow_ui :: Ptr CQQbar -> Ptr CQQbar -> CULong -> IO ()

qqbar_pow_ui res x n

qqbar_pow_si :: Ptr CQQbar -> Ptr CQQbar -> CULong -> IO ()

qqbar_pow_si res x n

qqbar_pow_fmpz :: Ptr CQQbar -> Ptr CQQbar -> Ptr CFmpz -> IO ()

qqbar_pow_fmpz res x n

qqbar_pow_fmpq :: Ptr CQQbar -> Ptr CQQbar -> Ptr CFmpq -> IO ()

qqbar_pow_fmpq res x n

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

qqbar_root_ui :: Ptr CQQbar -> Ptr CQQbar -> CULong -> IO ()

qqbar_root_ui res x n

qqbar_fmpq_root_ui :: Ptr CQQbar -> Ptr CFmpq -> CULong -> IO ()

qqbar_fmpq_root_ui res x n

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

qqbar_fmpq_pow_si_ui :: Ptr CQQbar -> Ptr CFmpq -> CLong -> CULong -> IO ()

qqbar_fmpq_pow_si_ui res x m n

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

qqbar_pow :: Ptr CQQbar -> Ptr CQQbar -> Ptr CQQbar -> IO CInt

qqbar_pow res x 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

qqbar_get_acb :: Ptr CAcb -> Ptr CQQbar -> CLong -> IO ()

qqbar_get_acb res x prec

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

qqbar_get_arb :: Ptr CArb -> Ptr CQQbar -> CLong -> IO ()

qqbar_get_arb res x 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]\).

qqbar_get_arb_re :: Ptr CArb -> Ptr CQQbar -> CLong -> IO ()

qqbar_get_arb_re res x prec

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

qqbar_get_arb_im :: Ptr CArb -> Ptr CQQbar -> CLong -> IO ()

qqbar_get_arb_im res x prec

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

qqbar_cache_enclosure :: Ptr CQQbar -> CLong -> IO ()

qqbar_cache_enclosure res 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

qqbar_denominator :: Ptr CFmpz -> Ptr CQQbar -> IO ()

qqbar_denominator res y

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

qqbar_numerator :: Ptr CQQbar -> Ptr CQQbar -> IO ()

qqbar_numerator res y

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

Conjugates

qqbar_conjugates :: Ptr CQQbar -> Ptr CQQbar -> IO ()

qqbar_conjugates res 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 qqbar_cmp_root_order).

Polynomial evaluation

_qqbar_evaluate_fmpq_poly :: Ptr CQQbar -> Ptr CFmpz -> Ptr CFmpz -> CLong -> Ptr CQQbar -> IO ()

_qqbar_evaluate_fmpq_poly res poly den len x

qqbar_evaluate_fmpq_poly :: Ptr CQQbar -> Ptr CFmpqPoly -> Ptr CQQbar -> IO ()

qqbar_evaluate_fmpq_poly res poly x

_qqbar_evaluate_fmpz_poly :: Ptr CQQbar -> Ptr CFmpz -> CLong -> Ptr CQQbar -> IO ()

_qqbar_evaluate_fmpz_poly res poly len x

qqbar_evaluate_fmpz_poly :: Ptr CQQbar -> Ptr CFmpzPoly -> Ptr CQQbar -> IO ()

qqbar_evaluate_fmpz_poly res poly 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.

qqbar_evaluate_fmpz_mpoly_iter :: Ptr CQQbar -> Ptr CFmpzMPoly -> Ptr CQQbar -> CLong -> CLong -> Ptr CFmpzMPolyCtx -> IO CInt

qqbar_evaluate_fmpz_mpoly_iter res poly x deg_limit bits_limit ctx

qqbar_evaluate_fmpz_mpoly_horner :: Ptr CQQbar -> Ptr CFmpzMPoly -> Ptr CQQbar -> CLong -> CLong -> Ptr CFmpzMPolyCtx -> IO CInt

qqbar_evaluate_fmpz_mpoly_horner res poly x deg_limit bits_limit ctx

qqbar_evaluate_fmpz_mpoly :: Ptr CQQbar -> Ptr CFmpzMPoly -> Ptr CQQbar -> CLong -> CLong -> Ptr CFmpzMPolyCtx -> IO CInt

qqbar_evaluate_fmpz_mpoly res poly x deg_limit bits_limit 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

qqbar_roots_fmpz_poly :: Ptr CQQbar -> Ptr CFmpzPoly -> CInt -> IO ()

qqbar_roots_fmpz_poly res poly flags

qqbar_roots_fmpq_poly :: Ptr CQQbar -> Ptr CFmpqPoly -> CInt -> IO ()

qqbar_roots_fmpq_poly res poly 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 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).

qqbar_eigenvalues_fmpz_mat :: Ptr CQQbar -> Ptr CFmpzMat -> CInt -> IO ()

qqbar_eigenvalues_fmpz_mat res mat flags

qqbar_eigenvalues_fmpq_mat :: Ptr CQQbar -> Ptr CFmpqMat -> CInt -> IO ()

qqbar_eigenvalues_fmpq_mat res mat 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 qqbar_roots_fmpz_poly with the same flags.

Roots of unity and trigonometric functions

qqbar_root_of_unity :: Ptr CQQbar -> CLong -> CULong -> IO ()

qqbar_root_of_unity res p q

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

qqbar_is_root_of_unity :: Ptr CLong -> Ptr CULong -> Ptr CQQbar -> IO CInt

qqbar_is_root_of_unity p q 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}\).

qqbar_exp_pi_i :: Ptr CQQbar -> CLong -> CULong -> IO ()

qqbar_exp_pi_i res p q

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

qqbar_cos_pi :: Ptr CQQbar -> CLong -> CULong -> IO ()

qqbar_cos_pi res p q

qqbar_sin_pi :: Ptr CQQbar -> CLong -> CULong -> IO ()

qqbar_sin_pi res p q

qqbar_tan_pi :: Ptr CQQbar -> CLong -> CULong -> IO CInt

qqbar_tan_pi res p q

qqbar_cot_pi :: Ptr CQQbar -> CLong -> CULong -> IO CInt

qqbar_cot_pi res p q

qqbar_sec_pi :: Ptr CQQbar -> CLong -> CULong -> IO CInt

qqbar_sec_pi res p q

qqbar_csc_pi :: Ptr CQQbar -> CLong -> CULong -> IO CInt

qqbar_csc_pi res p 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.

qqbar_log_pi_i :: Ptr CLong -> Ptr CULong -> Ptr CQQbar -> IO CInt

qqbar_log_pi_i p q 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.

qqbar_atan_pi :: Ptr CLong -> Ptr CULong -> Ptr CQQbar -> IO CInt

qqbar_atan_pi p q 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.

qqbar_asin_pi :: Ptr CLong -> Ptr CULong -> Ptr CQQbar -> IO CInt

qqbar_asin_pi p q 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.

qqbar_acos_pi :: Ptr CLong -> Ptr CULong -> Ptr CQQbar -> IO CInt

qqbar_acos_pi p q 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.

qqbar_acot_pi :: Ptr CLong -> Ptr CULong -> Ptr CQQbar -> IO CInt

qqbar_acot_pi p q 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.

qqbar_asec_pi :: Ptr CLong -> Ptr CULong -> Ptr CQQbar -> IO CInt

qqbar_asec_pi p q 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.

qqbar_acsc_pi :: Ptr CLong -> Ptr CULong -> Ptr CQQbar -> IO CInt

qqbar_acsc_pi p q 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

qqbar_guess :: Ptr CQQbar -> Ptr CAcb -> CLong -> CLong -> CInt -> CLong -> IO CInt

qqbar_guess res z max_deg max_bits flags 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.

qqbar_express_in_field :: Ptr CFmpqPoly -> Ptr CQQbar -> Ptr CQQbar -> CLong -> CInt -> CLong -> IO CInt

qqbar_express_in_field res alpha x max_bits flags 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

qqbar_get_quadratic :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CQQbar -> CInt -> IO ()

qqbar_get_quadratic a b c q x factoring

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

\[`\] \[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.

qqbar_set_fexpr :: Ptr CQQbar -> Ptr CFExpr -> IO CInt

qqbar_set_fexpr res 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 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 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)

qqbar_get_fexpr_repr :: Ptr CFExpr -> Ptr CQQbar -> IO ()

qqbar_get_fexpr_repr res 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 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.

qqbar_get_fexpr_root_nearest :: Ptr CFExpr -> Ptr CQQbar -> IO ()

qqbar_get_fexpr_root_nearest res 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 qqbar_set_fexpr. This is a useful format for human-readable presentation, but serialization and deserialization can be expensive.

qqbar_get_fexpr_root_indexed :: Ptr CFExpr -> Ptr CQQbar -> IO ()

qqbar_get_fexpr_root_indexed res 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 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.

qqbar_get_fexpr_formula :: Ptr CFExpr -> Ptr CQQbar -> CULong -> IO CInt

qqbar_get_fexpr_formula res x 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.

QQBAR_FORMULA_ALL

Toggles all methods (potentially expensive).

QQBAR_FORMULA_GAUSSIANS

Detect Gaussian rational numbers \(a + bi\).

QQBAR_FORMULA_QUADRATICS

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

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.

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).

QQBAR_FORMULA_DEPRESSION

Use depression to try to generate simpler numbers.

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.

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 qqbar_get_fexpr_formula.

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

qqbar_fmpz_poly_composed_op :: Ptr CFmpzPoly -> Ptr CFmpzPoly -> Ptr CFmpzPoly -> CInt -> IO ()

qqbar_fmpz_poly_composed_op res A B 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.

qqbar_binary_op :: Ptr CQQbar -> Ptr CQQbar -> Ptr CQQbar -> CInt -> IO ()

qqbar_binary_op res x y op

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

_qqbar_validate_uniqueness :: Ptr CAcb -> Ptr CFmpzPoly -> Ptr CAcb -> CLong -> IO CInt

_qqbar_validate_uniqueness res poly z 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, _qqbar_validate_existence_uniqueness should be used instead.

_qqbar_validate_existence_uniqueness :: Ptr CAcb -> Ptr CFmpzPoly -> Ptr CAcb -> CLong -> IO CInt

_qqbar_validate_existence_uniqueness res poly z 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.

_qqbar_enclosure_raw :: Ptr CAcb -> Ptr CFmpzPoly -> Ptr CAcb -> CLong -> IO ()

_qqbar_enclosure_raw res poly z prec

qqbar_enclosure_raw :: Ptr CAcb -> Ptr CQQbar -> CLong -> IO ()

qqbar_enclosure_raw res x 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.

_qqbar_acb_lindep :: Ptr CFmpz -> Ptr CAcb -> CLong -> CInt -> CLong -> IO CInt

_qqbar_acb_lindep rel vec len check 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.