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

Toggle Menu

Join PrimeGrid

Returning Participants

Community

Leader Boards

Results

Other

drummers-lowrise

Advanced search

Message boards : Number crunching : LLR initialization

Author Message
Profile composite
Volunteer tester
Send message
Joined: 16 Feb 10
Posts: 841
ID: 55391
Credit: 782,642,585
RAC: 443,190
Discovered 2 mega primesFound 1 prime in the 2018 Tour de Primes321 LLR Turquoise: Earned 5,000,000 credits (5,477,467)Cullen LLR Gold: Earned 500,000 credits (776,297)ESP LLR Ruby: Earned 2,000,000 credits (3,433,680)Generalized Cullen/Woodall LLR Ruby: Earned 2,000,000 credits (2,093,491)PPS LLR Sapphire: Earned 20,000,000 credits (27,298,849)PSP LLR Turquoise: Earned 5,000,000 credits (6,587,988)SoB LLR Sapphire: Earned 20,000,000 credits (33,929,863)SR5 LLR Turquoise: Earned 5,000,000 credits (6,110,877)SGS LLR Ruby: Earned 2,000,000 credits (3,486,285)TRP LLR Turquoise: Earned 5,000,000 credits (7,070,795)Woodall LLR Amethyst: Earned 1,000,000 credits (1,693,614)321 Sieve (suspended) Emerald: Earned 50,000,000 credits (50,256,050)Cullen/Woodall Sieve (suspended) Turquoise: Earned 5,000,000 credits (5,571,178)Generalized Cullen/Woodall Sieve (suspended) Emerald: Earned 50,000,000 credits (50,009,610)PPS Sieve Double Silver: Earned 200,000,000 credits (384,533,962)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 Turquoise: Earned 5,000,000 credits (6,616,128)GFN Emerald: Earned 50,000,000 credits (53,771,465)WW Gold: Earned 500,000 credits (932,000)PSA Double Bronze: Earned 100,000,000 credits (102,762,384)
Message 150302 - Posted: 5 May 2021 | 5:22:28 UTC
Last modified: 5 May 2021 | 5:28:11 UTC

How much compute time elapses from the start of the LLR algorthm until the computation becomes larger than the smallest untested candidate's modulus in each subproject? Before that point computations are the same for all workunits in the subproject, so it would save CPU time globally if the server issues workunits which are precomputed to start from the same advanced step of LLR instead of the first step.

EDIT: A precomputed advanced starting point would be particularly efficient for CPUs receiving workunits that don't have instructions like FMA.

Michael Millerick
Volunteer tester
Send message
Joined: 4 Feb 09
Posts: 799
ID: 35074
Credit: 319,968,572
RAC: 314,007
Discovered 1 mega primeFound 3 primes in the 2020 Tour de PrimesFound 2 primes in the 2021 Tour de Primes321 LLR Ruby: Earned 2,000,000 credits (2,023,600)Cullen LLR Ruby: Earned 2,000,000 credits (2,016,794)ESP LLR Sapphire: Earned 20,000,000 credits (20,186,009)Generalized Cullen/Woodall LLR Ruby: Earned 2,000,000 credits (2,614,647)PPS LLR Jade: Earned 10,000,000 credits (19,232,686)PSP LLR Ruby: Earned 2,000,000 credits (3,043,852)SoB LLR Ruby: Earned 2,000,000 credits (2,031,453)SR5 LLR Ruby: Earned 2,000,000 credits (2,085,475)SGS LLR Ruby: Earned 2,000,000 credits (2,035,177)TRP LLR Ruby: Earned 2,000,000 credits (2,740,707)Woodall LLR Ruby: Earned 2,000,000 credits (2,046,592)321 Sieve (suspended) Turquoise: Earned 5,000,000 credits (5,440,175)Cullen/Woodall Sieve (suspended) Ruby: Earned 2,000,000 credits (4,911,344)Generalized Cullen/Woodall Sieve (suspended) Ruby: Earned 2,000,000 credits (2,077,092)PPS Sieve Emerald: Earned 50,000,000 credits (50,200,870)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 Sapphire: Earned 20,000,000 credits (20,227,947)GFN Emerald: Earned 50,000,000 credits (70,980,363)WW Emerald: Earned 50,000,000 credits (50,104,000)PSA Emerald: Earned 50,000,000 credits (52,866,806)
Message 150303 - Posted: 5 May 2021 | 5:30:13 UTC

My understanding is that part of that initial computation is doing things like determining the FFT size and other things that are intrinsic to the computer that will ultimately be performing the calculation, which would mean that it can't be precomputed and sent to the host that will ultimately perform the calculations.
____________

Yves Gallot
Volunteer developer
Project scientist
Send message
Joined: 19 Aug 12
Posts: 672
ID: 164101
Credit: 305,042,960
RAC: 0
GFN Double Silver: Earned 200,000,000 credits (305,042,960)
Message 150305 - Posted: 5 May 2021 | 8:22:05 UTC - in response to Message 150302.
Last modified: 5 May 2021 | 8:27:15 UTC

