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.
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: 2022-05-20 09:07:08 GMT
Contact: Fredrik Johansson, flint-devel mailing list.