Join PrimeGrid
Returning Participants
Community
Leader Boards
Results
Other
drummers-lowrise
|
Message boards :
AP26 - AP27 Search :
Change to AP27 search parameters
Author |
Message |
Michael Goetz Volunteer moderator Project administrator
 Send message
Joined: 21 Jan 10 Posts: 13524 ID: 53948 Credit: 244,359,622 RAC: 386,594
                          
|
When we started the AP 27 search, we decided to search both shift 0 and shift 640 equally.
With an AP27 challenge starting in a few weeks, I decided to look into whether it was time to also start searching shift 1280.
The higher the shift, the fewer AP sequences you'll find. But as k increases within a shift, the number of sequences you find also decreases. There comes a point where you should start searching the next shift.
Right now, for every million k we search, we're finding about 1400 APs at shift 0 and about 1050 APs at shift 640.
If we started shift 1280, we'd probably get something between 700 and 1000 APs per million k. Definitely less than either 0 or 640.
Rather than open up 1280, we've closed down 640 and will run only shift 0 for a while until it's producing about 1050 APs per million k.
Both shift 0 and shift 640 are currently at approximately k=74M.
____________
My lucky number is 75898524288+1 | |
|
|
I may have missed it in my thread browsing, but what exactly are "shifts"?
Also, will this affect task size (i.e. runtime) and/or credit?
____________
Eating more cheese on Thursdays. | |
|
Michael Goetz Volunteer moderator Project administrator
 Send message
Joined: 21 Jan 10 Posts: 13524 ID: 53948 Credit: 244,359,622 RAC: 386,594
                          
|
I may have missed it in my thread browsing, but what exactly are "shifts"?
Also, will this affect task size (i.e. runtime) and/or credit?
Read this:
http://www.math.uni.wroc.pl/~jwr/AP26/AP26v3.pdf
If this was GFN, you could think of the shift as "N" and k as "B". It's not the same numerical relationship, but the roles are similar. The shift is a set of candidates that are going to be tested, with k iterating through the set.
In the paper, each shift was 64 bits, so the shifts were 0, 64, 128, 192, etc.
In the AP27 version of the search, we search 10 shifts at once, effectively creating 640 bit shifts, so the shifts are 0, 640, 1280, 1920, etc.
Right now, both shift 0 and shift 640 are at k = ~74M. We're freezing shift 640 where it is, and continuing with shift 0 until it reaches k = 143 M. At that point we will resume shift 640 and we will also start shift 1280.
From then on we will follow this pattern:
* All the shifts that have been started (initially, 0, 640, and 1280) will run in parallel until the most recently started shift (1280 initially) reaches k = 70M. Every shift will be approximately 70M k's ahead of the next shift.
* When the most recent shift gets to k = 70M, another shift (the next will be 1920) is started at k=0.
* The process then repeats.
* When a shift reaches k = 318M, it is shut down (the AP27 program will overflow otherwise).
* Shift 9600 is the last shift where k can go up to 318M. Shifts beyond 9600 have lower K limits.
____________
My lucky number is 75898524288+1 | |
|
|
That clears it up a bit, thanks. The paper was an interesting read, will need some digesting, though.
____________
Eating more cheese on Thursdays. | |
|
dukebgVolunteer tester
 Send message
Joined: 21 Nov 17 Posts: 238 ID: 950482 Credit: 23,670,125 RAC: 1,066
                  
|
In the AP27 version of the search, we search 10 shifts at once, effectively creating 640 bit shifts, so the shifts are 0, 640, 1280, 2560, etc.
Wouldn't the next after 1280 be 1920 then? | |
|
|
In the AP27 version of the search, we search 10 shifts at once, effectively creating 640 bit shifts, so the shifts are 0, 640, 1280, 2560, etc.
Wouldn't the next after 1280 be 1920 then?
Either: ..., 0, 640, 1280, 1920, 2560, 3200, 3840, ... or: ..., 5, 10, 20, 40, 80, 160, 320, 640, 1280, 2560, 5120, 10240, ... /JeppeSN | |
|
Michael Goetz Volunteer moderator Project administrator
 Send message
