mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Computer Science & Computational Number Theory

Reply
 
Thread Tools
Old 2014-12-29, 02:23   #23
D. B. Staple
 
D. B. Staple's Avatar
 
Nov 2007
Halifax, Nova Scotia

3816 Posts
Default

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!
D. B. Staple is offline   Reply With Quote
Old 2014-12-29, 04:27   #24
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

135418 Posts
Default

Quote:
Originally Posted by D. B. Staple View Post
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)?
CRGreathouse is offline   Reply With Quote
Old 2014-12-29, 06:00   #25
D. B. Staple
 
D. B. Staple's Avatar
 
Nov 2007
Halifax, Nova Scotia

23·7 Posts
Default

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.
D. B. Staple is offline   Reply With Quote
Old 2014-12-30, 13:02   #26
XYYXF
 
XYYXF's Avatar
 
Jan 2005
Minsk, Belarus

1100100002 Posts
Default

Any thoughts about 10^27?
XYYXF is offline   Reply With Quote
Old 2015-03-09, 01:37   #27
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

E5C16 Posts
Default

Douglas' paper is out: http://arxiv.org/abs/1503.01839
paulunderwood is offline   Reply With Quote
Old 2015-03-09, 02:17   #28
D. B. Staple
 
D. B. Staple's Avatar
 
Nov 2007
Halifax, Nova Scotia

23×7 Posts
Default

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.
D. B. Staple is offline   Reply With Quote
Old 2015-03-09, 11:45   #29
ldesnogu
 
ldesnogu's Avatar
 
Jan 2008
France

547 Posts
Default

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
ldesnogu is offline   Reply With Quote
Old 2015-03-09, 13:29   #30
D. B. Staple
 
D. B. Staple's Avatar
 
Nov 2007
Halifax, Nova Scotia

23×7 Posts
Default

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.
D. B. Staple is offline   Reply With Quote
Old 2015-03-10, 04:51   #31
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

32·5·7·19 Posts
Default

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?
CRGreathouse is offline   Reply With Quote
Old 2015-03-10, 08:27   #32
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

22·367 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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
R. Gerbicz is offline   Reply With Quote
Old 2015-03-10, 19:10   #33
D. B. Staple
 
D. B. Staple's Avatar
 
Nov 2007
Halifax, Nova Scotia

23×7 Posts
Default

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.
D. B. Staple is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
New confirmed pi(10^27), pi(10^28) prime counting function records kwalisch Computer Science & Computational Number Theory 34 2020-10-29 10:04
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

All times are UTC. The time now is 20:08.

Mon May 17 20:08:39 UTC 2021 up 39 days, 14:49, 0 users, load averages: 3.58, 3.35, 2.99

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.