Hi msft,

Having observed the development effort of this CUDA LL testing application over time, I see that it's already faster than Prime95 on a modern CPU and as such represents a significant speedup for GIMPS once it's distributed more widely. However, I can't help but wonder how hard it would be to modify this program to utilize the [URL="http://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer%E2%80%93Riesel_test"]Lucas-Lehmer-Riesel test[/URL]--it is a very small modification of the [URL="http://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer_primality_test"]Lucas-Lehmer test[/URL] that allows it to test numbers of the form k*2^n-1, a.k.a. Riesel primes, versus LL's 2^n-1. As you can see from the Wikipedia pages linked here, the two tests differ only in their starting value: for LL it is always 4, whereas for LLR it is determined by a dynamic formula based on the value of k.

I co-adminstrate the "No Prime Left Behind" project (which can be found in the "Prime Search Projects" section of this forum) along with Gary Barnes (who goes by gd_barnes on this forum), a project which tests k*2^n-1 numbers for primality. The other day we were discussing GPUs and the recent advances in LL testing, and were thinking how big a boost it would be for NPLB (and all the other myriad projects that search Riesel primes) if this application could be modified for the LLR test. Neither of us have any CUDA programming knowledge, and thus wouldn't be able to make the code changes ourselves. However, we would be willing to help test such an application if it was developed. Gary said that he would be willing to purchase a reasonably fast CUDA-capable GPU for the purposes of testing such a CUDA LLR application if progress was begun on development of such; I could then (via remote access to his system) assist in debugging and verifying the accuract of the application. NPLB has tons of residuals from the various LLR tests we've done, so we'd have plenty of material with which to doublecheck the GPU's accuracy. :smile:

Note that the tests NPLB is doing are much smaller than GIMPS's: mostly for n<1M, with some between 1M and 2M. Other projects test higher n, though usually no higher than 10M at the max. (Since k is a variable for Riesel primes, and they don't have all the handy factoring "shortcuts" available for Mersenne numbers, needless to say, Riesel primes haven't been advanced nearly as far in terms of n yet.) This translates into smaller FFTs, usually less than 100K, that would be primarily used in such an LLR program.

Would you (or anyone else here with CUDA experience) be interested in embarking on such an effort? I estimate that the code change to MacLucasFFTW to make it do LLR tests would be rather trivial; perhaps more consuming would be the optimization of the smaller FFTs most commonly used in the program. However, since such optimization would take place within the FFT library itself as opposed to the LLR-specific code, such improvements would benefit the LL test application as well.

Thanks,
Max :smile:

Max, if you look at the end of the [URL="http://www.mersenneforum.org/showthread.php?p=214866"]llr 3.8 thread[/URL] you will see that Jean is developping llr to be half way there to using cuda. He will be using the same or very similar(there was also not mention of mac) fft library I think but a non-CUDA version.

Another option would be to rip the llr code(working out the starting value etc.) from LLR and adding it into the CUDA program we have here. That would be a lot of the work done. We would have to ask permission of course but I am pretty certain that he would support it.

edit: i seem to remember that primegrid have developed a CUDA sieve that might be helpful to NPLB. they might be willing to help make a CUDA llr.

Changing the starting value is easy. Changing the modulus in each iteration may be more involved?

[quote=henryzz;218242]Max, if you look at the end of the [URL="http://www.mersenneforum.org/showthread.php?p=214866"]llr 3.8 thread[/URL] you will see that Jean is developping llr to be half way there to using cuda. He will be using the same or very similar(there was also not mention of mac) fft library I think but a non-CUDA version.

Another option would be to rip the llr code(working out the starting value etc.) from LLR and adding it into the CUDA program we have here. That would be a lot of the work done. We would have to ask permission of course but I am pretty certain that he would support it.

