mersenneforum.org Prime counting function records
 Register FAQ Search Today's Posts Mark Forums Read

 2014-12-29, 02:23 #23 D. B. Staple     Nov 2007 Halifax, Nova Scotia 23·7 Posts The double-check for π(286) 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 π(1026) because the powers of ten have been the most competitive historically. I computed π(2m) 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-29, 04:27   #24
CRGreathouse

Aug 2006

3×1,993 Posts

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)?

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

Nov 2007
Halifax, Nova Scotia

3816 Posts

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.

 2014-12-30, 13:02 #26 XYYXF     Jan 2005 Minsk, Belarus 40010 Posts Any thoughts about 10^27?
 2015-03-09, 01:37 #27 paulunderwood     Sep 2002 Database er0rr 1111011001102 Posts Douglas' paper is out: http://arxiv.org/abs/1503.01839
2015-03-09, 02:17   #28
D. B. Staple

Nov 2007
Halifax, Nova Scotia

5610 Posts

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.

2015-03-09, 11:45   #29
ldesnogu

Jan 2008
France

2·52·11 Posts

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

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

Nov 2007
Halifax, Nova Scotia

23·7 Posts

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.

 2015-03-10, 04:51 #31 CRGreathouse     Aug 2006 597910 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$?
2015-03-10, 08:27   #32
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

72·31 Posts

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).

Last fiddled with by R. Gerbicz on 2015-03-10 at 08:32

2015-03-10, 19:10   #33
D. B. Staple

Nov 2007
Halifax, Nova Scotia

5610 Posts

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 kwalisch Computer Science & Computational Number Theory 34 2020-10-29 10:04 Steve One Miscellaneous Math 8 2018-03-06 19:20 Steve One Miscellaneous Math 20 2018-03-03 22:44 SteveC Analysis & Analytic Number Theory 10 2016-10-14 21:48 pbewig Information & Answers 0 2011-07-14 00:47

All times are UTC. The time now is 21:49.

Mon Dec 6 21:49:38 UTC 2021 up 136 days, 16:18, 1 user, load averages: 2.88, 2.66, 3.04