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

Join PrimeGrid

Returning Participants

Community

Leader Boards

Results

Other

drummers-lowrise

Advanced search

Message boards : Generalized Cullen/Woodall prime search : How to speed up (some) GCW units by 10%+

Author Message
Profile serge
Avatar
Send message
Joined: 21 Jun 12
Posts: 108
ID: 144858
Credit: 190,226,617
RAC: 31,853
321 LLR Turquoise: Earned 5,000,000 credits (5,342,838)Cullen LLR Silver: Earned 100,000 credits (158,983)ESP LLR Gold: Earned 500,000 credits (505,527)Generalized Cullen/Woodall LLR Ruby: Earned 2,000,000 credits (2,264,032)PPS LLR Sapphire: Earned 20,000,000 credits (23,395,331)PSP LLR Silver: Earned 100,000 credits (120,541)SoB LLR Amethyst: Earned 1,000,000 credits (1,280,028)SR5 LLR Ruby: Earned 2,000,000 credits (2,649,390)SGS LLR Gold: Earned 500,000 credits (518,356)TRP LLR Silver: Earned 100,000 credits (141,131)Woodall LLR Silver: Earned 100,000 credits (116,405)Cullen/Woodall Sieve (suspended) Silver: Earned 100,000 credits (235,088)PPS Sieve Amethyst: Earned 1,000,000 credits (1,014,671)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Gold: Earned 500,000 credits (500,445)TRP Sieve (suspended) Gold: Earned 500,000 credits (507,938)GFN Double Bronze: Earned 100,000,000 credits (151,184,962)PSA Silver: Earned 100,000 credits (291,533)
Message 107873 - Posted: 13 May 2017 | 2:09:26 UTC

Nothing of what I am about to write is new. Or difficult.
And it has already been discussed multiple times.

Observe that some the chosen bases for this particular sub-project happen to be squares.
25 = 5^2, 49 = 7^2, 121 = 11^2. Some people even know that this was a deliberate choice. I've been waiting for a workunit to arrive for one of these bases for a while, and now I have one.

The candidate is 754806*121^754806+1 which can also be easily regrouped as 754806*11^1509612+1.

Let's compare:

/home/serge/NumTheory/GCW> llr -d d.npg
Base prime factor(s) taken : 11
Starting N-1 prime test of 754806*121^754806+1
Using zero-padded AVX FFT length 720K, Pass1=320, Pass2=2304, a = 3
754806*121^754806+1, bit: 70000 / 5222413 [1.34%]. Time per bit: 5.654 ms.

/home/serge/NumTheory/GCW/2> llr -d d2.npg
Base prime factor(s) taken : 11
Starting N-1 prime test of 754806*11^1509612+1
Using zero-padded AVX FFT length 640K, Pass1=640, Pass2=1K, a = 3
754806*11^1509612+1, bit: 40000 / 5222416 [0.76%]. Time per bit: 4.698 ms.

That's 20% faster. (Results are similar for AVX2.)

Why is the server sending this workunit task as 754806*121^754806+1 ?
Isn't it trivial, server-side, to fetch the candidate from the database and if/when b=x^2, send it to the client not as
100000000000000:P:1:b:1
n n

but as
100000000000000:P:1:x:1
n 2n

In this particular case:
100000000000000:P:1:11:1
754806 1509612

Too hard to implement?

Michael GoetzProject donor
Volunteer moderator
Project scientist
Avatar
Send message
Joined: 21 Jan 10
Posts: 9371
ID: 53948
Credit: 101,708,147
RAC: 23,054
321 LLR Amethyst: Earned 1,000,000 credits (1,169,719)Cullen LLR Amethyst: Earned 1,000,000 credits (1,157,331)ESP LLR Amethyst: Earned 1,000,000 credits (1,179,211)Generalized Cullen/Woodall LLR Amethyst: Earned 1,000,000 credits (1,330,821)PPS LLR Amethyst: Earned 1,000,000 credits (1,253,816)PSP LLR Ruby: Earned 2,000,000 credits (2,632,269)SoB LLR Ruby: Earned 2,000,000 credits (2,067,903)SR5 LLR Turquoise: Earned 5,000,000 credits (6,035,738)SGS LLR Amethyst: Earned 1,000,000 credits (1,680,461)TRP LLR Amethyst: Earned 1,000,000 credits (1,009,313)Woodall LLR Amethyst: Earned 1,000,000 credits (1,145,077)321 Sieve (suspended) Silver: Earned 100,000 credits (200,576)Cullen/Woodall Sieve (suspended) Ruby: Earned 2,000,000 credits (4,170,256)Generalized Cullen/Woodall Sieve Ruby: Earned 2,000,000 credits (2,085,723)PPS Sieve Jade: Earned 10,000,000 credits (18,162,350)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 Turquoise: Earned 5,000,000 credits (5,877,196)GFN Sapphire: Earned 20,000,000 credits (38,036,953)PSA Turquoise: Earned 5,000,000 credits (9,426,791)
Message 107874 - Posted: 13 May 2017 | 2:28:00 UTC

Thanks, Serge.

Do you know why LLR chooses different FFT sizes for the same number? I was not aware it would do that.
____________
My lucky number is 75898^524288+1
Please do not PM me with support questions. They will usually go unanswered. Ask on the forums instead. Thank you!

Profile serge
Avatar
Send message
Joined: 21 Jun 12
Posts: 108
ID: 144858
Credit: 190,226,617
RAC: 31,853
321 LLR Turquoise: Earned 5,000,000 credits (5,342,838)Cullen LLR Silver: Earned 100,000 credits (158,983)ESP LLR Gold: Earned 500,000 credits (505,527)Generalized Cullen/Woodall LLR Ruby: Earned 2,000,000 credits (2,264,032)PPS LLR Sapphire: Earned 20,000,000 credits (23,395,331)PSP LLR Silver: Earned 100,000 credits (120,541)SoB LLR Amethyst: Earned 1,000,000 credits (1,280,028)SR5 LLR Ruby: Earned 2,000,000 credits (2,649,390)SGS LLR Gold: Earned 500,000 credits (518,356)TRP LLR Silver: Earned 100,000 credits (141,131)Woodall LLR Silver: Earned 100,000 credits (116,405)Cullen/Woodall Sieve (suspended) Silver: Earned 100,000 credits (235,088)PPS Sieve Amethyst: Earned 1,000,000 credits (1,014,671)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Gold: Earned 500,000 credits (500,445)TRP Sieve (suspended) Gold: Earned 500,000 credits (507,938)GFN Double Bronze: Earned 100,000,000 credits (151,184,962)PSA Silver: Earned 100,000 credits (291,533)
Message 107876 - Posted: 13 May 2017 | 4:32:55 UTC - in response to Message 107874.

