## Features

FLINT is a collection of modules, with an interface
similar to that of the GMP library.
For example, the FLINT `fmpz_poly` module defines
the `fmpz_poly_t` type (representing a polynomial with multiprecision integer coefficients)
and provides methods such as `fmpz_poly_add`, `fmpz_poly_gcd`, etc.

### FLINT modules

The following is a list of modules available in FLINT version 2.6, and a summary of the features and algorithms in each module. Besides the features listed explicitly, each module implementing a specific type also provides methods for arithmetic operations (add, sub, mul and so on), conversions between types, random generation, and printing. Some utility modules are omitted from the list.

Extensive documentation is available. What follows is an executive summary.

#### flintxx - C++ wrapper

- Provides an object-oriented interface with operator overloading
- Exposes most of the FLINT C functions
- Uses C++98 expression templates to avoid temporary allocations and assignments, usually giving the same performance as hand-written C code

#### ulong_extras - functions for word-size integers

- Functions work with unsigned integers all the way up to 32/64 bits
- Division and modular arithmetic using precomputed inverses
- Random number generation
- Memory-efficient generation of primes (block sieve of Eratosthenes)
- Fast factorisation (trial division, Hart's one line algorithm, SQUFOF)
- Fast primality proving (verified BPSW test, Pocklington, pseudosquare)
- Probable prime tests (BPSW, Fermat, Fibonacci, Lucas)
- Square roots and modular square roots
- Number-theoretic functions (GCD, Jacobi symbol, Euler phi, etc.)
- Fast cube and nth root computation

#### qsieve - small quadratic field

- Efficient factorisation of integers up to two words (64 or 128 bits)

#### fft - optimised Schönhage-Strassen FFT

- Cache friendly up to huge transforms (integers of billions of bits)
- Truncated -- no uglytwit performance jumps at power of 2 lengths and no problem with unbalanced multiplications
- Truncated FFT/IFFT functions can be used for polynomial multiplication
- Extremely fast (up to 30% faster than MPIR 2.4.0 and 70% faster than GMP 5.0.2 on a 2.2GHz AMD K10-2)
- Easy to tune
- This module is BSD licensed

#### fmpz - multiprecision integers

- Tagged pointer representation, with integers up to 30 or 62 bits only using a single word and not requiring heap allocation
- Caches larger integers for fast allocation and deallocation
- Very efficient for small integers, and similar performance to the mpz type for large numbers
- GCD, XGCD, LCM, Jacobi symbol, modular inverse, modular square roots
- Factorials, Fibonacci numbers, binomial coefficients, rising factorials
- Asymptotically fast multimodular reduction and Chinese remaindering via subproduct trees
- Pseudosquare primality test
- Primality testing (Pocklington, Morrison)
- Probable primality testing (Lucas, Baillie-PSW, strong-psp, Brillhart-Lehmer-Selfridge)

#### fmpz_factor - factoring multiprecision integers

- Factors 32/64-bit integers quickly via ulong_extras
- Trial division
- Williams' p + 1 method
- ECM
- Self initialising, large prime variant quadratic sieve

#### fmpz_mat - dense matrices over the integers

- Classical and multimodular multiplication
- Fast nonsingular solving (fraction-free, Dixon p-adic lifting)
- Fast determinants (fraction-free, multimodular)
- Reduced row echelon form, nullspace, inverse (fraction-free)
- Characteristic polynomial
- Hermite normal form (naive, xgcd, Domich-Kannan-Trotter, Kannen-Bachem, Pernet-Stein)
- Smith normal form (diagonal, Kannen-Bachem, Iliopoulos)

#### fmpz_lll - LLL

- LLL (rational, Nguyen-Stehle, from Gram matrix, with_removal, Storjohann/ULLL)

#### fmpz_mod_poly - dense univariate polynomials over Z/nZ for multiprecision n

- Fast arithmetic based on the fmpz_poly module
- Divide-and-conquer division and composition
- GCD and XGCD (Euclidean, half GCD)
- Fast modular composition (Brent-Kung)
- Fast multipoint evaluation

#### fmpz_mod_poly_factor - factoring in (Z/nZ)[x] for multiprecision n

- Berlekamp, Cantor-Zassenhaus, Kaltofen-Shoup algorithms
- Squarefree, distinct-degree and equal-degree factorisation

#### fmpz_mod_mat - matrices over Z/nZ for multiprecision n

- Basic arithmetic

#### fmpz_poly - dense univariate polynomials over the integers

- Embarrassingly fast multiplication (classical, Karatsuba, Kronecker substitution, Schönhage-Strassen)
- Efficient truncated products (power series multiplication)
- Evaluation and composition (Horner, divide-and-conquer)
- Basecase and divide-and-conquer division and pseudodivision
- Power series composition (Brent-Kung) and reversion (fast Lagrange)
- Powering (binary algorithm, multinomial coefficients)
- Taylor shift (basecase, divide-and-conquer)
- GCD and XGCD (heuristic, multimodular), resultants
- Restartable Hensel lifting
- Interpolation, Chinese remaindering, bit packing

#### fmpz_poly_factor - factoring in Z[x]

- Squarefree factorisation
- Zassenhaus algorithm

#### fmpz_poly_mat - matrices over Z[x]

- Multiplication (classical, Kronecker substitution)
- Determinants (fraction-free, interpolation)
- Reduced row echelon form, nullspace, inverse (fraction-free)

#### fmpz_poly_q - rational functions over Q

- Efficient arithmetic based on the fmpz_poly module

#### fmpz_mpoly - multivariate polynomials over Z

- Efficient arithmetic for polynomials in sparse distributed form

#### fmpq - multiprecision rational numbers

- Based on the fmpz type -- efficient representation of small rational numbers, and similar performance to the mpq type for large numbers
- Rational reconstruction (balanced or unbalanced)
- Conversion from continued fraction (subquadratic) and to continued fraction
- Enumeration of the rationals (minimal height, Calkin-Wilf tree)

#### fmpq_mat - dense matrices over the rational numbers

- Efficient multiplication, determinants and nonsingular solving dona via the integers
- Reduced row echelon form (naive)

#### fmpq_poly - dense univariate polynomials over the rational numbers

- Efficient representation with a single denominator, basing most operations on the fmpz_poly module
- Fast multiplication, division, composition, powering, GCD, XGCD, LCM done via the integers
- Fast power series composition and reversion
- Functions of power series (inverse, sqrt, exp, log, sin, asin, ...)

#### fmpq_mpoly - multivariate polynomials over Q

- Efficient arithmetic for polynomials in sparse distributed form

#### nmod_mat - matrices over Z/nZ for word-size n

- Classical and multimodular multiplication
- Fast multiplication (reduction-free basecase, Strassen)
- Block recursive LU decomposition, reduced row echelon form, nullspace, inverse
- Determinant, rank, trace

#### nmod_poly - dense univariate polynomials over Z/nZ for word-size n

- Embarrassingly fast multiplication (classical, Kronecker substitution, David Harvey's KS2 and KS4)
- Fast division (basecase, divide-and-conquer, Newton)
- Divide-and-conquer composition
- Fast GCD and XGCD (Euclidean, half gcd)
- Fast modular composition
- Fast multipoint evaluation and interpolation
- Fast Taylor shift (basecase, convolution)
- Fast power series composition and reversion (Brent-Kung, fast Lagrange)
- Functions of power series (inverse, sqrt, exp, log, sin, asin, ...)

#### nmod_mod_poly_factor - factoring in (Z/nZ)[x] for word-size n

- Berlekamp, Cantor-Zassenhaus, Kaltofen-Shoup algorithms
- Squarefree, distinct-degree and equal-degree factorisation
- Irreducibility testing
- Power hack for polynomials of special form

#### nmod_poly_mat - matrices over Z/nZ[x] for word-size n

- Multiplication (classical, Kronecker substitution, interpolation)
- Determinants (fraction-free, interpolation)
- Reduced row echelon form, nullspace, inverse (fraction-free)

#### nmod_mpoly - multivariate polynomials over Z/nZ

- Efficient arithmetic for polynomials in sparse distributed form

#### padic - p-adic numbers

- Efficient representation based on the fmpz type
- Inverse and square root (Newton iteration)
- Exp and log (rectangular splitting, binary splitting)
- Teichmuller lift

#### padic_poly - polynomials over the p-adic numbers

- Efficient representation based on the fmpz_poly module

#### padic_mat - matrices over the p-adic numbers

- Efficient representation based on the fmpz_mat module

#### qadic - unramified extensions of the p-adic numbers

- Standardised representation using Conway polynomials
- Inverse and square root (Newton iteration)
- Exp and log (rectangular splitting, binary splitting)
- Teichmuller lift

#### fq / fq_nmod / fq_zech - finite fields F_q

- Three implementations optimised for different sizes: multi-precision primes, single-precision primes, and Zech logarithms
- Construction of finite fields using Conway polynomials or user-defined polynomials
- Powers, roots, Frobenius map, trace
- Bit packing

#### fq_mat / fq_nmod_mat / fq_zech_mat - dense matrices over finite fields F_q

- Classical and Kronecker substitution matrix multiplication
- Block recursive LU decomposition, reduced row echelon form, solving

#### fq_poly / fq_nmod_poly / fq_zech_poly - dense univariate polynomials over finite fields F_q

- Fast multiplication (classical, reordering, Kronecker substitution)
- Fast division (basecase, divide-and-conquer, Newton)
- Divide-and-conquer composition
- Fast GCD and XGCD (Euclidean, half gcd)
- Fast modular composition (Brent-Kung)

#### fq_poly_factor / fq_nmod_poly_factor / fq_zech_poly_factor - factorisation of polynomials over F_q

- Berlekamp, Cantor-Zassenhaus, Kaltofen-Shoup algorithms
- Squarefree, distinct-degree and equal-degree factorisation
- Irreducibility testing

#### fq_nmod_mpoly - multivariate polynomials over finite fields

- Efficient arithmetic for polynomials in sparse distributed form

#### arith - miscellaneous arithmetic functions

- Bernoulli, Euler, Bell, Stirling numbers
- Fast computation of the integer partition function
- Divisor sum, Euler phi and Möbius mu functions
- Sum of squares counting
- Cyclotomic, Chebyshev, Legendre, Swinnerton-Dyer polynomials
- Dedekind sums

### Antic library

The Antic library adds support for algebraic number theory. Antic includes the following modules.

#### qfb - binary quadratic forms

- Fast composition (Shanks' NUCOMP, NUDUPL)
- Computation of reduced forms
- Computation of the exponent of the class group (rigorously or assuming GRH)

#### nf_elem - elements of number fields

- Fast number field arithmetic based on the FLINT fmpq_poly type

### Arb library

The Arb library adds support for fast arbitrary-precision real and complex numbers with rigorous error control (using ball interval arithmetic). It supports polynomials, power series, matrices, and evaluation of special functions. Arb includes the following modules.

#### fmpr - binary floating-point numbers

- Efficient representation at word-size precision (up to 30/62 bits)
- Dynamic allocation, supporting integer-valued numbers efficiently
- Supports arbitrary-precision exponents
- Supports correct directed rounding (up/down/floor/ceiling)

#### fmprb - real numbers represented as floating-point balls

- All operations support arbitrary precision with automatic, rigorous error bounds
- Interval predicates (is positive, contains unique integer, etc.)
- Mathematical constants (pi, e, gamma, Catalan, ...)
- Elementary functions (sqrt, pow, exp, log, sin, ...)
- Rapid computation of special trigonometric values
- Special functions (gamma, digamma, log gamma, rising factorials, Riemann zeta function)

#### fmpcb - complex numbers

- Complex floating-point arithmetic based on the fmprb type
- All operations support arbitrary precision with automatic, rigorous error bounds
- Interval predicates
- Elementary functions (sqrt, pow, exp, log, sin, ...)
- Rapid computation of roots of unity
- Special functions (gamma, digamma, log gamma, rising factorials, Riemann zeta function, Hurwitz zeta function)

#### fmprb_poly - polynomials over the real numbers

- All operations support arbitrary precision with automatic, rigorous error bounds
- Numerically stable fast multiplication (scaling and blockwise multiplication over Z[x])
- Efficient truncated (power series) multiplication
- Fast division and power series division (Newton iteration)
- Composition (divide and conquer)
- Power series composition (Brent-Kung) and reversion (fast Lagrange)
- Evaluation (Horner, Paterson-Stockmeyer)
- Fast multipoint evaluation and interpolation
- Borel and binomial transforms
- Power series of elementary functions (sqrt, pow, exp, log, sin, ...)
- Power series of special functions (gamma, digamma, log gamma, rising factorials, Riemann and Hurwitz zeta functions, Riemann-Siegel theta and Z-functions)
- Asymptotically fast root polishing

#### fmpcb_poly - polynomials over the complex numbers

- All operations support arbitrary precision with automatic, rigorous error bounds
- Numerically stable fast multiplication (real decomposition)
- Fast division and power series division (Newton iteration)
- Composition (divide and conquer)
- Power series composition (Brent-Kung) and reversion (fast Lagrange)
- Evaluation (Horner, Paterson-Stockmeyer)
- Fast multipoint evaluation and interpolation
- Power series of elementary functions (sqrt, pow, exp, log, sin, ...)
- Power series of special functions (gamma, digamma, log gamma, rising factorials, Riemann and Hurwitz zeta functions)
- Isolation of all complex roots (Durand-Kerner iteration followed by verification)

#### fmprb_mat - matrices over the real numbers

- All operations support arbitrary precision with automatic, rigorous error bounds
- Multithreaded matrix multiplication
- LU decomposition
- Nonsingular solving, inverse, determinant

#### fmpcb_mat - matrices over the complex numbers

- All operations support arbitrary precision with automatic, rigorous error bounds
- LU decomposition
- Nonsingular solving, inverse, determinant

#### fmprb_calc - calculus with real-valued functions

- Rigorous isolation of roots (interval bisection)
- Asymptotically fast root polishing (Newton iteration with rigorous error bounds)

#### fmpcb_calc - calculus with complex-valued functions

- Numerical integration (Taylor algorithm with rigorous error bounds)

*Last updated: 2021-10-15 12:13:59 GMT*

*Contact: William Hart, flint-devel mailing list.*