mersenneforum.org New confirmed pi(10^27), pi(10^28) prime counting function records
 Register FAQ Search Today's Posts Mark Forums Read

2018-09-09, 17:25   #23
Till

"Tilman Neumann"
Jan 2016
Germany

2×11×19 Posts

Quote:
 Originally Posted by mikenickaloff You shouldnt hide your work.. I created an algorithm that can get the number of primes up to 10^51227 instantly.. Maybe you should try using it to see if you can find how many there are up to a larger amount? https://www.datafault.net/prime-numb...ery-algorithm/

I typed in a number that fits into the window, so the answer should definitely come instantly?

Code:
19700000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000197
Unfortunately i do not see any response (couple of miutes waiting)

Last fiddled with by Till on 2018-09-09 at 17:26 Reason: typo

2020-05-01, 22:28   #24
rudy235

Jun 2015
Vallejo, CA/.

96110 Posts

Quote:
 Originally Posted by kwalisch After roughly 5 months of computation David Baugh and myself have verified pi(10^27): pi(10^27) = 16,352,460,426,841,680,446,427,399 This time the computation took 20.35 CPU core years, this is 11.6% faster than our first computation. The speed up comes from primecount improvements, particularly I have added pre-sieving and wheel factorization to primecount's sieving algorithms. Below are the details of the verification: Code: x = 1000000000000000000000000000 y = 231112254739 pi(y) = 9199337709 P2 = 4743234949871865833944278 S1 = 45739379279637813150 S2_trivial = 42247262851521121201 S2_easy = 4453498620247012088893172 S2_hard = 16642108769824393833206446 S2 = S2_trivial + S2_easy + S2_hard pi(x) = S1 + S2 + pi(y) - 1 - P2 pi(x) = 16352460426841680446427399