For LLR it is not the number that matters, but the (k,b,n,c) form, and b is taken by it verbatim, as given.

I am not ready to go into a very deep explanation, but I will try to make an approximation to an explanation (not meant to be taken for that this is exact). With b=11, it is possible to form an array of length 640K where each element is a quasi-digit ("limb") in an unusual representation: some digit's weights are perhaps 11^6 and some digit's weights are 11^7, or something like that. (Off the top of my head, what I remember is that each limb on average is limited to keeping ~30 bits of information, or something like that.) Only powers of b can be used as limb weights.

In contrast if the number is entered with b=121, the program can only work with limbs of, say, 121^3 and 121^2. (It has less opportunities to pack, the larger the b.) For that reason it ponders the array of length 640K and thinks, "nah, some elements will be too large; gotta go for next FFT size", and so it does.

Long story short, using the simplest possible (k,b,n,c) (with b as low as possible) will lend more possibilities for more dense FFT arrays. If not only b=121, but also k is divisible by 11, the FFT size may be even smaller if (k,121,n,c) is transformed into (k/11,11,2*n+1,c).

As an aside, yes, it would be nice if LLR did it all itself, but as the timing test (shown earlier) demonstrates - it doesn't. But here's where we can help LLR and do transformation externally, server-side. The transformation logic is quite straightforward.[/i]

Michael GoetzProject donor
Volunteer moderator
Project scientist
Avatar
Send message
Joined: 21 Jan 10
Posts: 9371
ID: 53948
Credit: 101,708,147
RAC: 23,054
321 LLR Amethyst: Earned 1,000,000 credits (1,169,719)Cullen LLR Amethyst: Earned 1,000,000 credits (1,157,331)ESP LLR Amethyst: Earned 1,000,000 credits (1,179,211)Generalized Cullen/Woodall LLR Amethyst: Earned 1,000,000 credits (1,330,821)PPS LLR Amethyst: Earned 1,000,000 credits (1,253,816)PSP LLR Ruby: Earned 2,000,000 credits (2,632,269)SoB LLR Ruby: Earned 2,000,000 credits (2,067,903)SR5 LLR Turquoise: Earned 5,000,000 credits (6,035,738)SGS LLR Amethyst: Earned 1,000,000 credits (1,680,461)TRP LLR Amethyst: Earned 1,000,000 credits (1,009,313)Woodall LLR Amethyst: Earned 1,000,000 credits (1,145,077)321 Sieve (suspended) Silver: Earned 100,000 credits (200,576)Cullen/Woodall Sieve (suspended) Ruby: Earned 2,000,000 credits (4,170,256)Generalized Cullen/Woodall Sieve Ruby: Earned 2,000,000 credits (2,085,723)PPS Sieve Jade: Earned 10,000,000 credits (18,162,350)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 Turquoise: Earned 5,000,000 credits (5,877,196)GFN Sapphire: Earned 20,000,000 credits (38,036,953)PSA Turquoise: Earned 5,000,000 credits (9,426,791)
Message 107877 - Posted: 13 May 2017 | 4:53:35 UTC - in response to Message 107876.

Got it, thanks for the explanation. That makes sense.
____________
My lucky number is 75898^524288+1
Please do not PM me with support questions. They will usually go unanswered. Ask on the forums instead. Thank you!

mackerelProject donor
Volunteer tester
Avatar
Send message
Joined: 2 Oct 08
Posts: 1633
ID: 29980
Credit: 185,073,352
RAC: 82,479
321 LLR Ruby: Earned 2,000,000 credits (4,421,795)Cullen LLR Ruby: Earned 2,000,000 credits (4,619,611)ESP LLR Ruby: Earned 2,000,000 credits (3,725,865)Generalized Cullen/Woodall LLR Ruby: Earned 2,000,000 credits (3,220,326)PPS LLR Sapphire: Earned 20,000,000 credits (24,870,545)PSP LLR Jade: Earned 10,000,000 credits (10,128,604)SoB LLR Ruby: Earned 2,000,000 credits (2,643,659)SR5 LLR Jade: Earned 10,000,000 credits (12,262,110)SGS LLR Turquoise: Earned 5,000,000 credits (6,702,766)TPS LLR (retired) Bronze: Earned 10,000 credits (34,130)TRP LLR Turquoise: Earned 5,000,000 credits (5,143,430)Woodall LLR Ruby: Earned 2,000,000 credits (2,471,793)321 Sieve (suspended) Silver: Earned 100,000 credits (203,937)Cullen/Woodall Sieve (suspended) Turquoise: Earned 5,000,000 credits (5,383,853)Generalized Cullen/Woodall Sieve Sapphire: Earned 20,000,000 credits (20,070,475)PPS Sieve Sapphire: Earned 20,000,000 credits (39,662,287)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Ruby: Earned 2,000,000 credits (2,293,882)TRP Sieve (suspended) Turquoise: Earned 5,000,000 credits (5,012,757)AP 26/27 Jade: Earned 10,000,000 credits (12,231,866)GFN Jade: Earned 10,000,000 credits (17,029,965)PSA Ruby: Earned 2,000,000 credits (2,939,755)
Message 107879 - Posted: 13 May 2017 | 7:50:09 UTC

Maybe propose this optimisation as a feature request to go in future LLR if not already done?

JeppeSNProject donor
Send message
Joined: 5 Apr 14
Posts: 554
ID: 306875
Credit: 7,572,820
RAC: 10,625
PSA Turquoise: Earned 5,000,000 credits (7,572,820)
Message 107882 - Posted: 13 May 2017 | 9:00:33 UTC - in response to Message 107873.
Last modified: 13 May 2017 | 9:17:59 UTC

Observe that some the chosen bases for this particular sub-project happen to be squares.
25 = 5^2, 49 = 7^2, 121 = 11^2. Some people even know that this was a deliberate choice.


25, 49, 121; that is all the prime squares in the range 13 ≤ b ≤ 121. I wonder if there is some easy reason why n*b^n + 1 is more often composite when b is a perfect square. Does sieving remove a larger fraction, so that the expected occurrence of primes is lower for these b values?

"Deliberate choice"? I though these b values were chosen simply because they were the smallest b for which no known n with n>b-2 gives a prime n*b^n + 1?

/JeppeSN

Addition: I checked on Steven Harvey's page on GC, and for all prime square b among 121, 169, 289, 361, 529, 841, 961, 1369, 1681, 1849, 2209, 2809, 3481, 3721, 4489, 5041, 5329, 6241, 6889, 7921, 9409, the only time an n is known that satisfies n>b-2 is for b=5041 where:

8398*5041^8398 + 1 = 8398*71^16796 + 1

is a prime.

