FLINT3.7.0-dev
/
Overview

Choosing a representation for exact numbers

An exact number is one that is represented symbolically, so that the value is determined without error and can be approximated to any precision. FLINT has four exact representations of increasing generality, and they differ less in what they can express than in what they can decide: whether two numbers are equal, whether a number is real, positive or rational. The more general the representation, the more expensive arithmetic becomes and the weaker the guarantees.

The representations#

RepresentationNumbersElement stored asEqualityTypical cost
fmpq\mathbb{Q}reduced fractioncanonicalquasi-linear in the bit size
nf_elem.ha fixed number field \mathbb{Q}(a)polynomial in a of degree less than [\mathbb{Q}(a) : \mathbb{Q}]canonicalpolynomial arithmetic modulo the defining polynomial
qqbar.h\overline{\mathbb{Q}}minimal polynomial and isolating balldecidableresultants and factorisation; degrees multiply
ca.hreal and complex numbers built from \mathbb{Q} by arithmetic, roots, \exp, \log, \pi, trigonometric and some special functionselement of a formal field \mathbb{Q}(a_1, \ldots, a_n) reduced modulo proved relationssemi-decidable: answers may be unknownmultivariate rational functions, relation searches, numerical evaluation

The two exact algebraic representations behave very differently. A nf_elem.h is cheap, but all numbers must belong to one field fixed in advance, which is not always known and whose degree can be large. A qqbar.h number carries its own minimal polynomial, so any two algebraic numbers can be combined; arithmetic is self-contained and canonical, but an operation may need a resultant and its factorisation, and the degree of the result can be as large as the degree of the compositum, so long computations become expensive (see Arithmetic with algebraic numbers).

A ca.h number represents its value as an element of a formal field whose generators are algebraic numbers or transcendental extension numbers such as \pi, e^{\sqrt 2} or \log 3. Field arithmetic is formal and cheap compared with resultants, several algebraic generators can coexist without computing a primitive element, and transcendental numbers can be represented at all. The price is that equality is not canonical: a zero test combines numerical evaluation with exact reductions and can fail (see Zero testing). When all generators are algebraic, ca can fall back on qqbar.h and decide equality, within the degree limit CA_OPT_QQBAR_DEG_LIMIT.

The gr.h interface provides contexts for all of them (see Number fields and algebraic numbers and Real and complex numbers): qqbar through gr_ctx_init_real_qqbar and gr_ctx_init_complex_qqbar, and ca through gr_ctx_init_real_ca, gr_ctx_init_complex_ca, their algebraic variants and gr_ctx_init_complex_extended_ca. Generic polynomial and matrix algorithms then work over exact numbers and return GR_UNABLE when a zero test fails. Symbolic expressions (fexpr.h) are not numbers but trees; they are used to construct, print and convert exact numbers.

Which algorithm is used#

TaskMethodFunctions
Create an algebraic numberfactor the defining polynomial, isolate the roots, certify with interval Newtonqqbar_roots_fmpz_poly; Creating algebraic numbers
Refine an enclosurecertified Newton iteration, recomputation of all roots as fallbackqqbar_get_acb, qqbar_cache_enclosure; Refining an enclosure
Compare algebraic numbersminimal polynomials, then enclosuresqqbar_equal, qqbar_cmp_re; Deciding predicates
Add or multiply algebraic numbersclosed forms for quadratics, subfield and cyclotomic detection, guessing with proof, composed polynomials and factor selectionqqbar_add, qqbar_mul, qqbar_binary_op; Arithmetic with algebraic numbers
Create a field with given generatorsideal of relations: minimal polynomials, logarithmic and multiplicative relations, Gröbner basisca_field_build_ideal; Formal fields and the ideal of relations
Arithmetic in caformal arithmetic in the common field of the operands, reduction modulo the idealca_add, ca_mul, ca_merge_fields; Formal fields and the ideal of relations
Decide x = 0numerical evaluation, algebraic evaluation, normal form rewriting, factoringca_check_is_zero (Zero tests and equality); Zero testing
Simplify, recognise closed formscanonical number field forms, rewriting rules, LLL with exact verificationca_condense_field, qqbar_guess, qqbar_get_fexpr_formula; Simplification and closed forms
Roots of polynomialssquarefree factorisation, rational factors via qqbar.h, formulas up to degree 3ca_poly_roots (Roots and squarefree factorisation)
Linear algebrasimplest-first pivoting, fraction-free and division-free methods, rational and number field specialisationsca_mat_det, ca_mat_rank, ca_mat_eigenvalues; Linear algebra over exact numbers

Practical advice#

  • Use fmpq or nf_elem.h when the numbers are known to lie in \mathbb{Q} or in one known number field: arithmetic is much faster than with qqbar or ca.
  • Use qqbar.h for algebraic numbers when exact answers to all predicates are required and degrees stay moderate. Computations whose intermediate degrees explode, such as sums of many square roots, can be cheaper in ca.h, which keeps them in a field with several quadratic generators.
  • Use ca.h whenever transcendental numbers occur, and check the truth_t results of predicates: T_UNKNOWN is a legitimate answer. The options of the context (see Context options) bound the work spent on zero tests and relation searches.
  • For numerical values only, arb.h and acb.h are much faster; ca_get_acb and qqbar_get_acb convert exact numbers to balls of any precision.

Referenced from#

Cite this page

The FLINT team, “Choosing a representation for exact numbers,” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/algorithms/exact/overview.html (generated 2026-10-20).