Go Back > Great Internet Mersenne Prime Search > Software

Thread Tools
Old 2016-03-30, 19:49   #1
Mark Rose
Mark Rose's Avatar
Jan 2013

3·977 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's Avatar
Sep 2002
Database er0rr

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

1D4416 Posts

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 online now   Reply With Quote
Old 2016-03-31, 01:28   #4
Mark Rose
Mark Rose's Avatar
Jan 2013

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

Thread Tools

All times are UTC. The time now is 23:34.

Mon May 17 23:34:18 UTC 2021 up 39 days, 18:15, 0 users, load averages: 2.33, 2.05, 2.17

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.