Michael GoetzProject donor
Volunteer moderator
Project scientist
Avatar
Send message
Joined: 21 Jan 10
Posts: 9371
ID: 53948
Credit: 101,708,147
RAC: 23,054
321 LLR Amethyst: Earned 1,000,000 credits (1,169,719)Cullen LLR Amethyst: Earned 1,000,000 credits (1,157,331)ESP LLR Amethyst: Earned 1,000,000 credits (1,179,211)Generalized Cullen/Woodall LLR Amethyst: Earned 1,000,000 credits (1,330,821)PPS LLR Amethyst: Earned 1,000,000 credits (1,253,816)PSP LLR Ruby: Earned 2,000,000 credits (2,632,269)SoB LLR Ruby: Earned 2,000,000 credits (2,067,903)SR5 LLR Turquoise: Earned 5,000,000 credits (6,035,738)SGS LLR Amethyst: Earned 1,000,000 credits (1,680,461)TRP LLR Amethyst: Earned 1,000,000 credits (1,009,313)Woodall LLR Amethyst: Earned 1,000,000 credits (1,145,077)321 Sieve (suspended) Silver: Earned 100,000 credits (200,576)Cullen/Woodall Sieve (suspended) Ruby: Earned 2,000,000 credits (4,170,256)Generalized Cullen/Woodall Sieve Ruby: Earned 2,000,000 credits (2,085,723)PPS Sieve Jade: Earned 10,000,000 credits (18,162,350)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 Turquoise: Earned 5,000,000 credits (5,877,196)GFN Sapphire: Earned 20,000,000 credits (38,036,953)PSA Turquoise: Earned 5,000,000 credits (9,426,791)
Message 107885 - Posted: 13 May 2017 | 12:29:07 UTC

Serge, thanks for the optimization tip. It's appreciated!

By the way, we (and by "we", I mean "Jim") have recomputed many of the FFT sizes for the candidates. You don't always get a reduced FFT size when you use the square root of b, but you do for the vast majority of candidates. For the other bases, dividing k by b one or more times hasn't reduced the FFT size once yet.
____________
My lucky number is 75898^524288+1
Please do not PM me with support questions. They will usually go unanswered. Ask on the forums instead. Thank you!

Profile serge
Avatar
Send message
Joined: 21 Jun 12
Posts: 108
ID: 144858
Credit: 190,226,617
RAC: 31,853
321 LLR Turquoise: Earned 5,000,000 credits (5,342,838)Cullen LLR Silver: Earned 100,000 credits (158,983)ESP LLR Gold: Earned 500,000 credits (505,527)Generalized Cullen/Woodall LLR Ruby: Earned 2,000,000 credits (2,264,032)PPS LLR Sapphire: Earned 20,000,000 credits (23,395,331)PSP LLR Silver: Earned 100,000 credits (120,541)SoB LLR Amethyst: Earned 1,000,000 credits (1,280,028)SR5 LLR Ruby: Earned 2,000,000 credits (2,649,390)SGS LLR Gold: Earned 500,000 credits (518,356)TRP LLR Silver: Earned 100,000 credits (141,131)Woodall LLR Silver: Earned 100,000 credits (116,405)Cullen/Woodall Sieve (suspended) Silver: Earned 100,000 credits (235,088)PPS Sieve Amethyst: Earned 1,000,000 credits (1,014,671)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Gold: Earned 500,000 credits (500,445)TRP Sieve (suspended) Gold: Earned 500,000 credits (507,938)GFN Double Bronze: Earned 100,000,000 credits (151,184,962)PSA Silver: Earned 100,000 credits (291,533)
Message 107890 - Posted: 13 May 2017 | 16:15:55 UTC - in response to Message 107885.
Last modified: 13 May 2017 | 16:17:02 UTC

It seems that in your client-server set up the ideal place to put the reformatter would be the primegrid_llr_wrapper. It would keep the initial task parameters, reformat for (c)llr, get the result back from (c)llr, report back to server as initially requested. Then the database, the server and the accounting code would be unchanged.

primegrid_llr_wrapper for now can do only:
▪ square simplification,
▪ k simplification

Later, it can be extended to recognize b being any power. See here -

Curiously, these numbers may be hard to recognize when written in standard form (emphasis mine).

For example, they may be like
18740*3^168662-1
which could be written
168660*3^168660-1.

More difficult to spot are those like the following:

9750*7^29250-1 = 9750*7^(3*9750)-1 = 9750*343^9750-1
8511*2^374486-1 = (8511*2^2)*2^(11*8511)*4-1 = 34044*2048^34044-1.


This is in fact how the GCWs for 25, 49, 121 will end up showing in UTM lists. (And this is how GW for b=4 looks, indeed.)

Michael GoetzProject donor
Volunteer moderator
Project scientist
Avatar
Send message
Joined: 21 Jan 10
Posts: 9371
ID: 53948
Credit: 101,708,147
RAC: 23,054
321 LLR Amethyst: Earned 1,000,000 credits (1,169,719)Cullen LLR Amethyst: Earned 1,000,000 credits (1,157,331)ESP LLR Amethyst: Earned 1,000,000 credits (1,179,211)Generalized Cullen/Woodall LLR Amethyst: Earned 1,000,000 credits (1,330,821)PPS LLR Amethyst: Earned 1,000,000 credits (1,253,816)PSP LLR Ruby: Earned 2,000,000 credits (2,632,269)SoB LLR Ruby: Earned 2,000,000 credits (2,067,903)SR5 LLR Turquoise: Earned 5,000,000 credits (6,035,738)SGS LLR Amethyst: Earned 1,000,000 credits (1,680,461)TRP LLR Amethyst: Earned 1,000,000 credits (1,009,313)Woodall LLR Amethyst: Earned 1,000,000 credits (1,145,077)321 Sieve (suspended) Silver: Earned 100,000 credits (200,576)Cullen/Woodall Sieve (suspended) Ruby: Earned 2,000,000 credits (4,170,256)Generalized Cullen/Woodall Sieve Ruby: Earned 2,000,000 credits (2,085,723)PPS Sieve Jade: Earned 10,000,000 credits (18,162,350)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 Turquoise: Earned 5,000,000 credits (5,877,196)GFN Sapphire: Earned 20,000,000 credits (38,036,953)PSA Turquoise: Earned 5,000,000 credits (9,426,791)
Message 107891 - Posted: 13 May 2017 | 17:06:52 UTC - in response to Message 107890.

It seems that in your client-server set up the ideal place to put the reformatter would be the primegrid_llr_wrapper.


That's not the prefered place for the change, but we're still evaluating options.
____________
My lucky number is 75898^524288+1
Please do not PM me with support questions. They will usually go unanswered. Ask on the forums instead. Thank you!

