Add a combinatorial prime number counter

[justAnotherMathmo]

Hey - this PR adds a combinatorial prime number counting function that speeds things up for larger numbers. I'm hoping to speed it up much more in the future (it's far from optimal currently), but I figured I'd get the right api sorted out first.

Currently, this implementation is slower at evaluating pi(n) for n < 10^7, but faster for values larger than about that. It's more than 10x faster by the time you get to 10^10 - looking at benchmarks on my computer:

prime_pi/PrimeCounter with init/10000000000
time:   [127.04 ms 127.94 ms 128.67 ms]
prime_pi/Sieve with init/10000000000
time:   [2.1252 s 2.1258 s 2.1264 s]
prime_pi/StreamingSieve/10000000000
time:   [2.0433 s 2.0449 s 2.0466 s]
prime_pi/Primes/10000000000
time:   [3.7269 s 3.7319 s 3.7380 s] 

Please let me know if there's anything you want changed, or if you don't want this in this repo, in which case I'll move it elsewhere.

[autohuonw]

Thanks for the pull request, and welcome! You should hear from @huonw (or someone else) soon.

[codecov[bot]]

Codecov Report

Merging #28 into master will decrease coverage by 2.15%. The diff coverage is 94.56%.

@@            Coverage Diff             @@
##           master      #28      +/-   ##
==========================================
- Coverage   51.22%   49.06%   -2.16%     
==========================================
  Files          17       20       +3     
  Lines        3934     4537     +603     
==========================================
+ Hits         2015     2226     +211     
- Misses       1919     2311     +392

Impacted Files	Coverage Δ
primal-sieve/src/wheel/wheel210.rs	0% <0%> (ø)	:arrow_up:
primal-count/src/lib.rs	0% <0%> (ø)
primal-count/src/util.rs	100% <100%> (ø)
primal-sieve/src/streaming/mod.rs	88.65% <100%> (-0.46%)	:arrow_down:
primal-sieve/src/wheel/wheel30.rs	99.47% <100%> (+0.09%)	:arrow_up:
primal-sieve/src/sieve.rs	90.39% <100%> (-1.41%)	:arrow_down:
primal-count/src/prime_count.rs	99.11% <99.11%> (ø)
primal-sieve/src/streaming/primes.rs	95.77% <0%> (-2.76%)	:arrow_down:
primal-slowsieve/src/lib.rs	96.75% <0%> (-1.83%)	:arrow_down:
primal-estimate/src/lib.rs	94.64% <0%> (-1.73%)	:arrow_down:
... and 11 more

---

Continue to review full report at Codecov.

Legend - Click here to learn more Δ = absolute <relative> (impact), ø = not affected, ? = missing data Powered by Codecov. Last update 1b2d907...6f8eebf. Read the comment docs.

[huonw]

Thanks for the PR. That speed-up looks great! Unfortunately I'm going to be away for a few weeks, so won't be able to do anything with you. Maybe @cuviper is interested?

[justAnotherMathmo]

Sure! No rush here - I'll continue to commit and try to speed things up in the meantime. At the moment, I'm just playing around with speeding up the current implementation, but probably around December I'll try to implement the Delaglise, Rivat and perhaps Gourdon algorithms instead of the naive version now, which should hopefully get another few orders of magnitude of speed out for larger numbers.

Latest commit has 10^10 down, and I suspect the point at which this is better than the prime_pi method has shifted down as well, but I haven't looked too hard at that:

prime_pi/PrimeCounter with init/10000000000
time:   [52.322 ms 52.587 ms 52.886 ms]

[cuviper]

I am interested, but not able to work on it at the moment. I'll try to come back to this.