edit: i seem to remember that primegrid have developed a CUDA sieve that might be helpful to NPLB. they might be willing to help make a CUDA llr.[/quote]
Ah, I forgot about Jean's mention of that. However, I was thinking that it might simply be easier to modify this program; after all, as frmky said, it's easy enough to change the starting value the program uses, which AFAIK is the only difference between LL and LLR. I expect that would be easier even than trying to integrate Jean's existing LLR code with this code's CUDA FFT library.

I wasn't aware that PrimeGrid had a CUDA sieve. Does it work for k*b^n+-c numbers, or only for one of their other types of searches (AP26, etc.)?
[quote=frmky;218246]Changing the starting value is easy. Changing the modulus in each iteration may be more involved?[/quote]
Hmm, I didn't think of that. How much harder do you think it would be?

As for CUDA-enabled sieves, I have been pointed to Ken_g5 ppsieve.

I compiled it under both Linux and Windows, but I had problems passing an ABC(D) file to it.

Anybody here having hints? :smile:

Luigi

[quote=ET_;218312]As for CUDA-enabled sieves, I have been pointed to Ken_g5 ppsieve.

I compiled it under both Linux and Windows, but I had problems passing an ABC(D) file to it.

Anybody here having hints? :smile:

Luigi[/quote]
Yes thats the one [url]http://www.primegrid.com/forum_thread.php?id=1737[/url]

[QUOTE=henryzz;218418]Yes thats the one [url]http://www.primegrid.com/forum_thread.php?id=1737[/url][/QUOTE]

Maybe I made errors while explainig...

I correctly compiled and run ppsieve on Linux.

I don't need the file with the factors.

I need a siever like the one I downloaded from Ken's page,[COLOR="Red"] able to read and update an ABC(D) file[/COLOR], because the version I have just can't (or has hidden parameters I can't see).

That's why I asked for help. :smile:

Luigi

[quote=ET_;218435]Maybe I made errors while explainig...

I correctly compiled and run ppsieve on Linux.

I don't need the file with the factors.

I need a siever like the one I downloaded from Ken's page,[COLOR=Red] able to read and update an ABC(D) file[/COLOR], because the version I have just can't (or has hidden parameters I can't see).

That's why I asked for help. :smile:

Luigi[/quote]
Do you mean you need a program that produces files you can feed to ppsieve?
If so try googling srsieve.

[QUOTE=henryzz;218437]Do you mean you need a program that produces files you can feed to ppsieve?
If so try googling srsieve.[/QUOTE]

No... :smile:

Issue 1:

I have a correct ABCD file, produced by FermFact.
The file is correct, as pfgw reads it with no problem.

When I feed ppsieve with that ABCD file, ppsieve says it can't recognize the file.
---

Issue 2:

When I try to run ppsieve from scratch, all I can get is a "factors" file. No ABC or D file.

Luigi

[quote=ET_;218516]No... :smile:

Issue 1:

I have a correct ABCD file, produced by FermFact.
The file is correct, as pfgw reads it with no problem.

When I feed ppsieve with that ABCD file, ppsieve says it can't recognize the file.
---

Issue 2:

When I try to run ppsieve from scratch, all I can get is a "factors" file. No ABC or D file.

Luigi[/quote]I believe ppsieve only works with k*2^n+-1 numbers (base 2 Riesel/Proth) [Issue 1] and it's designed to continue sieves already started with a program like [URL="http://sites.google.com/site/srsieve/"]srsieve[/URL], not start a fresh sieve [Issue 2].

[QUOTE=mdettweiler;218517]I believe ppsieve only works with k*2^n+-1 numbers (base 2 Riesel/Proth) [Issue 1] and it's designed to continue sieves already started with a program like [URL="http://sites.google.com/site/srsieve/"]srsieve[/URL], not start a fresh sieve [Issue 2].[/QUOTE]

Thank you, so Issue 2 is cleared :smile:

As for k*2^n+/-1, they are quite the numbers I'm sieving as possible Fermat factors...

Luigi