axn
Volunteer developer
Send message
Joined: 29 Dec 07
Posts: 244
ID: 16874
Credit: 8,653,382
RAC: 0
321 LLR Silver: Earned 100,000 credits (115,840)Cullen LLR Silver: Earned 100,000 credits (175,895)ESP LLR Silver: Earned 100,000 credits (330,310)PPS LLR Gold: Earned 500,000 credits (748,824)SoB LLR Silver: Earned 100,000 credits (176,825)SR5 LLR Ruby: Earned 2,000,000 credits (2,010,622)SGS LLR Silver: Earned 100,000 credits (101,658)Cullen/Woodall Sieve (suspended) Bronze: Earned 10,000 credits (32,498)PPS Sieve Ruby: Earned 2,000,000 credits (2,479,572)GFN Ruby: Earned 2,000,000 credits (2,380,031)PSA Silver: Earned 100,000 credits (101,309)
Message 107907 - Posted: 14 May 2017 | 16:11:42 UTC

I could've sworn that LLR itself does the normalizing of the bases (perhaps only for power of 2?). This feature needs to be in LLR itself, tbh.

1. Normalize b if it is a power.
2. Normalize k if b divides k.

I would guess that it is a trivial change in LLR (except for printing output -- where it is arguably important to use the unnormalized values).

Profile serge
Avatar
Send message
Joined: 21 Jun 12
Posts: 108
ID: 144858
Credit: 190,226,617
RAC: 31,853
321 LLR Turquoise: Earned 5,000,000 credits (5,342,838)Cullen LLR Silver: Earned 100,000 credits (158,983)ESP LLR Gold: Earned 500,000 credits (505,527)Generalized Cullen/Woodall LLR Ruby: Earned 2,000,000 credits (2,264,032)PPS LLR Sapphire: Earned 20,000,000 credits (23,395,331)PSP LLR Silver: Earned 100,000 credits (120,541)SoB LLR Amethyst: Earned 1,000,000 credits (1,280,028)SR5 LLR Ruby: Earned 2,000,000 credits (2,649,390)SGS LLR Gold: Earned 500,000 credits (518,356)TRP LLR Silver: Earned 100,000 credits (141,131)Woodall LLR Silver: Earned 100,000 credits (116,405)Cullen/Woodall Sieve (suspended) Silver: Earned 100,000 credits (235,088)PPS Sieve Amethyst: Earned 1,000,000 credits (1,014,671)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Gold: Earned 500,000 credits (500,445)TRP Sieve (suspended) Gold: Earned 500,000 credits (507,938)GFN Double Bronze: Earned 100,000,000 credits (151,184,962)PSA Silver: Earned 100,000 credits (291,533)
Message 107909 - Posted: 14 May 2017 | 17:11:18 UTC - in response to Message 107907.

Maybe LLR's philosophy is "the client is always right!"
I.e.: If the input file calls for a test of a specific FFT or a "specific arrangement of bits", then that's what it will run (even if slower, because "this is the test that was ordered").

But it indeed doesn't follow this rule for powers of 2.

-bash-4.2$ llr -d -q"27*1024^10007+1"
Starting Proth prime test of 27*2^100070+1
Using all-complex FMA3 FFT length 10K, Pass1=128, Pass2=80, a = 11
27*2^100070+1 is not prime. Proth RES64: C14E6737D2E78E5E Time : 5.261 sec.

-bash-4.2$ llr -d -q"28*729^10007+1"
Base prime factor(s) taken : 3
Starting N-1 prime test of 28*729^10007+1
Using all-complex FMA3 FFT length 10K, Pass1=128, Pass2=80, a = 3
28*729^10007+1 is not prime. RES64: E83080E955E9B281. OLD64: B89182BC01BD1780 Time : 4.888 sec.

-bash-4.2$ llr -d -q"28*10000^10007+1"
Base factorized as : 2^4*5^4
Base prime factor(s) taken : 5
Starting N-1 prime test of 28*10000^10007+1
Using all-complex FMA3 FFT length 18K, Pass1=384, Pass2=48, a = 3
28*10000^10007+1 is not prime. RES64: 59CCA66A39ED54C4. OLD64: 0D65F33EADC7FE48 Time : 13.645 sec.

(and of course it is fully equipped to normalize the base, as a side effect of factoring the base for the purposes of the N-1 mechanics.)

PFGW does what it is ordered by the input file, too.

JeppeSNProject donor
Send message
Joined: 5 Apr 14
Posts: 554
ID: 306875
Credit: 7,572,820
RAC: 10,625
PSA Turquoise: Earned 5,000,000 credits (7,572,820)
Message 107910 - Posted: 14 May 2017 | 17:53:52 UTC - in response to Message 107909.

And GeneFer seems to do different things, not normalizing or de-normalizing:

.\genefer_windows64.exe -q "6^8388608+1"
.\genefer_windows64.exe -q "36^4194304+1"
.\genefer_windows64.exe -q "1296^2097152+1"
.\genefer_windows64.exe -q "1679616^1048576+1"

Even though the first form (where b=6 is not a square) is "canonical" and the one you would expect to see on Top 5000, it is not clear which form would actually be fastest.

Testing 6^8388608+1... 21684224 steps to go (1849:28:44 remaining)

Testing 36^4194304+1... 21684224 steps to go (747:08:06 remaining)

Testing 1296^2097152+1... 21684224 steps to go (367:41:08 remaining)

Testing 1679616^1048576+1... 21684224 steps to go (160:41:45 remaining)
Estimated time remaining for 1679616^1048576+1 is 1716:50:53

(the last one is switches to x87 (80-bit) transform).

/JeppeSN

Michael GoetzProject donor
Volunteer moderator
Project scientist
Avatar
Send message
Joined: 21 Jan 10
Posts: 9371
ID: 53948
Credit: 101,708,147
RAC: 23,054
321 LLR Amethyst: Earned 1,000,000 credits (1,169,719)Cullen LLR Amethyst: Earned 1,000,000 credits (1,157,331)ESP LLR Amethyst: Earned 1,000,000 credits (1,179,211)Generalized Cullen/Woodall LLR Amethyst: Earned 1,000,000 credits (1,330,821)PPS LLR Amethyst: Earned 1,000,000 credits (1,253,816)PSP LLR Ruby: Earned 2,000,000 credits (2,632,269)SoB LLR Ruby: Earned 2,000,000 credits (2,067,903)SR5 LLR Turquoise: Earned 5,000,000 credits (6,035,738)SGS LLR Amethyst: Earned 1,000,000 credits (1,680,461)TRP LLR Amethyst: Earned 1,000,000 credits (1,009,313)Woodall LLR Amethyst: Earned 1,000,000 credits (1,145,077)321 Sieve (suspended) Silver: Earned 100,000 credits (200,576)Cullen/Woodall Sieve (suspended) Ruby: Earned 2,000,000 credits (4,170,256)Generalized Cullen/Woodall Sieve Ruby: Earned 2,000,000 credits (2,085,723)PPS Sieve Jade: Earned 10,000,000 credits (18,162,350)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 Turquoise: Earned 5,000,000 credits (5,877,196)GFN Sapphire: Earned 20,000,000 credits (38,036,953)PSA Turquoise: Earned 5,000,000 credits (9,426,791)
Message 107912 - Posted: 14 May 2017 | 19:20:37 UTC

