mersenneforum.org  

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

Reply
 
Thread Tools
Old 2018-09-09, 17:25   #23
Till
 
Till's Avatar
 
"Tilman Neumann"
Jan 2016
Germany

2·11·19 Posts
Default

Quote:
Originally Posted by mikenickaloff View Post
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
Till is offline   Reply With Quote
Old 2020-05-01, 22:28   #24
rudy235
 
rudy235's Avatar
 
Jun 2015
Vallejo, CA/.

3C116 Posts
Default

Quote:
Originally Posted by kwalisch View Post
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
rudy235 is offline   Reply With Quote
Old 2020-05-06, 07:21   #25
kwalisch
 
kwalisch's Avatar
 
Sep 2015

17 Posts
Default

Quote:
Originally Posted by rudy235 View Post
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.
kwalisch is offline   Reply With Quote
Old 2020-05-24, 12:35   #26
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

5×181 Posts
Default

danaj is offline   Reply With Quote
Old 2020-05-29, 18:49   #27
ixfd64
Bemusing Prompter
 
ixfd64's Avatar
 
"Danny"
Dec 2002
California

72×47 Posts
Default

Quote:
Originally Posted by kwalisch View Post
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.
ixfd64 is offline   Reply With Quote
Old 2020-08-30, 10:04   #28
dbaugh
 
dbaugh's Avatar
 
Aug 2005

11510 Posts
Default 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
dbaugh is offline   Reply With Quote
Old 2020-08-30, 10:31   #29
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

8,741 Posts
Default

yay!
LaurV is offline   Reply With Quote
Old 2020-08-30, 11:31   #30
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

5×181 Posts
Default

Fantastic! I've been following the git repo watching the continuing improvements to the code.
danaj is offline   Reply With Quote
Old 2020-08-30, 20:38   #31
kwalisch
 
kwalisch's Avatar
 
Sep 2015

1116 Posts
Default

Quote:
Originally Posted by danaj View Post
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.
kwalisch is offline   Reply With Quote
Old 2020-08-31, 03:01   #32
rudy235
 
rudy235's Avatar
 
Jun 2015
Vallejo, CA/.

3C116 Posts
Default

Well, I must say it is impressive.

Congratulations to both of you.
rudy235 is offline   Reply With Quote
Old 2020-08-31, 16:58   #33
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

5,923 Posts
Default

Quote:
Originally Posted by kwalisch View Post
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.
CRGreathouse is offline   Reply With Quote
Reply

Thread Tools


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

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

Thu Sep 24 08:38:12 UTC 2020 up 14 days, 5:49, 0 users, load averages: 1.19, 1.40, 1.42

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.