PrimeGrid
Please visit donation page to help the project cover running costs for this month

Advanced search

Message boards : Sieving : Combining GFN sieves with different n

Author Message
Profile MyrskylyhtyProject donor
Avatar
Send message
Joined: 27 Jan 18
Posts: 116
ID: 972376
Credit: 543,868,707
RAC: 7,567
Discovered 1 mega primeFound 1 prime in the 2019 Tour de PrimesFound 1 prime in the 2020 Tour de PrimesFound 1 prime in the 2021 Tour de Primes321 LLR Double Bronze: Earned 100,000,000 credits (109,329,259)Cullen LLR Gold: Earned 500,000 credits (533,200)ESP LLR Gold: Earned 500,000 credits (808,848)Generalized Cullen/Woodall LLR Silver: Earned 100,000 credits (472,570)PPS LLR Jade: Earned 10,000,000 credits (15,031,331)PSP LLR Amethyst: Earned 1,000,000 credits (1,379,782)SoB LLR Ruby: Earned 2,000,000 credits (3,570,885)SR5 LLR Amethyst: Earned 1,000,000 credits (1,583,505)SGS LLR Silver: Earned 100,000 credits (128,562)TRP LLR Amethyst: Earned 1,000,000 credits (1,126,846)Woodall LLR Silver: Earned 100,000 credits (380,849)321 Sieve (suspended) Gold: Earned 500,000 credits (573,292)Generalized Cullen/Woodall Sieve (suspended) Amethyst: Earned 1,000,000 credits (1,069,231)PPS Sieve Emerald: Earned 50,000,000 credits (61,446,588)AP 26/27 Ruby: Earned 2,000,000 credits (2,494,531)GFN Double Silver: Earned 200,000,000 credits (258,863,912)PSA Emerald: Earned 50,000,000 credits (85,075,515)
Message 116253 - Posted: 21 Mar 2018 | 11:39:37 UTC
Last modified: 21 Mar 2018 | 12:18:47 UTC

This is based on my brainstorming on the discord chat, but I also want to post it here to bring discussion.

So the idea is, that since we sieve GFN of specific n for B values ranging from 2 to 2,000,000,000, could we use that sieve also for the higher n GFN project? Specifically, this idea would only apply for new projects.

Using GFN22 and GFN23 as an example, we can easily show that

(B^2)^2^22 = (B)^2^23,

which means that all values of B from GFN22 correspond to another B value in GFN23, with the relation

sqrt(B_22) = B_23.

Now, since we will already be testing B values from 2(?) to 400,000,000, we wont want to do those again, so we can instantly remove the corresponding B's from the higher n, which correspond to B_23 values from 2 to 20,000 (=sqrt(400,000,00)). (Or vice versa; we could exclude these from the lower n (undone ones, actually)).