Joined: 21 Jan 10 Posts: 13524 ID: 53948 Credit: 244,359,622 RAC: 386,594
                          
|
In the AP27 version of the search, we search 10 shifts at once, effectively creating 640 bit shifts, so the shifts are 0, 640, 1280, 2560, etc.
Wouldn't the next after 1280 be 1920 then?
Yes, it would be. I'll correct the 'plan'. Thanks.
____________
My lucky number is 75898524288+1 | |
|
|
So here's a somewhat "lazy" question because I haven't done any digging. I'm wondering how the list of ap's found is sorted. I ask because several ap's I've found recently are listed much lower than earlier finds.
Is this because of the change in parameters and we are only doing shift 0 at the moment? Also, is there a size for the ap (not referring to whether it's a 20 or 21 or ....) but with in the same range? (maybe this is the reason for the order)
Cheers | |
|
|
So here's a somewhat "lazy" question because I haven't done any digging. I'm wondering how the list of ap's found is sorted. I ask because several ap's I've found recently are listed much lower than earlier finds.
Is this because of the change in parameters and we are only doing shift 0 at the moment? Also, is there a size for the ap (not referring to whether it's a 20 or 21 or ....) but with in the same range? (maybe this is the reason for the order)
Cheers
Currently, looking only at your AP24, I see this:AP24: 316274648710690823+72225058*23#*n for n=0..23 (2018-10-07 12:11:54 UTC)
AP24: 288692820895984987+15022730*23#*n for n=0..23 (2016-11-30 21:36:43 UTC)
AP24: 243773399004862751+10054941*23#*n for n=0..23 (2016-11-18 23:03:18 UTC)
AP24: 265437309240041647+4081573*23#*n for n=0..23 (2016-10-02 02:09:19 UTC)
AP24: 251506340752380587+4245962*23#*n for n=0..23 (2016-10-03 09:24:18 UTC)
AP24: 213679296184640981+6537955*23#*n for n=0..23 (2016-10-23 03:20:27 UTC)
AP24: 194193315973220033+5435343*23#*n for n=0..23 (2016-10-14 01:35:27 UTC)
AP24: 57568392051724789+24248430*23#*n for n=0..23 (2017-03-13 07:15:13 UTC)
This seems to be "unsorted". It is not sorted by smallest term (the part before the plus, such as 316274648710690823). It is not sorted by the common difference in the progression (the coefficient to n, such as 72225058*23#). And it is also not sorted by the date (such as (2018-10-07 12:11:54 UTC)).
/JeppeSN | |
|
Michael Goetz Volunteer moderator Project administrator
 Send message
Joined: 21 Jan 10 Posts: 13524 ID: 53948 Credit: 244,359,622 RAC: 386,594
                          
|
So here's a somewhat "lazy" question because I haven't done any digging. I'm wondering how the list of ap's found is sorted. I ask because several ap's I've found recently are listed much lower than earlier finds.
Is this because of the change in parameters and we are only doing shift 0 at the moment? Also, is there a size for the ap (not referring to whether it's a 20 or 21 or ....) but with in the same range? (maybe this is the reason for the order)
Cheers
There's two places the AP list is displayed, the big list of everyone's APs (including some that weren't found at PrimeGrid), and your personal list.
Both are sorted first by length, i.e., the AP26s are shown by AP25s, and within each length, by size. Size is the largest prime in that AP sequence.
This seems to be "unsorted". It is not sorted by smallest term (the part before the plus, such as 316274648710690823). It is not sorted by the common difference in the progression (the coefficient to n, such as 72225058*23#). And it is also not sorted by the date (such as (2018-10-07 12:11:54 UTC)).
You were SO close! It's sorted by the largest term. That incorporates both the first term and the difference between terms.
____________
My lucky number is 75898524288+1 | |
|
|
There's two places the AP list is displayed, the big list of everyone's APs (including some that weren't found at PrimeGrid), and your personal list.
Both are sorted first by length, i.e., the AP26s are shown by AP25s, and within each length, by size. Size is the largest prime in that AP sequence.
This seems to be "unsorted". It is not sorted by smallest term (the part before the plus, such as 316274648710690823). It is not sorted by the common difference in the progression (the coefficient to n, such as 72225058*23#). And it is also not sorted by the date (such as (2018-10-07 12:11:54 UTC)).
You were SO close! It's sorted by the largest term. That incorporates both the first term and the difference between terms.
Thanks much - I just wasn't sure how things were sorted.
Cheers Rick
____________
@AggieThePew
| |
|
|
You were SO close! It's sorted by the largest term. That incorporates both the first term and the difference between terms.
Ah, yes, that is true:(largest term: 686871244638829403) AP24: 316274648710690823+72225058*23#*n for n=0..23 (2018-10-07 12:11:54 UTC)
(largest term: 365776491767492287) AP24: 288692820895984987+15022730*23#*n for n=0..23 (2016-11-30 21:36:43 UTC)
(largest term: 295366668848388161) AP24: 243773399004862751+10054941*23#*n for n=0..23 (2016-11-18 23:03:18 UTC)
(largest term: 286380415437785377) AP24: 265437309240041647+4081573*23#*n for n=0..23 (2016-10-02 02:09:19 UTC)
(largest term: 273292949267672207) AP24: 251506340752380587+4245962*23#*n for n=0..23 (2016-10-03 09:24:18 UTC)
(largest term: 247226432516900531) AP24: 213679296184640981+6537955*23#*n for n=0..23 (2016-10-23 03:20:27 UTC)
(largest term: 222082800167221463) AP24: 194193315973220033+5435343*23#*n for n=0..23 (2016-10-14 01:35:27 UTC)
(largest term: 181990384410689089) AP24: 57568392051724789+24248430*23#*n for n=0..23 (2017-03-13 07:15:13 UTC) /JeppeSN | |
|
|
Just a question. Since we've changed the search pool so to speak and limited it to just 0 for now was wondering if your estimate of found APs was holding true. | |
|
Michael Goetz Volunteer moderator Project administrator
 Send message
Joined: 21 Jan 10 Posts: 13524 ID: 53948 Credit: 244,359,622 RAC: 386,594
                          
|
Just a question. Since we've changed the search pool so to speak and limited it to just 0 for now was wondering if your estimate of found APs was holding true.
I'm not sure I understand your question.
____________
My lucky number is 75898524288+1 | |
|
|
Asked the wrong question.
Since the change to shift 0 only, is there any change in the distribution of APs found? Ie, more AP20's or more AP22's ? Just curious if the increase in units being worked made any difference what so ever in what AP's were found both in number and/or number (20-27). | |
|
Michael Goetz Volunteer moderator Project administrator
 Send message
Joined: 21 Jan 10 Posts: 13524 ID: 53948 Credit: 244,359,622 RAC: 386,594
                          
|
Asked the wrong question.
Since the change to shift 0 only, is there any change in the distribution of APs found? Ie, more AP20's or more AP22's ? Just curious if the increase in units being worked made any difference what so ever in what AP's were found both in number and/or number (20-27).
A) I don't know. This isn't the kind of thing I normally look at.
B) The change has only been in place for a few days.
C) When analyzing the data while we were considering whether or not to change the shifts, one of the things I looked at is whether the likelihood of finding APs of a certain length as either k or the shift varied was different than the overall likelihood of finding APs in general. I did not see any consistent pattern indicating that the probability of finding length X APs would be any different than length Y if we vary the parameters. In other words, we'll find more (or less) APs, but it doesn't favor long APs vs short APs (or viceversa).
____________
My lucky number is 75898524288+1 | |
|
|
Thanks was just wondering because the higher end AP's I was finding seem to have dropped off. I wasn't sure if it was because there's a lot more folks or units being run or what. No biggie just curious. | |
|
Michael Goetz Volunteer moderator Project administrator
 Send message
Joined: 21 Jan 10 Posts: 13524 ID: 53948 Credit: 244,359,622 RAC: 386,594
                          
|
Here's some raw data. Feel free to come to your own conclusions. AP20 through AP26 are percentages of total.
+-------+------+-------+---------+---------+--------+--------+--------+--------+--------+
| month | day | total | AP20 | AP21 | AP22 | AP23 | AP24 | AP25 | AP26 |
+-------+------+-------+---------+---------+--------+--------+--------+--------+--------+
| 10 | 20 | 232 | 81.0345 | 15.5172 | 2.5862 | 0.0000 | 0.8621 | 0.0000 | 0.0000 |
| 10 | 21 | 244 | 71.7213 | 19.6721 | 6.5574 | 1.2295 | 0.8197 | 0.0000 | 0.0000 |
| 10 | 22 | 256 | 78.1250 | 17.5781 | 3.5156 | 0.7813 | 0.0000 | 0.0000 | 0.0000 |
| 10 | 23 | 202 | 78.7129 | 14.8515 | 4.9505 | 0.9901 | 0.4950 | 0.0000 | 0.0000 |
| 10 | 24 | 161 | 72.0497 | 19.8758 | 6.2112 | 1.8634 | 0.0000 | 0.0000 | 0.0000 |
| 10 | 25 | 167 | 71.8563 | 19.1617 | 6.5868 | 2.3952 | 0.0000 | 0.0000 | 0.0000 |
| 10 | 26 | 239 | 76.5690 | 16.7364 | 5.4393 | 0.8368 | 0.0000 | 0.4184 | 0.0000 |
| 10 | 27 | 238 | 76.8908 | 17.2269 | 5.4622 | 0.0000 | 0.4202 | 0.0000 | 0.0000 |
| 10 | 28 | 205 | 77.0732 | 18.5366 | 3.9024 | 0.4878 | 0.0000 | 0.0000 | 0.0000 |
| 10 | 29 | 221 | 79.6380 | 15.3846 | 2.2624 | 2.7149 | 0.0000 | 0.0000 | 0.0000 |
| 10 | 30 | 200 | 75.0000 | 19.5000 | 4.5000 | 0.5000 | 0.5000 | 0.0000 | 0.0000 |
| 10 | 31 | 161 | 72.6708 | 18.0124 | 6.2112 | 2.4845 | 0.6211 | 0.0000 | 0.0000 |
| 11 | 1 | 184 | 77.1739 | 16.8478 | 5.9783 | 0.0000 | 0.0000 | 0.0000 | 0.0000 |
| 11 | 2 | 185 | 72.4324 | 20.0000 | 7.5676 | 0.0000 | 0.0000 | 0.0000 | 0.0000 |
| 11 | 3 | 212 | 78.3019 | 15.0943 | 5.6604 | 0.4717 | 0.4717 | 0.0000 | 0.0000 |
| 11 | 4 | 225 | 76.4444 | 19.5556 | 2.2222 | 1.3333 | 0.4444 | 0.0000 | 0.0000 |
| 11 | 5 | 262 | 76.7176 | 17.5573 | 4.5802 | 1.1450 | 0.0000 | 0.0000 | 0.0000 |
| 11 | 6 | 297 | 75.0842 | 21.2121 | 2.6936 | 1.0101 | 0.0000 | 0.0000 | 0.0000 |
| 11 | 7 | 393 | 79.6438 | 16.2850 | 3.3079 | 0.5089 | 0.2545 | 0.0000 | 0.0000 |
| 11 | 8 | 245 | 76.3265 | 18.7755 | 3.6735 | 0.8163 | 0.4082 | 0.0000 | 0.0000 |
| 11 | 9 | 140 | 76.4286 | 20.0000 | 2.8571 | 0.7143 | 0.0000 | 0.0000 | 0.0000 |
+-------+------+-------+---------+---------+--------+--------+--------+--------+--------+
____________
My lucky number is 75898524288+1 | |
|
Michael Goetz Volunteer moderator Project administrator
 Send message
Joined: 21 Jan 10 Posts: 13524 ID: 53948 Credit: 244,359,622 RAC: 386,594
                          
|
In the AP27 version of the search, we search 10 shifts at once, effectively creating 640 bit shifts, so the shifts are 0, 640, 1280, 1920, etc.
Right now, both shift 0 and shift 640 are at k = ~74M. We're freezing shift 640 where it is, and continuing with shift 0 until it reaches k = 143 M. At that point we will resume shift 640 and we will also start shift 1280.
From then on we will follow this pattern:
* All the shifts that have been started (initially, 0, 640, and 1280) will run in parallel until the most recently started shift (1280 initially) reaches k = 70M. Every shift will be approximately 70M k's ahead of the next shift.
* When the most recent shift gets to k = 70M, another shift (the next will be 1920) is started at k=0.
* The process then repeats.
* When a shift reaches k = 318M, it is shut down (the AP27 program will overflow otherwise).
* Shift 9600 is the last shift where k can go up to 318M. Shifts beyond 9600 have lower K limits.
Shift 0 has reached 143M, and we have resumed shift 640 and started shift 1280.
In case anyone's wondering, extrapolating how long it too to do 70M on shift 0 to all 11 shifts, if the processing rate stayed the same we'd have 41 years worth of work.
____________
My lucky number is 75898524288+1 | |
|
Bur Volunteer tester
 Send message
Joined: 25 Feb 20 Posts: 337 ID: 1241833 Credit: 40,849,327 RAC: 846,386
                
|
I don't really understand the paper posted by Michael in the earlier post.
Is there a simple explanation of the parameters of the AP search? I found this line in stderr:
"ap27_3.01_opencl_windows64.exe 196376536 196376656 0"
How will this relate to the AP tested? Or is it not as simple as that?
Thanks
____________
Primes: 1281979 & 12+8+1979 & 1+2+8+1+9+7+9 & 1^2+2^2+8^2+1^2+9^2+7^2+9^2 & 12*8+19*79 & 12^8-1979 & 1281979 + 4 (cousin prime) | |
|
Ravi FernandoProject administrator Volunteer tester Project scientist Send message
Joined: 21 Mar 19 Posts: 145 ID: 1108183 Credit: 8,631,704 RAC: 6,824
              
|
"ap27_3.01_opencl_windows64.exe 196376536 196376656 0"
How will this relate to the AP tested? Or is it not as simple as that?
The large numbers are lower and upper limits for k, and the 0 is a shift. We are searching for AP's of the form a_i = b*MOD + R + i*D, where:
i is the variable indexing the AP; in the best case (an AP28) it goes from -2 to 25.
b ranges over [0, 639] when shift = 0, or [640, 1279] when shift = 640, etc.
MOD = 2*3*5*29*31*37*41*43*47*53*59 = 258559632607830.
R is a number modulo MOD; for each k it ranges over 5489436680 "good" values, which are determined by the sieving step.
D = k*23# = k*223092870.
For example, if I'm reverse-engineering things correctly, I think robish's AP27 was found with k = 81292139, b = 938, R = 191367151342301, and i running from -1 to 25.
But notice that each workunit tests a huge number of (k, b, R) triples, and sieves out a far huger number. In particular, the number of "good" R's is about 1/47000 of MOD. I think this is really the key to how Jarek made the app so efficient: it sieves out 46999 out of every 47000 candidates without even iterating over them. | |
|
Bur Volunteer tester
 Send message
Joined: 25 Feb 20 Posts: 337 ID: 1241833 Credit: 40,849,327 RAC: 846,386
                
|
Thanks, that was very helpful.
____________
Primes: 1281979 & 12+8+1979 & 1+2+8+1+9+7+9 & 1^2+2^2+8^2+1^2+9^2+7^2+9^2 & 12*8+19*79 & 12^8-1979 & 1281979 + 4 (cousin prime) | |
|
Post to thread
Message boards :
AP26 - AP27 Search :
Change to AP27 search parameters |