Author 
Message 

Just curious. Is it theoretically possible to have a PPSDYFL subproject (PPS  Do You Feel Lucky?) that searches, for instance, the range 1200<k<10000 and n>=82589926? Are there hardware/software limitations?
____________
My DC mathematical side :)




Too long for us to test. Using Yves' Proth2.0 ocl though it could be possible...?
Look at the SoB tasks which are at 32M. and then compare 32M to 82M and note there's a exponential increase in time as the exponent grows (hmm, pun).
____________
My lucky number is 6219*2^3374198+1




If you were to go to such high exponents n, surely you would pick tiny k, like k = 3; 5; 7; etc.?
You could try to start LLR on one such candidate, like 3*2^82589933 + 1. I do not know if it will run. If it will, it will take a LONG time.
I suspect Yves's upcoming GPU Proth application will be unable to cope with such huge numbers.
/JeppeSN 



Well, long run times don't shock me. Mersenne prime searchers are testing the 90100M range.
Yeah, k could be chosen lower.
____________
My DC mathematical side :)



Michael GoetzVolunteer moderator Project administrator
Send message
Joined: 21 Jan 10 Posts: 13804 ID: 53948 Credit: 345,369,032 RAC: 6,456

Can you? Sure. The question is why?
Obviously, any number of that size takes a long time to test. If the goal is specifically to find a world record prime, and you don't really care what kind of number you're testing, you would pick the type of number with the fastest test.
That's why GIMPS is searching Mersenne numbers.
The second fastest number to test are Generalized Fermat numbers. That's why we're searching GFNDYFL.
Is there a reason to search Proth numbers of that size? If the goal is to find a world record prime, Generalized Fermat numbers are better.
____________
My lucky number is 75898^{524288}+1 



Suppose you discovered a 3*2^n + 1 prime greater than all known Mersenne primes (world record prime). It would take an incredible amount of time to find out what ((x)G)F numbers it divided. /JeppeSN 



Ok, Micheal's answer is very clear. Thanks!
I will try to understand how much Proth numbers primality tests are slower.
If I search for a world record prime, I would care that my prime will be beautiful/elegant.
I like primorial/factorial primes because only 1 number (and +/ 1) is needed to represent them. :)
____________
My DC mathematical side :)



rogueVolunteer developer
Send message
Joined: 8 Sep 07 Posts: 1249 ID: 12001 Credit: 18,565,548 RAC: 0

I like primorial/factorial primes because only 1 number (and +/ 1) is needed to represent them. :)
Both primorial and factorial searches are due. It has been nearly 8 years since the last primorial prime and 6.5 years since the last factorial prime. 


mackerelVolunteer tester
Send message
Joined: 2 Oct 08 Posts: 2584 ID: 29980 Credit: 550,654,016 RAC: 13,199

You could try to start LLR on one such candidate, like 3*2^82589933 + 1. I do not know if it will run. If it will, it will take a LONG time.
Just tried it with LLR, before moving to using Prime95 built in benchmark function with a 4608k FFT reported by LLR as required. Timings were similar.
As a rough estimate, it'll take 5.5 to 6 days on a 6 core Coffee Lake running at 4 GHz with 3200 dual channel, single rank ram. This would likely go down with faster ram, more so than faster CPU.
A 7920X with 12 cores at 2.9 GHz (turbo disabled), quad channel 2DPC 3000 ram, could do it in under 2 days. I'd guess it is still more ram bandwidth limited than CPU limited.
Intel CPUs don't have the cache so it'll be ram bandwidth limited. Zen 2 has more cache, but because it is not unified it doesn't fully unleash its core potential, although still gives some boost relative to the ram bandwidth considered alone. 



I suspect Yves's upcoming GPU Proth application will be unable to cope with such huge numbers.
Where is this being discussed? What has changed in the last couple of years that makes LLR on GPU reasonable now?
____________



Ravi FernandoProject administrator Volunteer tester Project scientist Send message
Joined: 21 Mar 19 Posts: 206 ID: 1108183 Credit: 11,958,242 RAC: 5,116

I suspect Yves's upcoming GPU Proth application will be unable to cope with such huge numbers.
Where is this being discussed? What has changed in the last couple of years that makes LLR on GPU reasonable now?
Yves has told us about it on the PG Discord server. There's also some discussion on the Mersenne forum here. 


Yves GallotVolunteer developer Project scientist Send message
Joined: 19 Aug 12 Posts: 712 ID: 164101 Credit: 305,166,630 RAC: 0

Where is this being discussed? What has changed in the last couple of years that makes LLR on GPU reasonable now?
This is not LLR. LLR is based on complex FFT and 64bit FP numbers. That's efficient on CPU because of fast AVX or AVX512 units. But GPUs have no fast 64bit FP units (except expensive Tesla with GP100 or GV100).
proth20 is based on a Number Theoretic Transform. A good point with this method is that the primality proof is deterministic.
We can test a 24Mdigit Proth number with proth20 but the size of the transform is 2^23. With genefer, the size of the transform of a 24Mdigit generalized Fermat number is 2^22. genefer is twice as fast. The reason for this is that the transform of genefer (which is not based on FFTs) computes P(x)^2 (mod x^{2^n} + 1). We can apply the same method to cyclotomic polynomials as x^{2^n}  x^{2^{n1}} + 1 (Phi(3, 123447^524288) was found by this method). But Proth numbers are not "cyclotomic numbers" then we have to compute P(x)^2 and reduce the result modulo k·2^n+1. Is it possible to compute a sort of IBDWT with integers and a fast deterministic Proth test? ... I haven't found it. 


compositeVolunteer tester Send message
Joined: 16 Feb 10 Posts: 1022 ID: 55391 Credit: 887,640,929 RAC: 145,920

Is it possible to compute a sort of IBDWT with integers and a fast deterministic Proth test? ... I haven't found it.
How far does this all integer IBDWT (GitHub) get you toward that goal?



Yves GallotVolunteer developer Project scientist Send message
Joined: 19 Aug 12 Posts: 712 ID: 164101 Credit: 305,166,630 RAC: 0

Is it possible to compute a sort of IBDWT with integers and a fast deterministic Proth test? ... I haven't found it.
How far does this all integer IBDWT (GitHub) get you toward that goal?
I didn't know that code (I prefer the C version ioccc2012/mersenne.c).
Very interesting, now the idea is to mix it with Colin Percival's multiplication Rapid multiplication modulo the sum and difference of highly composite numbers.
Some good work for the future... :o) 

