| Author |
Message |
|---|
|
|
|
Just curious. Is it theoretically possible to have a PPS-DYFL 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 90-100M range.
Yeah, k could be chosen lower.
____________
My DC mathematical side :)
|
|
|
 Michael Goetz Volunteer moderator
Project administrator
Send message
Joined: 21 Jan 10
Posts: 13881
ID: 53948
Credit: 383,625,495
RAC: 119,859
                              
|
|
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 GFN-DYFL.
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 75898524288+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: 1255
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: 2619
ID: 29980
Credit: 566,961,020
RAC: 14,993
                       
|
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: 210
ID: 1108183
Credit: 13,047,881
RAC: 6,479
              
|
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: 779
ID: 164101
Credit: 305,422,075
RAC: 4,243
|
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 64-bit FP numbers. That's efficient on CPU because of fast AVX or AVX-512 units. But GPUs have no fast 64-bit 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 24M-digit Proth number with proth20 but the size of the transform is 2^23. With genefer, the size of the transform of a 24M-digit 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^{n-1}} + 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: 1099
ID: 55391
Credit: 959,419,215
RAC: 871,392
             
|
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: 779
ID: 164101
Credit: 305,422,075
RAC: 4,243
|
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) |
|
|