Genefer and LLR/PFGW are completely different. Genefer doesn't normalize anything (although I suppose it could.)

With regards to LLR doing some normalizations but not others, does anyone know if that's LLR's code or gwnum's code?
____________
My lucky number is 75898^524288+1
Please do not PM me with support questions. They will usually go unanswered. Ask on the forums instead. Thank you!

Profile composite
Send message
Joined: 16 Feb 10
Posts: 314
ID: 55391
Credit: 338,444,542
RAC: 259,167
321 LLR Ruby: Earned 2,000,000 credits (3,454,678)Cullen LLR Gold: Earned 500,000 credits (676,922)ESP LLR Amethyst: Earned 1,000,000 credits (1,021,827)Generalized Cullen/Woodall LLR Amethyst: Earned 1,000,000 credits (1,715,268)PPS LLR Ruby: Earned 2,000,000 credits (3,311,588)PSP LLR Ruby: Earned 2,000,000 credits (3,138,070)SoB LLR Ruby: Earned 2,000,000 credits (3,225,373)SR5 LLR Turquoise: Earned 5,000,000 credits (5,071,131)SGS LLR Ruby: Earned 2,000,000 credits (2,860,720)TRP LLR Amethyst: Earned 1,000,000 credits (1,006,014)Woodall LLR Amethyst: Earned 1,000,000 credits (1,291,833)321 Sieve (suspended) Amethyst: Earned 1,000,000 credits (1,228,005)Cullen/Woodall Sieve (suspended) Turquoise: Earned 5,000,000 credits (5,571,178)Generalized Cullen/Woodall Sieve Ruby: Earned 2,000,000 credits (2,206,963)PPS Sieve Double Bronze: Earned 100,000,000 credits (141,097,197)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Jade: Earned 10,000,000 credits (10,165,888)TRP Sieve (suspended) Sapphire: Earned 20,000,000 credits (20,071,454)AP 26/27 Ruby: Earned 2,000,000 credits (2,439,709)GFN Sapphire: Earned 20,000,000 credits (26,149,758)PSA Double Bronze: Earned 100,000,000 credits (102,758,261)
Message 107936 - Posted: 16 May 2017 | 5:09:50 UTC

If you let LLR do the normalization, it will be impossible to rerun serge's benchmark comparison. But once is enough to prove a point.

KEPProject donor
Send message
Joined: 10 Aug 05
Posts: 231
ID: 110
Credit: 1,864,604
RAC: 5
PSP LLR Silver: Earned 100,000 credits (273,295)SoB LLR Gold: Earned 500,000 credits (594,405)SR5 LLR Bronze: Earned 10,000 credits (59,335)TRP LLR Silver: Earned 100,000 credits (130,589)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Bronze: Earned 10,000 credits (64,186)TRP Sieve (suspended) Silver: Earned 100,000 credits (259,649)PSA Silver: Earned 100,000 credits (456,059)
Message 107998 - Posted: 18 May 2017 | 15:39:39 UTC - in response to Message 107907.

I could've sworn that LLR itself does the normalizing of the bases (perhaps only for power of 2?). This feature needs to be in LLR itself, tbh.


This appears also not to be the case. Currently, I've seen reduction in overall testing times, ranging from 9% to 33%, dependant on FFT length and weather I'm on my Sandy Bridge or Haswell. So it appears, that LLR is also not doing a normalizing for bases that are powers of 2, but in fact still tests k*16^n+/-1 as base 16 number and not k*2^(n*4)+/-1 - even though the screen shows that k*2^(n*4)+/-1 is being tested.

To sum up, at least on my system, there can be up to 33% reduction of testing time per k*b^n+/-1 test, by normalizing the test, if it is a power of a base, to smallest possible base.

Just my 2 cents, take care :)

Regards

KEP

Michael GoetzProject donor
Volunteer moderator
Project scientist
Avatar
Send message
Joined: 21 Jan 10
Posts: 9371
ID: 53948
Credit: 101,708,147
RAC: 23,054
321 LLR Amethyst: Earned 1,000,000 credits (1,169,719)Cullen LLR Amethyst: Earned 1,000,000 credits (1,157,331)ESP LLR Amethyst: Earned 1,000,000 credits (1,179,211)Generalized Cullen/Woodall LLR Amethyst: Earned 1,000,000 credits (1,330,821)PPS LLR Amethyst: Earned 1,000,000 credits (1,253,816)PSP LLR Ruby: Earned 2,000,000 credits (2,632,269)SoB LLR Ruby: Earned 2,000,000 credits (2,067,903)SR5 LLR Turquoise: Earned 5,000,000 credits (6,035,738)SGS LLR Amethyst: Earned 1,000,000 credits (1,680,461)TRP LLR Amethyst: Earned 1,000,000 credits (1,009,313)Woodall LLR Amethyst: Earned 1,000,000 credits (1,145,077)321 Sieve (suspended) Silver: Earned 100,000 credits (200,576)Cullen/Woodall Sieve (suspended) Ruby: Earned 2,000,000 credits (4,170,256)Generalized Cullen/Woodall Sieve Ruby: Earned 2,000,000 credits (2,085,723)PPS Sieve Jade: Earned 10,000,000 credits (18,162,350)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 Turquoise: Earned 5,000,000 credits (5,877,196)GFN Sapphire: Earned 20,000,000 credits (38,036,953)PSA Turquoise: Earned 5,000,000 credits (9,426,791)
Message 109348 - Posted: 14 Aug 2017 | 13:29:21 UTC - in response to Message 107873.

The candidate is 754806*121^754806+1 which can also be easily regrouped as 754806*11^1509612+1.

Let's compare:
/home/serge/NumTheory/GCW> llr -d d.npg
Base prime factor(s) taken : 11
Starting N-1 prime test of 754806*121^754806+1
Using zero-padded AVX FFT length 720K, Pass1=320, Pass2=2304, a = 3
754806*121^754806+1, bit: 70000 / 5222413 [1.34%]. Time per bit: 5.654 ms.