We are left with B_23 values from 20,000 to 44,720 (~sqrt(2,000,000,000)), for which you could use the sievefile from GFN22. If we assume that the sieved-% for GFN22 is the same to up to B=2,000,000,000 than it is to 100,000,000, we can already exclude 58,56% (source: http://www.primegrid.com/sieving/gfn/#R4194304) of candidates from GFN23 (B = 20,000 to 44,720) using the GFN22 sieve file.

Probably when the time comes, its more efficient to sieve GFN23 even deeper than GFN22, but until that work is done, we could already work on 20,000 to 44720 (=5121 candidates with the above sieve-%) with a "ready" sievefile. Assuming that same amount of work is done for that as for GFN22 (~33 tasks a day), we could maybe do 10 tasks (=5 workunits) a day, which would mean that this range has work for nearly 3 years.

A few another ideas come up from this:
-If the B upper limit for GFN sieving could go up at some point, we could reach even higher.
-Vice versa: does it save any computation time to exclude B=2 to 44720, from GFN sieving, since those are already done at lower n sieving (altough not to same depth probably).

What do you think about this idea? Do you notice any mistakes? Is it something that could be used? Or is actually already used, but I just couldn't find the documentation about it? Will GFN23 ever be even started?

One last question: Is there an computing-efficiency difference between lower B, higher n and higher B, lower n? i.e. would testing 10,000^2^23+1 be faster than testing 100,000,000^2^22+1?

EDIT: formatted the equation to a bit more understandable form.

Gabriel LignelliProject donor
Avatar
Send message
Joined: 1 Sep 13
Posts: 61
ID: 251415
Credit: 10,423,448
RAC: 0
Found 1 prime in the 2018 Tour de Primes321 LLR Bronze: Earned 10,000 credits (53,871)Cullen LLR Bronze: Earned 10,000 credits (15,017)ESP LLR Bronze: Earned 10,000 credits (62,595)Generalized Cullen/Woodall LLR Bronze: Earned 10,000 credits (21,984)PPS LLR Silver: Earned 100,000 credits (136,702)PSP LLR Bronze: Earned 10,000 credits (47,301)SoB LLR Silver: Earned 100,000 credits (305,770)SR5 LLR Bronze: Earned 10,000 credits (18,306)SGS LLR Bronze: Earned 10,000 credits (14,608)TRP LLR Silver: Earned 100,000 credits (282,537)Woodall LLR Bronze: Earned 10,000 credits (33,562)321 Sieve (suspended) Gold: Earned 500,000 credits (865,427)Generalized Cullen/Woodall Sieve (suspended) Ruby: Earned 2,000,000 credits (2,397,311)PPS Sieve Ruby: Earned 2,000,000 credits (2,349,587)AP 26/27 Amethyst: Earned 1,000,000 credits (1,475,695)GFN Ruby: Earned 2,000,000 credits (2,056,798)PSA Silver: Earned 100,000 credits (286,377)
Message 116256 - Posted: 21 Mar 2018 | 13:31:41 UTC - in response to Message 116253.
Last modified: 21 Mar 2018 | 13:33:43 UTC

One last question: Is there an computing-efficiency difference between lower B, higher n and higher B, lower n? i.e. would testing 10,000^2^23+1 be faster than testing 100,000,000^2^22+1?

From my limited testing with Genefer and LLR, it seems that lower B, higher n is faster than higher B, lower n. For LLR it seems to mainly come down to FFT size, where a lower B will yield smaller FFT sizes. This is also probably true for Genefer, however another compounding factor in this case is the transform used. For a lower B, higher n, it is likely that a faster transform may be used when compared to higher B, lower n. LLR seems to also have different transforms (all-complex vs. generic reduction) but I don't know how to interpret and compare these, other than to say that all-complex (lower B, higher n) seems a lot faster than generic reduction (higher B, lower n).
Edit: forgot to mention that, interestingly, Genefer outputs different residues for the two different forms while LLR gives the same residue for both. It is, after all, the same candidate, so one would reasonably expect the same residue, regardless of written form.
____________

Profile MyrskylyhtyProject donor
Avatar
Send message
Joined: 27 Jan 18
Posts: 116
ID: 972376
Credit: 543,868,707
RAC: 7,567
Discovered 1 mega primeFound 1 prime in the 2019 Tour de PrimesFound 1 prime in the 2020 Tour de PrimesFound 1 prime in the 2021 Tour de Primes321 LLR Double Bronze: Earned 100,000,000 credits (109,329,259)Cullen LLR Gold: Earned 500,000 credits (533,200)ESP LLR Gold: Earned 500,000 credits (808,848)Generalized Cullen/Woodall LLR Silver: Earned 100,000 credits (472,570)PPS LLR Jade: Earned 10,000,000 credits (15,031,331)PSP LLR Amethyst: Earned 1,000,000 credits (1,379,782)SoB LLR Ruby: Earned 2,000,000 credits (3,570,885)SR5 LLR Amethyst: Earned 1,000,000 credits (1,583,505)SGS LLR Silver: Earned 100,000 credits (128,562)TRP LLR Amethyst: Earned 1,000,000 credits (1,126,846)Woodall LLR Silver: Earned 100,000 credits (380,849)321 Sieve (suspended) Gold: Earned 500,000 credits (573,292)Generalized Cullen/Woodall Sieve (suspended) Amethyst: Earned 1,000,000 credits (1,069,231)PPS Sieve Emerald: Earned 50,000,000 credits (61,446,588)AP 26/27 Ruby: Earned 2,000,000 credits (2,494,531)GFN Double Silver: Earned 200,000,000 credits (258,863,912)PSA Emerald: Earned 50,000,000 credits (85,075,515)
Message 116258 - Posted: 21 Mar 2018 | 14:17:22 UTC - in response to Message 116256.
Last modified: 21 Mar 2018 | 14:17:36 UTC

It seems the for GFN, lower n is actually better:

152423716^32768+1 is composite. (RES=0000000000000000) (268143 digits) (err = 0.0000) (time = 0:00:52) 15:48:05
12346^65536+1 is composite. (RES=0000000000000000) (268143 digits) (err = 0.0000) (time = 0:01:03) 15:49:29

and

Estimated time for 10000^262144+1 is 0:13:40
Estimated time for 100^524288+1 is 0:26:40

Also, I received a response that the sieve files are taken into account at higher n. So my post is essentially "old news".

Nevertheless, I'll leave it here for everyone to ponder. Maybe it helps someone else come up with something even better :)

Profile JeppeSNProject donor
Avatar
Send message
Joined: 5 Apr 14
Posts: 1849
ID: 306875
Credit: 52,230,046
RAC: 17,829
Found 1 prime in the 2020 Tour de Primes321 LLR Gold: Earned 500,000 credits (684,183)Cullen LLR Gold: Earned 500,000 credits (611,298)ESP LLR Silver: Earned 100,000 credits (174,818)Generalized Cullen/Woodall LLR Silver: Earned 100,000 credits (112,799)PPS LLR Sapphire: Earned 20,000,000 credits (21,743,450)PSP LLR Gold: Earned 500,000 credits (598,093)SoB LLR Gold: Earned 500,000 credits (575,934)SR5 LLR Silver: Earned 100,000 credits (210,142)SGS LLR Silver: Earned 100,000 credits (142,930)TRP LLR Silver: Earned 100,000 credits (476,246)Woodall LLR Silver: Earned 100,000 credits (281,400)321 Sieve (suspended) Silver: Earned 100,000 credits (175,037)Cullen/Woodall Sieve Bronze: Earned 10,000 credits (22,952)PPS Sieve Bronze: Earned 10,000 credits (10,113)AP 26/27 Bronze: Earned 10,000 credits (52,559)GFN Ruby: Earned 2,000,000 credits (4,988,252)WW (retired) Jade: Earned 10,000,000 credits (13,756,000)PSA Turquoise: Earned 5,000,000 credits (7,614,290)
Message 116287 - Posted: 21 Mar 2018 | 21:59:46 UTC - in response to Message 116253.

(B^2)^2^22 = (B)^2^23


You are right, this formula which can also be written GF(n, B^2) = GF(n+1, B) is certainly something to be aware of.

First of all, the most natural way to write a number (when communicating it) is with the highest possible exponent and a base B which is not a perfect square. If you see a GFN whose base is a square, rewrite it with this formula GF(n, B^2) = GF(n+1, B) until you reach a base which is not a perfect square.

You are right, this is old news. But maybe not always done optimally anyway? (A while ago I noticed problems with it, but I guess it is better now.)

So for example when doing GFN19, we should skip perfect square bases because this will have been tested a long time ago under the GFN20 project. This is true even if it would often be faster to check the "unnatural" form GF(19, B^2) than the more natural for GF(20, B) ...

But when doing GFN22, which is currently the highest exponent we have, I think we should include perfect square bases. If we do, when we open GFN23 one day, we can start from the square root of the base we have reached at that time in GFN22.

/JeppeSN

Gabriel LignelliProject donor
Avatar
Send message
Joined: 1 Sep 13
Posts: 61
ID: 251415
Credit: 10,423,448
RAC: 0
Found 1 prime in the 2018 Tour de Primes321 LLR Bronze: Earned 10,000 credits (53,871)Cullen LLR Bronze: Earned 10,000 credits (15,017)ESP LLR Bronze: Earned 10,000 credits (62,595)Generalized Cullen/Woodall LLR Bronze: Earned 10,000 credits (21,984)PPS LLR Silver: Earned 100,000 credits (136,702)PSP LLR Bronze: Earned 10,000 credits (47,301)SoB LLR Silver: Earned 100,000 credits (305,770)SR5 LLR Bronze: Earned 10,000 credits (18,306)SGS LLR Bronze: Earned 10,000 credits (14,608)TRP LLR Silver: Earned 100,000 credits (282,537)Woodall LLR Bronze: Earned 10,000 credits (33,562)321 Sieve (suspended) Gold: Earned 500,000 credits (865,427)Generalized Cullen/Woodall Sieve (suspended) Ruby: Earned 2,000,000 credits (2,397,311)PPS Sieve Ruby: Earned 2,000,000 credits (2,349,587)AP 26/27 Amethyst: Earned 1,000,000 credits (1,475,695)GFN Ruby: Earned 2,000,000 credits (2,056,798)PSA Silver: Earned 100,000 credits (286,377)
Message 117788 - Posted: 6 May 2018 | 21:33:28 UTC

I have been thinking about this while doing some testing with Genefer and I found that there does not seem to be a clear rule as to what form is faster to test. For some candidates, Genefer will even be able to use faster transforms, depending on what form of the number you use. As a result, the different transforms and number logic that goes on behind the scenes can make a lot of difference in testing times.
For example, Genefer was only able to test the number 256^16777216+1 using the OCL and OCL3 transforms, while for the number 65536^8388608+1 Genefer could use OCL, OCL2, OCL3, OCL4, and OCL5. The thing is that that is the same number, only written in two different ways. The latter showed about a third of the estimated completion time of the former. Similar behaviour can be observed with the CPU program as well.

I don't know whether these transform limitations are due to the way Genefer was programmed (pointing to a possible bug) or due to the nature of the transforms themselves. Either way, I would suggest adding some more benchmarking logic to Genefer to test perfect square roots.
For example, say you want to test the number 16^(2^18)+1. This new logic would make Genefer benchmark this number together with 4^(2^19)+1 and 2^(2^20)+1. What's more, it could also benchmark against 256^(2^17)+1 and 65536^(2^16)+1, since all these are the same number. Benchmarking all these different forms against the different transforms might show reductions in testing time.
____________

Profile Michael GoetzProject donor
Volunteer moderator
Project administrator
Avatar
Send message
Joined: 21 Jan 10
Posts: 14037
ID: 53948
Credit: 476,288,249
RAC: 227,716
The "Shut up already!" badge:  This loud mouth has mansplained on the forums over 10 thousand times!  Sheesh!!!Discovered the World's First GFN-19 prime!!!Discovered 2 mega primesFound 1 prime in the 2018 Tour de PrimesFound 1 prime in the 2019 Tour de PrimesFound 1 prime in the 2020 Tour de PrimesFound 2 primes in the 2021 Tour de PrimesFound 2 primes in the 2022 Tour de PrimesFound 1 mega prime in the 2022 Tour de PrimesFound 1 prime in the 2022 Tour de Primes Mountain StageFound 1 prime in the 2023 Tour de Primes321 LLR Turquoise: Earned 5,000,000 credits (6,949,793)Cullen LLR Turquoise: Earned 5,000,000 credits (5,513,946)ESP LLR Turquoise: Earned 5,000,000 credits (7,150,009)Generalized Cullen/Woodall LLR Turquoise: Earned 5,000,000 credits (5,094,541)PPS LLR Sapphire: Earned 20,000,000 credits (24,049,916)PSP LLR Jade: Earned 10,000,000 credits (11,203,327)SoB LLR Sapphire: Earned 20,000,000 credits (36,601,737)SR5 LLR Sapphire: Earned 20,000,000 credits (22,821,256)SGS LLR Turquoise: Earned 5,000,000 credits (6,369,306)TRP LLR Turquoise: Earned 5,000,000 credits (6,308,522)Woodall LLR Turquoise: Earned 5,000,000 credits (6,390,624)321 Sieve (suspended) Jade: Earned 10,000,000 credits (10,061,196)Cullen/Woodall Sieve Emerald: Earned 50,000,000 credits (51,764,198)Generalized Cullen/Woodall Sieve (suspended) Turquoise: Earned 5,000,000 credits (5,059,304)PPS Sieve Sapphire: Earned 20,000,000 credits (22,888,492)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Amethyst: Earned 1,000,000 credits (1,035,522)TRP Sieve (suspended) Ruby: Earned 2,000,000 credits (2,051,121)AP 26/27 Sapphire: Earned 20,000,000 credits (22,607,130)GFN Double Bronze: Earned 100,000,000 credits (120,616,519)WW (retired) Emerald: Earned 50,000,000 credits (88,580,000)PSA Jade: Earned 10,000,000 credits (13,196,884)
Message 117789 - Posted: 6 May 2018 | 22:39:43 UTC

Further comments about Genefer performance will be hidden -- they're off topic here in "Sieving". Please take this discussion to the appropriate forum.
____________
My lucky number is 75898524288+1

Message boards : Sieving : Combining GFN sieves with different n

[Return to PrimeGrid main page]
DNS Powered by DNSEXIT.COM
Copyright © 2005 - 2023 Rytis Slatkevičius (contact) and PrimeGrid community. Server load 2.27, 2.26, 2.45
Generated 22 Sep 2023 | 22:35:26 UTC