This program implements the algorithms of "Computing π(x): the combinatorial method" by Tomás Oliveira e Silva (2006). It is also a learning project for numerical computing in C++ and a sandbox to test out optimizations.
Alpha is a tuning parameter that trades fewer segmented sieve blocks to iterate over for more computation per block. From the paper, it must be <= x^(1/6) and should grow like O(log^3 x). I found log10(x)^3 / 150 generated reasonable alpha values, and there is a decent amount of leeway.
The following benchmarks used a block size of 2^20 and default alpha value. Compiled with g++ -O3 and run on my laptop (Ubuntu 22.04, GCC 11.4.0, i7-7700HQ). The CPU has 6 MiB of L3 cache, and experimentally a block size of 2^20, taking up 2^20 x (1/2 sieve size storing odd values) x 4 byte ints = 2 MiB, works well.
x | Time | π(x) |
---|---|---|
10^12 | 0.3s | 37607912018 |
10^13 | 1.0s | 346065536839 |
10^14 | 4.0s | 3204941750802 |
10^15 | 18s | 29844570422669 |
10^16 | 1m16s | 279238341033925 |
10^17 | 5m50s | 2623557157654233 |
10^18 | 30m38s | 24739954287740860 |
10^19 | 186m | 234057667276344607 |
Still a better use of electricity than crypto
The powers of 10 in the table match Table IV of the paper. Previously I had only tested smaller values, and starting from x = 10^15 had an overflow bug due to cubing some values. Running with GCC's -ftrapv can detect signed overflow. There was also an issue with crashing where Algorithm 2 sometimes needs
Legendre (1808) was the first to notice
Lagarias and Odlyzko (1987) described an analytic algorithm with better time complexity O(x^(1/2+ε)), but it goes way over my head and in practice has not been faster than the combinatorial method yet. The implementation also uses interval arithmetic. Don't expect that project from me any time soon.
Let
By the fundamental theorem of arithmetic,
Since the prime factors have to be greater than
The Lagarias et al. methods use
rearranging
The computation of
The main computation
Lehmer's original algorithm stops recursing at
The algorithm as a whole takes