/home/serge/NumTheory/GCW/2> llr -d d2.npg
Base prime factor(s) taken : 11
Starting N-1 prime test of 754806*11^1509612+1
Using zero-padded AVX FFT length 640K, Pass1=640, Pass2=1K, a = 3
754806*11^1509612+1, bit: 40000 / 5222416 [0.76%]. Time per bit: 4.698 ms.

That's 20% faster. (Results are similar for AVX2.)

Why is the server sending this workunit task as 754806*121^754806+1 ?
Isn't it trivial[?]


You would be surprised at how utterly non-trivial it turned out to be. But it is done. Thanks for pushing us along in the right direction.
____________
My lucky number is 75898^524288+1
Please do not PM me with support questions. They will usually go unanswered. Ask on the forums instead. Thank you!

HonzaProject donor
Volunteer moderator
Volunteer tester
Project scientist
Send message
Joined: 15 Aug 05
Posts: 1605
ID: 352
Credit: 1,756,123,988
RAC: 1,199,208
321 LLR Jade: Earned 10,000,000 credits (15,812,082)Cullen LLR Sapphire: Earned 20,000,000 credits (20,758,697)ESP LLR Sapphire: Earned 20,000,000 credits (20,183,757)Generalized Cullen/Woodall LLR Sapphire: Earned 20,000,000 credits (21,044,302)PPS LLR Emerald: Earned 50,000,000 credits (51,016,093)PSP LLR Sapphire: Earned 20,000,000 credits (23,462,639)SoB LLR Sapphire: Earned 20,000,000 credits (22,553,364)SR5 LLR Sapphire: Earned 20,000,000 credits (20,233,642)SGS LLR Sapphire: Earned 20,000,000 credits (20,037,618)TPS LLR (retired) Bronze: Earned 10,000 credits (43,033)TRP LLR Jade: Earned 10,000,000 credits (18,591,918)Woodall LLR Sapphire: Earned 20,000,000 credits (20,037,694)321 Sieve (suspended) Ruby: Earned 2,000,000 credits (4,024,795)Cullen/Woodall Sieve (suspended) Ruby: Earned 2,000,000 credits (4,142,109)Generalized Cullen/Woodall Sieve Sapphire: Earned 20,000,000 credits (20,357,260)PPS Sieve Double Silver: Earned 200,000,000 credits (376,970,310)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Sapphire: Earned 20,000,000 credits (20,288,222)TRP Sieve (suspended) Sapphire: Earned 20,000,000 credits (20,149,354)AP 26/27 Sapphire: Earned 20,000,000 credits (20,062,973)GFN Double Gold: Earned 500,000,000 credits (511,313,346)PSA Double Gold: Earned 500,000,000 credits (525,027,972)
Message 109353 - Posted: 14 Aug 2017 | 20:08:30 UTC

So, 3 of 14 bases will be 20% faster?
About 4% overall speed-up for GCW LLR?
____________
My stats
Badge score: 1*1 + 5*2 + 7*2 + 8*12 + 9*1 + 11*1 + 12*2 = 165

Michael GoetzProject donor
Volunteer moderator
Project scientist
Avatar
Send message
Joined: 21 Jan 10
Posts: 9371
ID: 53948
Credit: 101,708,147
RAC: 23,054
321 LLR Amethyst: Earned 1,000,000 credits (1,169,719)Cullen LLR Amethyst: Earned 1,000,000 credits (1,157,331)ESP LLR Amethyst: Earned 1,000,000 credits (1,179,211)Generalized Cullen/Woodall LLR Amethyst: Earned 1,000,000 credits (1,330,821)PPS LLR Amethyst: Earned 1,000,000 credits (1,253,816)PSP LLR Ruby: Earned 2,000,000 credits (2,632,269)SoB LLR Ruby: Earned 2,000,000 credits (2,067,903)SR5 LLR Turquoise: Earned 5,000,000 credits (6,035,738)SGS LLR Amethyst: Earned 1,000,000 credits (1,680,461)TRP LLR Amethyst: Earned 1,000,000 credits (1,009,313)Woodall LLR Amethyst: Earned 1,000,000 credits (1,145,077)321 Sieve (suspended) Silver: Earned 100,000 credits (200,576)Cullen/Woodall Sieve (suspended) Ruby: Earned 2,000,000 credits (4,170,256)Generalized Cullen/Woodall Sieve Ruby: Earned 2,000,000 credits (2,085,723)PPS Sieve Jade: Earned 10,000,000 credits (18,162,350)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 Turquoise: Earned 5,000,000 credits (5,877,196)GFN Sapphire: Earned 20,000,000 credits (38,036,953)PSA Turquoise: Earned 5,000,000 credits (9,426,791)
Message 109355 - Posted: 14 Aug 2017 | 20:52:19 UTC - in response to Message 109353.

So, 3 of 14 bases will be 20% faster?
About 4% overall speed-up for GCW LLR?


Something like that, yes.
____________
My lucky number is 75898^524288+1
Please do not PM me with support questions. They will usually go unanswered. Ask on the forums instead. Thank you!

axn
Volunteer developer
Send message
Joined: 29 Dec 07
Posts: 244
ID: 16874
Credit: 8,653,382
RAC: 0
321 LLR Silver: Earned 100,000 credits (115,840)Cullen LLR Silver: Earned 100,000 credits (175,895)ESP LLR Silver: Earned 100,000 credits (330,310)PPS LLR Gold: Earned 500,000 credits (748,824)SoB LLR Silver: Earned 100,000 credits (176,825)SR5 LLR Ruby: Earned 2,000,000 credits (2,010,622)SGS LLR Silver: Earned 100,000 credits (101,658)Cullen/Woodall Sieve (suspended) Bronze: Earned 10,000 credits (32,498)PPS Sieve Ruby: Earned 2,000,000 credits (2,479,572)GFN Ruby: Earned 2,000,000 credits (2,380,031)PSA Silver: Earned 100,000 credits (101,309)
Message 109381 - Posted: 16 Aug 2017 | 7:53:38 UTC - in response to Message 109348.
Last modified: 16 Aug 2017 | 7:59:40 UTC

You would be surprised at how utterly non-trivial it turned out to be. But it is done. Thanks for pushing us along in the right direction.

Is the base the only thing normalized or do you normalize k as well (the latter is applicable for all the bases, not just the square ones)?

