Comment by lkbm | Hacker News Reader

Comment by lkbm | Hacker News Reader

Looking at the recent history:

  2020-11-27 All exponents below 99 million tested at least once.
  2020-11-17 All exponents below 98 million tested at least once.
  2020-11-17 All exponents below 97 million tested at least once.
  2020-11-09 All exponents below 96 million tested at least once.
  2020-11-03 All exponents below 95 million tested at least once.
  2020-10-24 All exponents below 94 million tested at least once.
  2020-10-09 All exponents below 93 million tested at least once.
  2020-10-04 All exponents below 92 million tested at least once.
  2020-06-20 All exponents below 91 million tested at least once.
  2020-04-09 All exponents below 90 million tested at least once.
  2020-03-01 All exponents below 89 million tested at least once.

What happened in June/July that caused it to stop, and in October to make it suddenly restart? Did they just switch from sequential to a grouping that checked all but a small portion of each million undone until November?

  September 17, 2020 All tests below 53 million verified.

Makes me think part of it is them spending extra time verifying old tests. Just curious 1. if that's all it is and 2. why / whether this was triggered by something. Was there a bug found that raised doubt in previous tests?

EDIT: Formatting

Ben Delo joined the project and has been running several hundred AWS cores.[1]

Slightly related a new method to validate the result was found which means that they no longer need to run a 2nd double check run to validate that there wasn't floating point rounding errors[2]. Interestingly this credits a HN thread as the source of inspiration[3].

[1] https://www.mersenneforum.org/showthread.php?t=24819&highlig... [2] https://mersenneforum.org/showthread.php?p=546560 [3] https://news.ycombinator.com/item?id=20587753

I'm only tangencially related to the project, but I do have a spare machine running the software.

Yes, there was a big push to re-verify old abandoned tests. First, understand that the project requires multiple tests results from each exponent - I believe it needs a triplicate confirmation (ie 3 different computers have to run the same test and all have to match) At some point, they developed a new, different algorithm that can do the check in one go (but it's more expensive computationally). However, most of the pre-existing work was done using the type of calculation that needed the triplicate check.

There were a lot of exponents where some computer claimed one of the "verification tests" (ie it was already rejected as a prime, but we needed 2 more computers to verify), but then stopped mid way (it's pretty common since these primality tests take about 3-5 days on a modern fast threadripper - so it could take up to a month on slower machines from years ago).

It's very unlikely that these exponents signified primes (since they were already verified to NOT be prime by 1 computer, and it's just the rechecks that are pending) These abandoned exponents formed a huge amount of "leftovers" that people didn't want as work units because they are most likely not prime, and if you were hunting for primes, these are not the work you want to do.

So at some point, the project said they wanted a big push into picking up abandoned re-verifications and giving them a much higher priority to computers that could complete the test in a few days [either by finishing off what was left of the triplicate check, or by using the new algorithm that just needed one pass] - thus getting them out of the queue once and for all for good. If you have a fast computer (ie modern day i9, threadripper, xeon, anything with AVX512, etc) chances are you were assigned this type of rechecking task unless you rejected the work units.

It's not just the gap you noticed in June, this whole project of looking for and verifying old exponents has been ongoing for the bulk of 2020.

Another idea is that the project is always trying out new number techniques and algorithms and always looking for new instruction sets to use etc - a change or tweek in algorithm could cause this kind of "pause" as well, the client computers don't make the shift all at once (there's likely some verification, where a small subset of clients run both algorithms in parallel to see if the results are the same, etc) and then machines are moved onto the new algorithm as verifications are complete, etc.

EDIT: As I wrote this post, I started remembering more about the different algorithms the projects used. All of the text above can be check with the prime95 forums, where they discuss these algorithm changes, the push to re-verify, etc.

I'm an active and more acknowledged member of the project.

To explain and correct things:

There are two types of primality checking algorithms for Mersenne numbers, PRP (probable-prime test) and LL (Lucas-Lehmer test). PRP does only say that the number is most probably prime, whereas LL, if correctly computed, says it with 100% certainty (i.e. it definitely is or definitely is not a prime). PRP tests have better error correction algorithms, and new feature is "Certification", which is rather complicated, but basically, it can confirm, that PRP was done correctly, but if the PRP indicates that number is prime, LL must be still done to be sure. LL test can have a lot more error, that are unnoticed by the existing error correction (which is different from the one used for PRP), thus it has to be at least DOUBLE-checked, not triple-checked. Triple checks are only necessary if the previous two runs don't match. If not even third run matches, fourth one is run, etc.

The order of assigning tasks is not uniform at all, there are "Categories" of assignments. Simply said, the more assignments computer finishes and turns in, the lower numbers it can get assigned next. If it returns a result, that turns out to be bad, it is downgraded in the eyes of the server, meaning it kind of goes back to the higher exponents. This is done so that the "wavefront" moves as quickly as possible with current amount of computing power.

I will probably write more later. Until then, you all can explore the page, especially the "More Information / Help" tab.

Reply on news.ycombinator.com