Hello: The last post on this thread is a bit short of twenty months old. Is there any chance some new calculation has increased the size of the known π(x) ?
For instance π(290 is very close to π(1027) and while the next exponent (1028 is a difficult task I would think some progress might be there after almost 5 years. Last time it took about a year to go from 10^26 to 10^27

2020-05-06, 07:21   #25
kwalisch

Sep 2015

218 Posts

Quote:
 Originally Posted by rudy235 Hello: The last post on this thread is a bit short of twenty months old. Is there any chance some new calculation has increased the size of the known π(x) ? For instance π(290 is very close to π(1027) and while the next exponent (1028 is a difficult task I would think some progress might be there after almost 5 years. Last time it took about a year to go from 10^26 to 10^27
primecount is still being actively used to compute new records by David Baugh and myself. primecount has been massively improved since our last pi(10^27) announcement i.e. I have now implemented Xavier Gourdon's algorithm and I have found an optimization that improves primecount's runtime complexity of the hard special leaves formula by more than a constant factor (see https://github.com/kimwalisch/primec...cial-Leaves.md).

I don't exactly know which values David is currently computing using primecount, but we will announce important new records here on the mersenneforum. I don't want to publicly disclose ongoing computations as this could give competitors a strategic edge. If you would like to contribute and use primecount to compute new records please send me an email and we can discuss privately and I can share more information.

 2020-05-24, 12:35 #26 danaj   "Dana Jacobsen" Feb 2011 Bangkok, TH 5×181 Posts
2020-05-29, 18:49   #27
ixfd64
Bemusing Prompter

"Danny"
Dec 2002
California

230310 Posts

Quote:
 Originally Posted by kwalisch I don't exactly know which values David is currently computing using primecount, but we will announce important new records here on the mersenneforum. I don't want to publicly disclose ongoing computations as this could give competitors a strategic edge. If you would like to contribute and use primecount to compute new records please send me an email and we can discuss privately and I can share more information.
Unless there's a prize involved, we should ideally be working together rather than competing against one another.

 2020-08-30, 10:04 #28 dbaugh     Aug 2005 11510 Posts New prime counting function record, pi(10^28) I am happy to announce that Kim Walisch and I have computed the number of primes below 10^28, the result is: pi(10^28) = 157,589,269,275,973,410,412,739,598 The computation was performed using a version of Kim's primecount program with backup functionality. primecount counts primes using a highly optimized parallel implementation of Xavier Gourdon's algorithm (combinatorial method). The computation took 26.42 CPU core years (only physical CPU cores are counted) and the peak memory usage was 370 gigabytes. My part of the calculation was run on a dual socket server (36 CPU cores, 2x Intel Xeon E5-2699 v3). The rest of the computation was run on a single socket server (48 CPU cores, 1x AMD EPYC 7642). Our result passes the parity check and the result is also very close to RiemannR(10^28), i.e.: | R(10^28) - 157,589,269,275,973,410,412,739,598| < sqrt(10^28) / log(10^28) As can be expected with such a large and protracted calculation, a few hardware issues were dealt with. However, the software is extremely robust and we have sufficient confidence in the result. We will start a full verification shortly by recalculating pi(10^28) a second time using different configuration parameters and an improved version of primecount. We expect this verification to take less than a year. Best regards, David Baugh
 2020-08-30, 10:31 #29 LaurV Romulan Interpreter     Jun 2011 Thailand 8,741 Posts yay!
 2020-08-30, 11:31 #30 danaj   "Dana Jacobsen" Feb 2011 Bangkok, TH 90510 Posts Fantastic! I've been following the git repo watching the continuing improvements to the code.
2020-08-30, 20:38   #31
kwalisch

Sep 2015

100012 Posts

Quote:
 Originally Posted by danaj Fantastic! I've been following the git repo watching the continuing improvements to the code.
Implementing primecount was/is a lot of work, when I started the project back in 2013 you were a tremendous help to myself. At that time both your and my project included the only advanced prime counting function implementations on the web. It was very difficult to get started and I asked a lot of questions (because you had started implementing the Lagarias-Miller-Odlyzko algorithm a few months earlier) that you patiently answered. Thanks for that I also still read your source code from time to time.

What David has not mentioned is that we had a miscalculation of PrimePi(1e28) at the beginning of the year. It was depressing! That computation was started back in August 2017 jointly by David and myself using the Deleglise-Rivat algorithm. At the time I had significantly improved the sieving algorithm of the hard special leaves formula (S2_hard) and the benchmarks of the new implementation were very promising. I expected that we could compute PrimePi(1e28) in about 6 to 8 months. So we started the computation but we soon realised that my estimations were too optimistic and that the S2_hard formula had severe scaling issues. After running that formula for about 18 months on a dual-socket server it still had not completed and it was difficult for me to estimate how much longer it would run. Every month I estimated that it would finish next month. Another issue was that the backups were happening very infrequently, sometimes it took more than a month until the program would write a new backup to disk. So what happened frequently is that we lost a lot of work due to power outages or my EC2 spot instances got killed for various reasons. At the end of 2019 the issue of infrequent backups become so annoying that we decided to manually edit the backup files to reduce the thread sieving distances in order to increase the backup frequency. That was likely a big mistake!

When the computation of the S2_hard formula finally finished after about 2.5 years we calculated the final sum and we immediately realised that the result was not correct, it was orders of magnitude off. This was the first primecount miscalculation in about 3 years and unfortunately we couldn't even tell which formula had been miscalculated, we guess it is S2_hard but we don't know for sure. Because of that miscalculation, I started the tiring work of rechecking every single formula/algorithm and I re-read all the combinatorial prime counting papers. After a few weeks I had such a in-depth understanding of all the different formulas and algorithms that I realised that the scaling issue we had experienced was not a hardware issue as I expected but rather an unsound optimization that I had copied from other people's implementations. The problem is/was that theory and practice have diverged significantly. All math papers describe that one must compute the special leaves using a binary indexed tree, however most of the prime counting function implementations that one can find on the web don't do this, instead most implementations use a large number of micro optimizations to quickly count the number of unsieved elements from the sieve array. Once I understood that these optimizations were deteriorating the runtime complexity of the algorithm and hence causing my scaling issue it did not take long until I found a simple but significant improvement that fixed my scaling issue: https://github.com/kimwalisch/primec...cial-Leaves.md.

So in the end that miscalculation was hugely beneficial to primecount: I implemented Gourdon's algorithm, I found an improvement that fixed the scaling issue of the hard special leaves formula and I also improved the backup functionality (more frequent backups + checksums). When we recomputed PrimePi(1e28) using Gourdon's algorithm the computation of the hard special leaves took only 37 days (instead of 2.5 years). Here is another example that shows how much primecount has improved since our last record: PrimePi(1e27) took 23.03 CPU core years whereas PrimePi(1e28) took only 26.42 CPU core years. Usually you can expect that computing a 10x larger value takes about 5x more time. Hence for record computations primecount has been sped up by about 4x since 2015.

 2020-08-31, 03:01 #32 rudy235     Jun 2015 Vallejo, CA/. 312 Posts Well, I must say it is impressive. Congratulations to both of you.
2020-08-31, 16:58   #33
CRGreathouse

Aug 2006

172316 Posts

Quote:
 Originally Posted by kwalisch So in the end that miscalculation was hugely beneficial to primecount: I implemented Gourdon's algorithm, I found an improvement that fixed the scaling issue of the hard special leaves formula and I also improved the backup functionality (more frequent backups + checksums). When we recomputed PrimePi(1e28) using Gourdon's algorithm the computation of the hard special leaves took only 37 days (instead of 2.5 years). Here is another example that shows how much primecount has improved since our last record: PrimePi(1e27) took 23.03 CPU core years whereas PrimePi(1e28) took only 26.42 CPU core years. Usually you can expect that computing a 10x larger value takes about 5x more time. Hence for record computations primecount has been sped up by about 4x since 2015.
Extremely impressive work.

 Similar Threads Thread Thread Starter Forum Replies Last Post MJansen Prime Gap Searches 28 2020-05-09 12:46 enzocreti enzocreti 10 2020-02-15 13:23 Steve One Miscellaneous Math 20 2018-03-03 22:44 D. B. Staple Computer Science & Computational Number Theory 43 2016-12-25 22:15 pbewig Information & Answers 0 2011-07-14 00:47

All times are UTC. The time now is 07:54.

Thu Sep 24 07:54:41 UTC 2020 up 14 days, 5:05, 0 users, load averages: 0.67, 1.04, 1.18