Michael GoetzProject donor
Volunteer moderator
Project scientist
Avatar
Send message
Joined: 21 Jan 10
Posts: 9371
ID: 53948
Credit: 101,708,147
RAC: 23,054
321 LLR Amethyst: Earned 1,000,000 credits (1,169,719)Cullen LLR Amethyst: Earned 1,000,000 credits (1,157,331)ESP LLR Amethyst: Earned 1,000,000 credits (1,179,211)Generalized Cullen/Woodall LLR Amethyst: Earned 1,000,000 credits (1,330,821)PPS LLR Amethyst: Earned 1,000,000 credits (1,253,816)PSP LLR Ruby: Earned 2,000,000 credits (2,632,269)SoB LLR Ruby: Earned 2,000,000 credits (2,067,903)SR5 LLR Turquoise: Earned 5,000,000 credits (6,035,738)SGS LLR Amethyst: Earned 1,000,000 credits (1,680,461)TRP LLR Amethyst: Earned 1,000,000 credits (1,009,313)Woodall LLR Amethyst: Earned 1,000,000 credits (1,145,077)321 Sieve (suspended) Silver: Earned 100,000 credits (200,576)Cullen/Woodall Sieve (suspended) Ruby: Earned 2,000,000 credits (4,170,256)Generalized Cullen/Woodall Sieve Ruby: Earned 2,000,000 credits (2,085,723)PPS Sieve Jade: Earned 10,000,000 credits (18,162,350)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 Turquoise: Earned 5,000,000 credits (5,877,196)GFN Sapphire: Earned 20,000,000 credits (38,036,953)PSA Turquoise: Earned 5,000,000 credits (9,426,791)
Message 109382 - Posted: 16 Aug 2017 | 11:02:29 UTC - in response to Message 109381.

You would be surprised at how utterly non-trivial it turned out to be. But it is done. Thanks for pushing us along in the right direction.

Is the base the only thing normalized or do you normalize k as well (the latter is applicable for all the bases, not just the square ones)?


Just the base. In our tests there was no advantage to normalizing k.
____________
My lucky number is 75898^524288+1
Please do not PM me with support questions. They will usually go unanswered. Ask on the forums instead. Thank you!

axn
Volunteer developer
Send message
Joined: 29 Dec 07
Posts: 244
ID: 16874
Credit: 8,653,382
RAC: 0
321 LLR Silver: Earned 100,000 credits (115,840)Cullen LLR Silver: Earned 100,000 credits (175,895)ESP LLR Silver: Earned 100,000 credits (330,310)PPS LLR Gold: Earned 500,000 credits (748,824)SoB LLR Silver: Earned 100,000 credits (176,825)SR5 LLR Ruby: Earned 2,000,000 credits (2,010,622)SGS LLR Silver: Earned 100,000 credits (101,658)Cullen/Woodall Sieve (suspended) Bronze: Earned 10,000 credits (32,498)PPS Sieve Ruby: Earned 2,000,000 credits (2,479,572)GFN Ruby: Earned 2,000,000 credits (2,380,031)PSA Silver: Earned 100,000 credits (101,309)
Message 109387 - Posted: 16 Aug 2017 | 14:39:55 UTC - in response to Message 109382.

Just the base. In our tests there was no advantage to normalizing k.

Hmmm... That was ... unexpected! Can you give me the set of (n,b) numbers used to test this? I am assuming that you used LLR's setup feature to get the FFTs?

JimBProject donor
Volunteer moderator
Project developer
Project scientist
Send message
Joined: 4 Aug 11
Posts: 628
ID: 107307
Credit: 427,396,598
RAC: 1,871,867
321 LLR Ruby: Earned 2,000,000 credits (2,014,631)Cullen LLR Ruby: Earned 2,000,000 credits (2,041,185)ESP LLR Ruby: Earned 2,000,000 credits (2,060,837)Generalized Cullen/Woodall LLR Ruby: Earned 2,000,000 credits (2,006,814)PPS LLR Ruby: Earned 2,000,000 credits (2,052,020)PSP LLR Ruby: Earned 2,000,000 credits (3,262,777)SoB LLR Turquoise: Earned 5,000,000 credits (6,889,253)SR5 LLR Turquoise: Earned 5,000,000 credits (6,328,868)SGS LLR Ruby: Earned 2,000,000 credits (2,000,415)TRP LLR Ruby: Earned 2,000,000 credits (2,064,150)Woodall LLR Ruby: Earned 2,000,000 credits (2,009,056)Cullen/Woodall Sieve (suspended) Ruby: Earned 2,000,000 credits (4,002,919)Generalized Cullen/Woodall Sieve Turquoise: Earned 5,000,000 credits (5,885,049)PPS Sieve Sapphire: Earned 20,000,000 credits (22,870,331)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Ruby: Earned 2,000,000 credits (2,341,676)TRP Sieve (suspended) Ruby: Earned 2,000,000 credits (2,070,804)AP 26/27 Ruby: Earned 2,000,000 credits (2,268,123)GFN Sapphire: Earned 20,000,000 credits (25,886,632)PSA Double Silver: Earned 200,000,000 credits (329,341,056)
Message 109390 - Posted: 16 Aug 2017 | 23:46:46 UTC
Last modified: 16 Aug 2017 | 23:48:13 UTC

Speaking as the person who made the code changes, we are in fact reducing k for all bases. I was supposed to remove that code, but chose to leave it in. I neglected to tell Mike about it until now. My real life is a bit busy at the moment, so sometimes I'm forgetting things like that.

while ($k % $b == 0) { $k /= $b; $n++; }

Michael Millerick
Volunteer tester
Send message
Joined: 4 Feb 09
Posts: 609
ID: 35074
Credit: 120,918,304
RAC: 158
321 LLR Amethyst: Earned 1,000,000 credits (1,063,954)Cullen LLR Gold: Earned 500,000 credits (665,748)ESP LLR Amethyst: Earned 1,000,000 credits (1,025,432)Generalized Cullen/Woodall LLR Silver: Earned 100,000 credits (120,091)PPS LLR Turquoise: Earned 5,000,000 credits (5,123,986)PSP LLR Amethyst: Earned 1,000,000 credits (1,134,556)SoB LLR Amethyst: Earned 1,000,000 credits (1,064,898)SR5 LLR Amethyst: Earned 1,000,000 credits (1,043,015)SGS LLR Amethyst: Earned 1,000,000 credits (1,072,821)TRP LLR Amethyst: Earned 1,000,000 credits (1,005,623)Woodall LLR Amethyst: Earned 1,000,000 credits (1,042,977)321 Sieve (suspended) Bronze: Earned 10,000 credits (20,737)Cullen/Woodall Sieve (suspended) Ruby: Earned 2,000,000 credits (4,911,344)Generalized Cullen/Woodall Sieve Amethyst: Earned 1,000,000 credits (1,782,743)PPS Sieve Sapphire: Earned 20,000,000 credits (45,157,854)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Amethyst: Earned 1,000,000 credits (1,034,014)TRP Sieve (suspended) Ruby: Earned 2,000,000 credits (2,070,774)AP 26/27 Amethyst: Earned 1,000,000 credits (1,169,245)GFN Ruby: Earned 2,000,000 credits (3,800,771)PSA Sapphire: Earned 20,000,000 credits (46,607,721)
Message 109403 - Posted: 18 Aug 2017 | 2:54:20 UTC

