FLINT: Fast Library for Number Theory

Overview | News | Features | Benchmarks | Downloads | Development | Authors and credits | Links and references

Benchmarks

This page shows how FLINT compares to other software on a selection of artificial benchmarks.

Polynomial factorisation over Z/pZ

Time (s) to factor the degree-n polynomial (x + 2x + 3x³ + ... + nxⁿ) modulo 17. CPU: AMD Opteron 6174 2.20 GHz, except Mathematica which was timed on a Xeon E5-2650, 2.00 GHz (>20% faster). FLINT, NTL and presumably also Magma use similar implementations of the Cantor-Zassenhaus algorithm with the Kaltofen-Shoup improvement, so this benchmark largely tests the speed of polynomial arithmetic.

Arithmetic with p-adic numbers

Time (s) to compute a p-adic logarithm to precision 17ⁿ. CPU: Xeon X5670, 2.93 GHz. FLINT uses rectangular splitting series evaluation for small n and an asymptotically optimal algorithm (based on balanced argument reduction and binary splitting series evaluation) for large n.

Factorisation of word-size integers

Time (s) to factor 10000 consecutive n-bit integers (2^n-1 + 1), ..., (2^n-1 + 10000), where n goes up to the word size (64 bits). CPU: Xeon E5-2650, 2.00 GHz. FLINT uses a combination of trial division, Hart's One Line Factor algorithm, SQUFOF, and quick tests for primes and perfect powers. The slowdown very close to 64 bits is possibly due to the fact that FLINT does not currently use the p+1 algorithm.

Power series over the real numbers

Time (s) to compute the Taylor series exp(exp(1+x)) to order xⁿ at n-digit precision. CPU: Xeon E5-2650, 2.00 GHz. For large n, this example illustrates FLINT's efficient arithmetic with polynomials that have both high degree and large coefficients. It should be noted that the timings are not perfectly comparable since the results have different accuracy. Only FLINT 2.4/Arb computes rigorous error bounds.

Generating Bernoulli numbers

Time (s) to generate a table of the Bernoulli numbers B₀, ..., B_n as exact fractions. CPU: Xeon E5-2650, 2.00 GHz. Pari/GP and FLINT 2.4/Arb compute the Bernoulli numbers by numerical approximation of the Riemann zeta function.

Integer partitions

Time (s) to compute the exact value of the partition function p(n). CPU: Xeon X5675, 3.07 GHz. All implementations (except Maple?) use the numerical Hardy-Ramanujan-Rademacher formula. Out of the two FLINT implementations, the newer "FLINT 2.4/Arb" version implements a provably correct algorithm (the older "FLINT 2.4" version depends on heuristics, with most of the speedup for very small n coming from use of hardware floating-point arithmetic).

---