## Other

drummers-lowrise

Message boards : Proth Prime Search : Naive question about 24M-digits PPS numbers

Author Message
Luigi R.

Joined: 11 Feb 14
Posts: 165
ID: 297455
Credit: 38,836,937
RAC: 0

Message 137239 - Posted: 5 Feb 2020 | 10:14:29 UTC

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 :)

dannyridel
Volunteer tester

Joined: 3 Feb 19
Posts: 791
ID: 1097922
Credit: 3,783,734
RAC: 0

Message 137242 - Posted: 5 Feb 2020 | 11:52:41 UTC - in response to Message 137239.

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).
____________
SHSID Electronics Group
SHSIDElectronicsGroup@outlook.com

GFN-14: 50103906^16384+1
Proth "SoB": 44243*2^440969+1

JeppeSN

Joined: 5 Apr 14
Posts: 1378
ID: 306875
Credit: 21,623,822
RAC: 0

Message 137244 - Posted: 5 Feb 2020 | 11:54:14 UTC

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

Luigi R.

Joined: 11 Feb 14
Posts: 165
ID: 297455
Credit: 38,836,937
RAC: 0

Message 137246 - Posted: 5 Feb 2020 | 12:27:15 UTC

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

Joined: 21 Jan 10
Posts: 13513
ID: 53948
Credit: 236,922,854
RAC: 0

Message 137247 - Posted: 5 Feb 2020 | 12:40:23 UTC

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

JeppeSN

Joined: 5 Apr 14
Posts: 1378
ID: 306875
Credit: 21,623,822
RAC: 0

Message 137249 - Posted: 5 Feb 2020 | 12:51:41 UTC

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

Luigi R.

Joined: 11 Feb 14
Posts: 165
ID: 297455
Credit: 38,836,937
RAC: 0

Message 137253 - Posted: 5 Feb 2020 | 13:45:44 UTC - in response to Message 137247.

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 :)

rogue
Volunteer developer

Joined: 8 Sep 07
Posts: 1218
ID: 12001
Credit: 18,565,548
RAC: 0

Message 137272 - Posted: 5 Feb 2020 | 20:29:32 UTC - in response to Message 137253.

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.

mackerel
Volunteer tester

Joined: 2 Oct 08
Posts: 2460
ID: 29980
Credit: 442,802,854
RAC: 0

Message 137277 - Posted: 5 Feb 2020 | 21:08:06 UTC - in response to Message 137244.

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.

Michael Millerick
Volunteer tester

Joined: 4 Feb 09
Posts: 743
ID: 35074
Credit: 199,599,590
RAC: 0

Message 137300 - Posted: 6 Feb 2020 | 5:10:07 UTC

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 Fernando
Volunteer tester
Project scientist

Joined: 21 Mar 19
Posts: 144
ID: 1108183
Credit: 8,505,009
RAC: 0

Message 137302 - Posted: 6 Feb 2020 | 5:48:49 UTC - in response to Message 137300.

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 Gallot
Volunteer developer
Project scientist

Joined: 19 Aug 12
Posts: 644
ID: 164101
Credit: 305,010,093
RAC: 0

Message 137308 - Posted: 6 Feb 2020 | 9:46:14 UTC - in response to Message 137300.

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.

composite
Volunteer tester

Joined: 16 Feb 10
Posts: 769
ID: 55391
Credit: 696,046,522
RAC: 0

Message 137317 - Posted: 6 Feb 2020 | 13:56:06 UTC - in response to Message 137308.

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 Gallot
Volunteer developer
Project scientist

Joined: 19 Aug 12
Posts: 644
ID: 164101
Credit: 305,010,093
RAC: 0

Message 137329 - Posted: 6 Feb 2020 | 17:11:10 UTC - in response to Message 137317.

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)

Message boards : Proth Prime Search : Naive question about 24M-digits PPS numbers