Prime95: LL vs PRP

Mark Rose · 2016-03-30, 19:49

First let me preface this by saying math isn't my strong suit. I'm here because I find distributed projects fun. Another project I participate in is SeventeenOrBust, which uses Prime95 for a PRP tests.

I'm curious as to how much of the code is shared between the LL and PRP implementations in Prime95, especially with regards to the amount of execution time. I hope someone can enlighten me.

paulunderwood · 2016-03-30, 20:00

Both do about log_2(n) FFT squarings and "special" modular reductions. LL is very slightly more efficient in that it is doing s <- s^2- 2 whereas a PRP test needs to multiply by the base if there is a "1" at that point in its binary string.

In the nitty gritty of the implementation LL is faster. For example 3*2^n-1 was faster than other larger "k".

Prime95 · 2016-03-30, 23:38

Quote:

Originally Posted by paulunderwood

LL is very slightly more efficient .

This can vary. Both LL and PRP use the same FFT code which tests numbers of the form k*b^n+/-c. The modular reduction is most efficient when k=2 and c=1 (i.e. perfect for LL tests). SeventeenOrBust tests k values from something like 4000 to 60000, which forces larger FFTs than would be required for an LL test. You're probably looking at double the runtime for k=60000, on the order of maybe 1.5x for k=4000.

Paul's example of 3*2^n-1 is often just as fast as an LL test because of the small k value, but sometimes it is a little slower as the next higher FFT size will be required.

Mark Rose · 2016-03-31, 01:28

Thanks, guys. That answered my question.

SoB is well behind GIMPS when it comes to FFT size. The current assignments I'm getting use a 2880K FFT, such as 24737*2^30623287+1. mprime 28.6 is giving 7.0 ms/iter with 3 Haswell cores at 3.4 GHz and 1600 MHz DDR3 RAM.

SoB has very little throughput compared to GIMPS. There are only 1243 outstanding tests at the moment. I'm responsible for about 7.5% of production there with a dozen or so 24-hour-equivalent CPU cores dedicated to SoB. (That's not counting the related work the Prime Sierpinski Problem project is doing.)

2016-03-30, 19:49	#1
Mark Rose "/X\(‘-‘)/X\" Jan 2013 5561₈ Posts	Prime95: LL vs PRP First let me preface this by saying math isn't my strong suit. I'm here because I find distributed projects fun. Another project I participate in is SeventeenOrBust, which uses Prime95 for a PRP tests. I'm curious as to how much of the code is shared between the LL and PRP implementations in Prime95, especially with regards to the amount of execution time. I hope someone can enlighten me.

2016-03-30, 20:00	#2
paulunderwood Sep 2002 Database er0rr 3,533 Posts	Both do about log_2(n) FFT squarings and "special" modular reductions. LL is very slightly more efficient in that it is doing s <- s^2- 2 whereas a PRP test needs to multiply by the base if there is a "1" at that point in its binary string. In the nitty gritty of the implementation LL is faster. For example 32^n-1 was faster than other larger "k". Last fiddled with by paulunderwood on 2016-03-30 at 20:36*

2016-03-31, 01:28	#4
Mark Rose "/X\(‘-‘)/X\" Jan 2013 B71₁₆ Posts	Thanks, guys. That answered my question. SoB is well behind GIMPS when it comes to FFT size. The current assignments I'm getting use a 2880K FFT, such as 24737*2^30623287+1. mprime 28.6 is giving 7.0 ms/iter with 3 Haswell cores at 3.4 GHz and 1600 MHz DDR3 RAM. SoB has very little throughput compared to GIMPS. There are only 1243 outstanding tests at the moment. I'm responsible for about 7.5% of production there with a dozen or so 24-hour-equivalent CPU cores dedicated to SoB. (That's not counting the related work the Prime Sierpinski Problem project is doing.)