Join PrimeGrid
Returning Participants
Community
Leader Boards
Results
Other
drummers-lowrise
|
Message boards :
General discussion :
Sieve factors
| Author |
Message |
|---|
|
|
|
To date I have completed 600+ ESP/PSP/SoB sieve workunits and have found 2 factors. Does this provide fodder for only 2 llr workunits? If so , I see how important these tasks are.
____________
  | |
|
 Michael Goetz Volunteer moderator
Project administrator
Send message
Joined: 21 Jan 10
Posts: 13804
ID: 53948
Credit: 345,369,032
RAC: 1,967
                              
|
To date I have completed 600+ ESP/PSP/SoB sieve workunits and have found 2 factors. Does this provide fodder for only 2 llr workunits? If so , I see how important these tasks are.
Every factor found by sieving is two LLR tasks that don't need to be run.
____________
My lucky number is 75898524288+1 | |
|
|
|
|
Ahhh had it backwards then. Still important however.
Edit: Does this mean a substantial amount of work has been greenlighted due to so few factors found or is it all a go until thus eliminated? I'm no math whiz so short answer ok. Sorry if this is covered in a FAQ somewhere. | |
|
Michael GoetzVolunteer moderator
Project administrator
Send message
Joined: 21 Jan 10
Posts: 13804
ID: 53948
Credit: 345,369,032
RAC: 1,967
|
Ahhh had it backwards then. Still important however.
Edit: Does this mean a substantial amount of work has been greenlighted due to so few factors found or is it all a go until thus eliminated? I'm no math whiz so short answer ok. Sorry if this is covered in a FAQ somewhere.
The latter.
You start with a set of numbers, and you don't know whether they're prime or composite. First you use a sieve, which works on the entire set of numbers at once, and it finds COMPOSITE numbers within that set. At the beginning, the sieve finds composite numbers very quickly, but as the sieving continues, it finds composite numbers more and more slowly. (We usually say it finds 'factors' -- it's actually determines that XXXXX is a factor of YYYYY, so saying it finds factors or it finds composite numbers is equally accurate.)
As each composite number is removed from the set of numbers you want to test, that set shrinks and shrinks and shrinks. All the while, the sieve is finding fewer and fewer factors. Eventually, it takes more computing time running the sieve to find a single factor than it does to run run LLR on one of the remaining numbers. At that point, you stop sieving and start testing each remaining unknown candidate with LLR to see if it's composite or if it's prime.
____________
My lucky number is 75898524288+1 | |
|
|
|
Ahhh had it backwards then. Still important however.
Edit: Does this mean a substantial amount of work has been greenlighted due to so few factors found or is it all a go until thus eliminated? I'm no math whiz so short answer ok. Sorry if this is covered in a FAQ somewhere.
Eventually, it takes more computing time running the sieve to find a single factor than it does to run run LLR on one of the remaining numbers. At that point, you stop sieving and start testing each remaining unknown candidate with LLR to see if it's composite or if it's prime.
At what point does this occur? Sorry if it's a stupid question. | |
|
Michael GoetzVolunteer moderator
Project administrator
Send message
Joined: 21 Jan 10
Posts: 13804
ID: 53948
Credit: 345,369,032
RAC: 1,967
|
Ahhh had it backwards then. Still important however.
Edit: Does this mean a substantial amount of work has been greenlighted due to so few factors found or is it all a go until thus eliminated? I'm no math whiz so short answer ok. Sorry if this is covered in a FAQ somewhere.
Eventually, it takes more computing time running the sieve to find a single factor than it does to run run LLR on one of the remaining numbers. At that point, you stop sieving and start testing each remaining unknown candidate with LLR to see if it's composite or if it's prime.
At what point does this occur? Sorry if it's a stupid question.
Hmmmmm. You actually quoted the answer to your question: When it takes more time to remove a factor from the sieve than it does to check a number with LLR or Genefer, then it's time to stop sieving.
While it's possible to figure out mathematically when that will occur based on how fast the sieve runs, how fast LLR runs, how the factor density changes as the sieve gets deeper, and how long each number takes to compute with LLR based on the size of the number, in practice the speeds of both the sieving and LLR change over time because of hardware and software improvements. So forward looking calculations ("We'll stop when we get to point X") tend to only be valid until the next software or hardware inovation, and then everything changes. In practice, it's more like "We seem to be finding factors more slowly now than we can test numbers with LLR, so it's time to stop sieving".
____________
My lucky number is 75898524288+1 | |
|
|
|
Ahhh had it backwards then. Still important however.
Edit: Does this mean a substantial amount of work has been greenlighted due to so few factors found or is it all a go until thus eliminated? I'm no math whiz so short answer ok. Sorry if this is covered in a FAQ somewhere.
Eventually, it takes more computing time running the sieve to find a single factor than it does to run run LLR on one of the remaining numbers. At that point, you stop sieving and start testing each remaining unknown candidate with LLR to see if it's composite or if it's prime.
At what point does this occur? Sorry if it's a stupid question.
Hmmmmm. You actually quoted the answer to your question: When it takes more time to remove a factor from the sieve than it does to check a number with LLR or Genefer, then it's time to stop sieving.
While it's possible to figure out mathematically when that will occur based on how fast the sieve runs, how fast LLR runs, how the factor density changes as the sieve gets deeper, and how long each number takes to compute with LLR based on the size of the number, in practice the speeds of both the sieving and LLR change over time because of hardware and software improvements. So forward looking calculations ("We'll stop when we get to point X") tend to only be valid until the next software or hardware inovation, and then everything changes. In practice, it's more like "We seem to be finding factors more slowly now than we can test numbers with LLR, so it's time to stop sieving".
Yeah, I know I kinda quoted it but I was asking when, like an actual date rather than "when this happens." But yeah, I see what you mean. Thanks :) | |
|
Message boards :
General discussion :
Sieve factors |
