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 : General discussion : an idea for speeding up LLR testing

Author Message
Profile composite
Volunteer tester
Send message
Joined: 16 Feb 10
Posts: 1002
ID: 55391
Credit: 879,366,379
RAC: 316,449
Discovered 2 mega primesFound 1 prime in the 2018 Tour de PrimesFound 1 prime in the 2022 Tour de Primes321 LLR Turquoise: Earned 5,000,000 credits (6,055,323)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,443,837)PPS LLR Sapphire: Earned 20,000,000 credits (33,759,219)PSP LLR Turquoise: Earned 5,000,000 credits (6,587,988)SoB LLR Sapphire: Earned 20,000,000 credits (44,987,733)SR5 LLR Turquoise: Earned 5,000,000 credits (6,205,694)SGS LLR Ruby: Earned 2,000,000 credits (3,627,819)TRP LLR Turquoise: Earned 5,000,000 credits (7,078,152)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 (457,897,035)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,798,063)GFN Emerald: Earned 50,000,000 credits (57,113,430)WW Ruby: Earned 2,000,000 credits (2,072,000)PSA Double Bronze: Earned 100,000,000 credits (102,762,384)
Message 150846 - Posted: 18 Jul 2021 | 9:44:10 UTC
Last modified: 18 Jul 2021 | 9:46:22 UTC

How about testing 2 candidate primes at the same time for most of the LLR iterations?

Since we are repeating the same calculations for different candidates, say X and Y, just with different modulii and different numbers of iterations, then use a common calculation for (X-1) iterations with the modulus which is the product of the candidates (X*Y).
At iteration X compute the LLR residue for candidate X as A (mod X), and replace the intermediate result A with A (mod Y), then continue as normally until iteration Y with A (mod Y).

Of course, we will be doing (X-1) iterations with a modulus twice as long, plus 1 additional (normal length) modulus operation.
But if the modulus code is faster than the rest of the code in each iteration, then we have a speedup by using the slower code just Y times for each 2 candidates instead of (X+Y) times.
There's a net speedup if the overhead of multiplying the candidates X and Y together, plus 1 additional normal length modulus operation, plus the extra time of using the longer modulus for (X-1) iterations,
is less than the time saved by not repeating the first X iterations of the slower code for candidate Y.

i.e.
A(n+1) = An2-2 (mod X*Y)
At iteration X instead taking AX (mod X*Y)
compute LLR residue for candidate X = AX (mod X)
and replace AX with AX (mod Y)
then continue as normal until iteration Y with
A(n+1) = An2-2 (mod Y)

Profile MiauiKatze
Send message
Joined: 4 Apr 20
Posts: 22
ID: 1251453
Credit: 1,168,485
RAC: 0
PPS LLR Silver: Earned 100,000 credits (104,780)SGS LLR Bronze: Earned 10,000 credits (14,968)PPS Sieve Bronze: Earned 10,000 credits (57,307)AP 26/27 Silver: Earned 100,000 credits (238,537)GFN Silver: Earned 100,000 credits (212,222)WW Gold: Earned 500,000 credits (540,000)
Message 150933 - Posted: 23 Jul 2021 | 12:34:31 UTC

I'm not an expert, but it sounds logical to me. But I doubt it is really that easy to implement. And does the modulo function really behave like this?

A math expert should look at it. What I wrote are just my 2 cents (or maybe even only one :D )

Best regards,
MiauiKatze
____________
--------
"MiauiKatze" is german and means as much as "mewing cat"!
--------

Yves Gallot
Volunteer developer
Project scientist
Send message
Joined: 19 Aug 12
Posts: 705
ID: 164101
Credit: 305,166,630
RAC: 8
GFN Double Silver: Earned 200,000,000 credits (305,166,630)
Message 150934 - Posted: 23 Jul 2021 | 14:32:36 UTC - in response to Message 150846.
Last modified: 23 Jul 2021 | 14:33:17 UTC

Let X ~ Y be two n-bit numbers.
The computation time for one mul modulo X is M(X) = K * n * log(n).
If Z = X * Y, the computation time for one mul modulo X*Y is M(X*Y) = K * 2*n * log(2*n).

With 2 LLR, the computation time is 2 * n * M(X) = 2 * K * n^2 * log(n).
With your algorithm, it is n * M(X*Y) = 2 * K * n^2 * log(2*n).

That's not faster.

Pavel Atnashev
Send message
Joined: 11 Aug 17
Posts: 57
ID: 914937
Credit: 3,943,381,807
RAC: 1,256,394
Discovered 4 mega primesEliminated 3 conjecture "k"s321 LLR Jade: Earned 10,000,000 credits (11,980,856)Cullen LLR Emerald: Earned 50,000,000 credits (71,772,873)ESP LLR Double Ruby: Earned 2,000,000,000 credits (2,000,000,842)Generalized Cullen/Woodall LLR Bronze: Earned 10,000 credits (67,073)PPS LLR Double Bronze: Earned 100,000,000 credits (133,973,142)PSP LLR Double Silver: Earned 200,000,000 credits (314,914,090)SoB LLR Double Amethyst: Earned 1,000,000,000 credits (1,010,504,273)SR5 LLR Double Bronze: Earned 100,000,000 credits (137,511,997)TRP LLR Double Silver: Earned 200,000,000 credits (257,876,275)Woodall LLR Ruby: Earned 2,000,000 credits (4,756,356)Generalized Cullen/Woodall Sieve (suspended) Bronze: Earned 10,000 credits (24,029)
Message 150965 - Posted: 27 Jul 2021 | 6:49:30 UTC - in response to Message 150934.

Not to mention twofold increase in cache and memory bandwidth requirements.

The first rule: one should keep FFT size as small as possible.

Post to thread

Message boards : General discussion : an idea for speeding up LLR testing

[Return to PrimeGrid main page]
DNS Powered by DNSEXIT.COM
Copyright © 2005 - 2022 Rytis Slatkevičius (contact) and PrimeGrid community. Server load 0.63, 1.05, 1.82
Generated 4 Jul 2022 | 2:18:38 UTC