mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Software

Reply
 
Thread Tools
Old 2016-03-30, 19:49   #1
Mark Rose
 
Mark Rose's Avatar
 
"/X\(‘-‘)/X\"
Jan 2013

B7116 Posts
Default 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.
Mark Rose is offline   Reply With Quote
Old 2016-03-30, 20:00   #2
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

3,617 Posts
Default

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
paulunderwood is offline   Reply With Quote
Old 2016-03-30, 23:38   #3
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

23·52·37 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
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.
Prime95 is offline   Reply With Quote
Old 2016-03-31, 01:28   #4
Mark Rose
 
Mark Rose's Avatar
 
"/X\(‘-‘)/X\"
Jan 2013

B7116 Posts
Default

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.)
Mark Rose is offline   Reply With Quote
Reply

Thread Tools


All times are UTC. The time now is 01:13.

Sun Apr 11 01:13:54 UTC 2021 up 2 days, 19:54, 1 user, load averages: 1.98, 1.74, 1.52

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