Maximizing the return the challenge will have. Excellent!
____________

axn
Volunteer developer
Send message
Joined: 29 Dec 07
Posts: 244
ID: 16874
Credit: 8,653,382
RAC: 0
321 LLR Silver: Earned 100,000 credits (115,840)Cullen LLR Silver: Earned 100,000 credits (175,895)ESP LLR Silver: Earned 100,000 credits (330,310)PPS LLR Gold: Earned 500,000 credits (748,824)SoB LLR Silver: Earned 100,000 credits (176,825)SR5 LLR Ruby: Earned 2,000,000 credits (2,010,622)SGS LLR Silver: Earned 100,000 credits (101,658)Cullen/Woodall Sieve (suspended) Bronze: Earned 10,000 credits (32,498)PPS Sieve Ruby: Earned 2,000,000 credits (2,479,572)GFN Ruby: Earned 2,000,000 credits (2,380,031)PSA Silver: Earned 100,000 credits (101,309)
Message 109405 - Posted: 18 Aug 2017 | 4:35:18 UTC - in response to Message 109390.

Speaking as the person who made the code changes, we are in fact reducing k for all bases. I was supposed to remove that code, but chose to leave it in. I neglected to tell Mike about it until now. My real life is a bit busy at the moment, so sometimes I'm forgetting things like that.

while ($k % $b == 0) { $k /= $b; $n++; }


LOL! Well it doesn't hurt. But I replicated the result, and Mike's right -- there is no need to normalize the k, since apparently LLR (or perhaps gwnum library) is doing it. I can see that when k is a multiple of base, it chooses a lower FFT (compared to adjacent k's), even without explicit normalizing.
Sorry about that -- I should've done my homework before posting about it.

Profile composite
Send message
Joined: 16 Feb 10
Posts: 314
ID: 55391
Credit: 338,444,542
RAC: 259,167
321 LLR Ruby: Earned 2,000,000 credits (3,454,678)Cullen LLR Gold: Earned 500,000 credits (676,922)ESP LLR Amethyst: Earned 1,000,000 credits (1,021,827)Generalized Cullen/Woodall LLR Amethyst: Earned 1,000,000 credits (1,715,268)PPS LLR Ruby: Earned 2,000,000 credits (3,311,588)PSP LLR Ruby: Earned 2,000,000 credits (3,138,070)SoB LLR Ruby: Earned 2,000,000 credits (3,225,373)SR5 LLR Turquoise: Earned 5,000,000 credits (5,071,131)SGS LLR Ruby: Earned 2,000,000 credits (2,860,720)TRP LLR Amethyst: Earned 1,000,000 credits (1,006,014)Woodall LLR Amethyst: Earned 1,000,000 credits (1,291,833)321 Sieve (suspended) Amethyst: Earned 1,000,000 credits (1,228,005)Cullen/Woodall Sieve (suspended) Turquoise: Earned 5,000,000 credits (5,571,178)Generalized Cullen/Woodall Sieve Ruby: Earned 2,000,000 credits (2,206,963)PPS Sieve Double Bronze: Earned 100,000,000 credits (141,097,197)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Jade: Earned 10,000,000 credits (10,165,888)TRP Sieve (suspended) Sapphire: Earned 20,000,000 credits (20,071,454)AP 26/27 Ruby: Earned 2,000,000 credits (2,439,709)GFN Sapphire: Earned 20,000,000 credits (26,149,758)PSA Double Bronze: Earned 100,000,000 credits (102,758,261)
Message 109411 - Posted: 18 Aug 2017 | 23:22:01 UTC - in response to Message 109405.
Last modified: 18 Aug 2017 | 23:23:41 UTC

Hmm, a process akin to normalization could be responsible for the WTF effect, which is using a timing sidechannel during sieving to "discover" small primes in the blocking factor. So far there is no other explanation for that weirdness.

HonzaProject donor
Volunteer moderator
Volunteer tester
Project scientist
Send message
Joined: 15 Aug 05
Posts: 1605
ID: 352
Credit: 1,756,123,988
RAC: 1,199,208
321 LLR Jade: Earned 10,000,000 credits (15,812,082)Cullen LLR Sapphire: Earned 20,000,000 credits (20,758,697)ESP LLR Sapphire: Earned 20,000,000 credits (20,183,757)Generalized Cullen/Woodall LLR Sapphire: Earned 20,000,000 credits (21,044,302)PPS LLR Emerald: Earned 50,000,000 credits (51,016,093)PSP LLR Sapphire: Earned 20,000,000 credits (23,462,639)SoB LLR Sapphire: Earned 20,000,000 credits (22,553,364)SR5 LLR Sapphire: Earned 20,000,000 credits (20,233,642)SGS LLR Sapphire: Earned 20,000,000 credits (20,037,618)TPS LLR (retired) Bronze: Earned 10,000 credits (43,033)TRP LLR Jade: Earned 10,000,000 credits (18,591,918)Woodall LLR Sapphire: Earned 20,000,000 credits (20,037,694)321 Sieve (suspended) Ruby: Earned 2,000,000 credits (4,024,795)Cullen/Woodall Sieve (suspended) Ruby: Earned 2,000,000 credits (4,142,109)Generalized Cullen/Woodall Sieve Sapphire: Earned 20,000,000 credits (20,357,260)PPS Sieve Double Silver: Earned 200,000,000 credits (376,970,310)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Sapphire: Earned 20,000,000 credits (20,288,222)TRP Sieve (suspended) Sapphire: Earned 20,000,000 credits (20,149,354)AP 26/27 Sapphire: Earned 20,000,000 credits (20,062,973)GFN Double Gold: Earned 500,000,000 credits (511,313,346)PSA Double Gold: Earned 500,000,000 credits (525,027,972)
Message 109548 - Posted: 24 Aug 2017 | 7:31:14 UTC

While discussed and implement trick with b=25,49,121 brings about 4% speed-up, recently found prime makes GCW yet another 7% faster on top of that. Nice!
____________
My stats
Badge score: 1*1 + 5*2 + 7*2 + 8*12 + 9*1 + 11*1 + 12*2 = 165

Post to thread

Message boards : Generalized Cullen/Woodall prime search : How to speed up (some) GCW units by 10%+

[Return to PrimeGrid main page]
Copyright © 2005 - 2017 Rytis Slatkevičius (contact) and PrimeGrid community. Server load 2.03, 2.04, 1.98
Generated 26 Sep 2017 | 2:07:54 UTC