Prime counting function records - Page 3

D. B. Staple · 2014-12-29, 02:23

The double-check for π(2⁸⁶) completed; the result was consistent with the value I posted on Dec. 17.

Regarding timing and resource usage, I am going to release that information when I write up this work for publication. I don't plan to run calculations for other bases, because there is no limit to how many such calculations one can do. I computed π(10²⁶) because the powers of ten have been the most competitive historically. I computed π(2^m) for m ≤ 86 because I find two a natural base, and because there were some other powers of two for large heights available to which I could compare. This served as an additional opportunity to check my software.

Thank you everyone for being interested in these calculations!

CRGreathouse · 2014-12-29, 04:27

Quote:

Originally Posted by D. B. Staple

Thank you everyone for being interested in these calculations!

I am, very much! I hope you will post here when the preprint is available on the arXiv (or your website, or when it's published)?

D. B. Staple · 2014-12-29, 06:00

Quote:

I am, very much! I hope you will post here when the preprint is available on the arXiv (or your website, or when it's published)?

Yes, I will definitely post back here when I have more to share.

XYYXF · 2014-12-30, 13:02

Any thoughts about 10^27?

paulunderwood · 2015-03-09, 01:37

Douglas' paper is out: http://arxiv.org/abs/1503.01839

D. B. Staple · 2015-03-09, 02:17

Quote:

Douglas' paper is out: http://arxiv.org/abs/1503.01839

It's true! Thank you for noticing. I actually just got the notice myself, so you are exceptionally fast. If anyone finds any typos, omissions, or errors, please let me know. Again, I am really happy at the interest in these calculations and this paper.

ldesnogu · 2015-03-09, 11:45

Though I didn't read all of the article yet, here are some comments.

You don't define what a "node" is. The first occurrence of "node" page 6 talks about 16 threads, and given that you talk about 2 8-core CPUs in Appendix A, I assume it's a set of cores sharing memory.

Did you try to play with hyper-threading? On my 4770K (4 cores, 8 threads with HT), using Walish library (from last December) I get 1.5s for 10^15 with 12 threads while I only get 2.2s with 4 threads. It seems Walisch implementation is about twice faster than yours (accounting for threads and frequency difference); I guess this is due to your memory usage improvements?

I found a missing word on page 2 line +4:

Quote:

The problem of counting the number of primes up to some limit

D. B. Staple · 2015-03-09, 13:29

Quote:

Though I didn't read all of the article yet, here are some comments.

Thanks -- I'll fix each of these points in the next version. (Yes, a node is a shared-memory computer. Multiple nodes together make a cluster. I typically use 16-core nodes with 64 or 128 GB of ram each.)

Re: hyper-threading, my code is also significantly faster with hyper-threading enabled, to a similar degree as what you're seeing with the implementation from Kim Walisch. Unfortunately hyper-threading is not enabled on one of the best clusters in Canada, where I ran my calculations. I've spoken to the people in charge and they're planning to enable it some time this year, which will take some time on ~1000 compute nodes.

I also noticed that the implementation by Kim Walisch is faster than mine. I think their implementation is just more numerically efficient than mine. I wrote the bulk of my pi(x) software while I was still working as a physicist. I improved my optimization skills a lot while writing that code, and am now working full-time as a software engineer.

If you've looked at the sieve of Eratosthenes implementation by Kim Walisch, you'll see that it is incredibly efficient. I think Kim Walisch and Tomás Oliveira e Silva are two of the most efficient low-level coders I've ever seen. I'm glad I didn't know about the implementation by Kim Walisch, or it would have interfered with my project. However, I will probably go back now and read through their code and see what I can learn.

It's a bit interesting to me that I managed to "beat" Kim Walisch to pi(10^26) despite the fact that they are apparently a more efficient low-level coder (for now). My feeling is that they (1) were probably missing the algorithm for between-node (distributed memory) parallelism and (2) had more trouble getting the memory usage down. I'm going to send them an email here shortly.

Sorry that was a bit long-winded. Please send me any more corrections you find.

CRGreathouse · 2015-03-10, 04:51

Great paper! Two small points on p. 1: I'd write "limited to time complexity $\Omega(n/\log n)$ " rather than "limited to time complexity $O(n/\log n)$ " -- even though people would probably understand it the other way, you might as well be correct. And surely the complexity of Meissel's method was $x^{1-\varepsilon}$ for some small $\varepsilon>0$ , not just any $\varepsilon>0$ ?

R. Gerbicz · 2015-03-10, 08:27

Quote:

Originally Posted by CRGreathouse

And surely the complexity of Meissel's method was $x^{1-\varepsilon}$ for some small $\varepsilon>0$ , not just any $\varepsilon>0$ ?

Yes, that couldn't be for any eps>0 (let eps=2).

D. B. Staple · 2015-03-10, 19:10

Quote:

Two small points on p. 1...

Quote:

Yes, that couldn't be for any eps>0 (let eps=2).

Thanks! Good catch. Yes, you are both right, I am colloquial to the point of incorrect in those two places.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
New confirmed pi(10^27),... pi(10^29) prime counting function records	kwalisch	Computer Science & Computational Number Theory	42	2022-08-12 10:48
Counting Goldbach Prime Pairs Up To...	Steve One	Miscellaneous Math	8	2018-03-06 19:20
Prime counting function	Steve One	Miscellaneous Math	20	2018-03-03 22:44
Fourier Series for Prime Number Counting Functions	SteveC	Analysis & Analytic Number Theory	10	2016-10-14 21:48
Legendre's prime counting function	pbewig	Information & Answers	0	2011-07-14 00:47

2014-12-29, 02:23	#23
D. B. Staple Nov 2007 Halifax, Nova Scotia 2³×7 Posts	The double-check for π(2⁸⁶) completed; the result was consistent with the value I posted on Dec. 17. Regarding timing and resource usage, I am going to release that information when I write up this work for publication. I don't plan to run calculations for other bases, because there is no limit to how many such calculations one can do. I computed π(10²⁶) because the powers of ten have been the most competitive historically. I computed π(2^m) for m ≤ 86 because I find two a natural base, and because there were some other powers of two for large heights available to which I could compare. This served as an additional opportunity to check my software. Thank you everyone for being interested in these calculations!

2014-12-30, 13:02	#26
XYYXF Jan 2005 Minsk, Belarus 620₈ Posts	Any thoughts about 10^27?

2015-03-09, 01:37	#27
paulunderwood Sep 2002 Database er0rr 2²·1,063 Posts	Douglas' paper is out: http://arxiv.org/abs/1503.01839

2015-03-10, 04:51	#31
CRGreathouse Aug 2006 3×1,993 Posts	Great paper! Two small points on p. 1: I'd write "limited to time complexity $\Omega(n/\log n)$ " rather than "limited to time complexity $O(n/\log n)$ " -- even though people would probably understand it the other way, you might as well be correct. And surely the complexity of Meissel's method was $x^{1-\varepsilon}$ for some small $\varepsilon>0$ , not just any $\varepsilon>0$ ?