How much compute time elapses from the start of the LLR algorthm until the computation becomes larger than the smallest untested candidate's modulus in each subproject? Before that point computations are the same for all workunits in the subproject, so it would save CPU time globally if the server issues workunits which are precomputed to start from the same advanced step of LLR instead of the first step.

Let n ~ 101,000,000.
3n-1 mod n is computed.
The number of loops is log2(n - 1) ~ 106 · log2(10) ~ 3,322,000.
Let e such that 3e = n. We have e = 106 · log(10) / log(3) ~ 2,095,903.
The number of loops to reach that point is log2(e) ~ 21.
Then the computation time for the initialisation stage which is the same for all workunits is 21 / 3,322,000 ~ 0.0006%.

Profile composite
Volunteer tester
Send message
Joined: 16 Feb 10
Posts: 841
ID: 55391
Credit: 782,642,585
RAC: 443,190
Discovered 2 mega primesFound 1 prime in the 2018 Tour de Primes321 LLR Turquoise: Earned 5,000,000 credits (5,477,467)Cullen LLR Gold: Earned 500,000 credits (776,297)ESP LLR Ruby: Earned 2,000,000 credits (3,433,680)Generalized Cullen/Woodall LLR Ruby: Earned 2,000,000 credits (2,093,491)PPS LLR Sapphire: Earned 20,000,000 credits (27,298,849)PSP LLR Turquoise: Earned 5,000,000 credits (6,587,988)SoB LLR Sapphire: Earned 20,000,000 credits (33,929,863)SR5 LLR Turquoise: Earned 5,000,000 credits (6,110,877)SGS LLR Ruby: Earned 2,000,000 credits (3,486,285)TRP LLR Turquoise: Earned 5,000,000 credits (7,070,795)Woodall LLR Amethyst: Earned 1,000,000 credits (1,693,614)321 Sieve (suspended) Emerald: Earned 50,000,000 credits (50,256,050)Cullen/Woodall Sieve (suspended) Turquoise: Earned 5,000,000 credits (5,571,178)Generalized Cullen/Woodall Sieve (suspended) Emerald: Earned 50,000,000 credits (50,009,610)PPS Sieve Double Silver: Earned 200,000,000 credits (384,533,962)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 Turquoise: Earned 5,000,000 credits (6,616,128)GFN Emerald: Earned 50,000,000 credits (53,771,465)WW Gold: Earned 500,000 credits (932,000)PSA Double Bronze: Earned 100,000,000 credits (102,762,384)
Message 150314 - Posted: 5 May 2021 | 20:16:40 UTC - in response to Message 150305.

Thanks Yves, very enlightening.
Quoting one of my professors, back in the day...
That's shooting at mice, we're after elephants.

Profile composite
Volunteer tester
Send message
Joined: 16 Feb 10
Posts: 841
ID: 55391
Credit: 782,642,585
RAC: 443,190
Discovered 2 mega primesFound 1 prime in the 2018 Tour de Primes321 LLR Turquoise: Earned 5,000,000 credits (5,477,467)Cullen LLR Gold: Earned 500,000 credits (776,297)ESP LLR Ruby: Earned 2,000,000 credits (3,433,680)Generalized Cullen/Woodall LLR Ruby: Earned 2,000,000 credits (2,093,491)PPS LLR Sapphire: Earned 20,000,000 credits (27,298,849)PSP LLR Turquoise: Earned 5,000,000 credits (6,587,988)SoB LLR Sapphire: Earned 20,000,000 credits (33,929,863)SR5 LLR Turquoise: Earned 5,000,000 credits (6,110,877)SGS LLR Ruby: Earned 2,000,000 credits (3,486,285)TRP LLR Turquoise: Earned 5,000,000 credits (7,070,795)Woodall LLR Amethyst: Earned 1,000,000 credits (1,693,614)321 Sieve (suspended) Emerald: Earned 50,000,000 credits (50,256,050)Cullen/Woodall Sieve (suspended) Turquoise: Earned 5,000,000 credits (5,571,178)Generalized Cullen/Woodall Sieve (suspended) Emerald: Earned 50,000,000 credits (50,009,610)PPS Sieve Double Silver: Earned 200,000,000 credits (384,533,962)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 Turquoise: Earned 5,000,000 credits (6,616,128)GFN Emerald: Earned 50,000,000 credits (53,771,465)WW Gold: Earned 500,000 credits (932,000)PSA Double Bronze: Earned 100,000,000 credits (102,762,384)
Message 150316 - Posted: 6 May 2021 | 1:34:20 UTC

To give Yves' answer a concrete example,
the time saved by precomputing 21 iterations of PPS-MEGA
for Intel(R) Core(TM)2 Duo CPU E8400 @ 3.00GHz,
which takes about 11,200 CPU seconds using 2 threads to do the full main task,
would be around .06 CPU seconds.

Post to thread

Message boards : Number crunching : LLR initialization

[Return to PrimeGrid main page]
DNS Powered by DNSEXIT.COM
Copyright © 2005 - 2021 Rytis Slatkevičius (contact) and PrimeGrid community. Server load 2.26, 2.45, 2.20
Generated 18 Sep 2021 | 6:51:53 UTC