2016-03-30, 19:49 | #1 |
"/X\(‘-‘)/X\"
Jan 2013
3·977 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 |
Sep 2002
Database er0rr
E5C_{16} 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 3*2^n-1 was faster than other larger "k". Last fiddled with by paulunderwood on 2016-03-30 at 20:36 |
2016-03-30, 23:38 | #3 |
P90 years forever!
Aug 2002
Yeehaw, FL
1D44_{16} Posts |
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. |
2016-03-31, 01:28 | #4 |
"/X\(‘-‘)/X\"
Jan 2013
B73_{16} 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.) |