profiling2026
Word-size primality test and factoring (Fredrik)
Pari used to be much better than FLINT for primality testing and factoring word-size integers at least in some input ranges. After some recent optimizations I’ve made to FLINT, I expect that this should no longer be the case, and I’ve done some quick benchmarking to verify this. Average time in seconds for 100000 random inputs of each bit size:
isprime factorint
bits pari flint ratio pari flint ratio
-----------------------------------------------------------
2 1.27e-08 4.40e-09 2.89x 2.46e-08 5.42e-09 4.53x
3 1.33e-08 4.37e-09 3.04x 3.58e-08 6.71e-09 5.33x
4 1.43e-08 4.38e-09 3.26x 4.45e-08 8.45e-09 5.26x
5 1.43e-08 4.37e-09 3.28x 4.98e-08 9.16e-09 5.44x
6 1.51e-08 4.37e-09 3.47x 5.47e-08 1.04e-08 5.26x
7 1.60e-08 4.38e-09 3.66x 5.94e-08 1.22e-08 4.87x
8 1.68e-08 4.36e-09 3.84x 6.36e-08 1.37e-08 4.65x
9 1.72e-08 4.39e-09 3.92x 6.82e-08 1.47e-08 4.64x
10 1.87e-08 4.39e-09 4.25x 7.27e-08 1.58e-08 4.60x
11 1.93e-08 4.37e-09 4.41x 7.88e-08 1.68e-08 4.69x
12 2.03e-08 4.38e-09 4.63x 8.45e-08 1.79e-08 4.72x
13 2.14e-08 4.39e-09 4.89x 9.06e-08 1.88e-08 4.82x
14 2.29e-08 4.39e-09 5.22x 9.62e-08 1.96e-08 4.91x
15 2.48e-08 4.39e-09 5.65x 1.05e-07 2.05e-08 5.10x
16 2.90e-08 5.65e-09 5.13x 1.14e-07 2.30e-08 4.94x
17 2.62e-08 5.65e-09 4.64x 1.27e-07 2.65e-08 4.81x
18 2.39e-08 5.69e-09 4.19x 1.38e-07 2.83e-08 4.89x
19 2.51e-08 5.67e-09 4.43x 1.57e-07 3.04e-08 5.17x
20 2.72e-08 5.65e-09 4.81x 1.77e-07 3.29e-08 5.38x
21 2.80e-08 1.46e-08 1.91x 1.99e-07 4.09e-08 4.87x
22 2.88e-08 1.51e-08 1.91x 2.18e-07 4.79e-08 4.56x
23 2.93e-08 1.54e-08 1.90x 2.38e-07 5.52e-08 4.31x
24 3.05e-08 1.59e-08 1.92x 2.59e-07 6.31e-08 4.10x
25 3.07e-08 1.63e-08 1.88x 2.97e-07 7.18e-08 4.13x
26 3.15e-08 1.68e-08 1.87x 3.35e-07 8.13e-08 4.12x
27 3.22e-08 1.73e-08 1.86x 3.75e-07 9.15e-08 4.10x
28 3.26e-08 1.76e-08 1.85x 4.26e-07 1.03e-07 4.14x
29 3.34e-08 1.82e-08 1.84x 4.89e-07 1.17e-07 4.18x
30 3.41e-08 1.85e-08 1.84x 5.64e-07 1.31e-07 4.31x
31 3.80e-08 1.89e-08 2.01x 6.61e-07 1.48e-07 4.46x
32 4.02e-08 1.97e-08 2.04x 7.71e-07 1.69e-07 4.56x
33 5.11e-08 2.42e-08 2.11x 9.08e-07 1.99e-07 4.56x
34 5.78e-08 2.44e-08 2.37x 1.08e-06 2.37e-07 4.55x
35 6.19e-08 2.45e-08 2.53x 1.25e-06 2.75e-07 4.56x
36 6.34e-08 2.49e-08 2.55x 1.51e-06 3.32e-07 4.56x
37 6.45e-08 2.52e-08 2.56x 1.72e-06 3.92e-07 4.39x
38 6.62e-08 2.55e-08 2.60x 2.04e-06 4.62e-07 4.41x
39 6.48e-08 2.57e-08 2.52x 2.39e-06 5.47e-07 4.37x
40 6.37e-08 2.59e-08 2.46x 2.88e-06 6.38e-07 4.51x
41 6.42e-08 2.64e-08 2.43x 3.37e-06 7.53e-07 4.47x
42 6.43e-08 2.71e-08 2.37x 4.02e-06 8.73e-07 4.61x
43 6.44e-08 2.69e-08 2.39x 4.78e-06 1.03e-06 4.64x
44 6.48e-08 2.74e-08 2.37x 5.77e-06 1.20e-06 4.81x
45 6.63e-08 2.76e-08 2.40x 6.77e-06 1.35e-06 5.02x
46 6.73e-08 2.82e-08 2.39x 8.09e-06 1.54e-06 5.25x
47 6.76e-08 2.80e-08 2.41x 9.27e-06 1.74e-06 5.33x
48 6.98e-08 2.83e-08 2.47x 1.02e-05 1.94e-06 5.25x
49 7.00e-08 2.87e-08 2.44x 1.14e-05 2.17e-06 5.23x
50 7.09e-08 2.89e-08 2.45x 1.26e-05 2.45e-06 5.14x
51 7.22e-08 2.92e-08 2.47x 1.38e-05 2.72e-06 5.07x
52 7.26e-08 2.99e-08 2.43x 1.51e-05 3.05e-06 4.96x
53 7.30e-08 3.02e-08 2.42x 1.66e-05 3.40e-06 4.89x
54 7.48e-08 3.05e-08 2.45x 1.83e-05 3.78e-06 4.83x
55 7.59e-08 3.08e-08 2.46x 1.98e-05 4.22e-06 4.69x
56 7.66e-08 3.11e-08 2.46x 2.15e-05 4.70e-06 4.58x
57 7.75e-08 3.14e-08 2.47x 2.36e-05 5.19e-06 4.55x
58 7.86e-08 3.15e-08 2.50x 2.56e-05 5.83e-06 4.38x
59 8.04e-08 3.13e-08 2.57x 2.79e-05 6.52e-06 4.28x
60 8.00e-08 3.26e-08 2.45x 3.00e-05 7.36e-06 4.08x
61 8.11e-08 3.25e-08 2.49x 3.29e-05 8.28e-06 3.97x
62 8.25e-08 3.28e-08 2.51x 3.51e-05 9.25e-06 3.80x
63 8.50e-08 3.69e-08 2.30x 3.78e-05 1.07e-05 3.54x
64 8.54e-08 3.75e-08 2.28x 4.11e-05 1.23e-05 3.34xHere are the main tricks currently used in FLINT, some of which would make sense to implement in Pari too where they are not already used.
Primality testing:
- Static bitmap mod 2 up to 15 bits, mod 30 up to 20 bits
- Trial division by a handful of small fixed primes
- Between 21 and 32 bits, use a single base-2 test and catch all passing composites with a hash table
- Modular arithmetic up to 32 bits uses Shoup modular reduction
- Between 33 and 64 bits, use a base-2 test, then a single extra base strong probable prime test with a base chosen from a hash table to guarantee catching all remaining composites
- Modular arithmetic up to 64 bits uses Montgomery reduction
Factoring:
- Trial division uses exactly the 16-bit primes. Divisibility testing is done by multiplying by precomputed inverses mod 2^64
- A primality test is done at a strategically chosen point in the middle of trial division
- Between 33 and 38 bits, try Hart’s one line factor algorithm with SQUFOF as a fallback (in practice SQUFOF is never needed)
- Between 39 and 64 bits, try one run of Pollard-Brent (succeeds in 99.9% of cases), then one line factor, then SQUFOF as a fallback
- Pollard-Brent uses Montgomery arithmetic
- Primality testing (of the input as well as partial factors) skips trial division
