The combinatorial algorithm for computing pi(x)
Author
Staple, Douglas
Metadata
Show full item recordAbstract
This thesis describes recent advances in the combinatorial method for computing pi(x), the number of primes less-than or equal-to x. In particular, the memory usage has been reduced by a factor of log x, and modifications for shared- and distributed-memory parallelism have been incorporated. The resulting method computes pi(x) with complexity O(x^(2/3) (log x)^(-2)) in time and O(x^(1/3) (log x)^2) in space. The algorithm has been implemented and used to compute pi(10^n) for 1 <= n <= 26 and pi(2^m) for 1 <= m <= 86. The mathematics presented here is consistent with and builds on that of previous authors.