mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Aliquot Sequences

Reply
 
Thread Tools
Old 2021-08-10, 13:30   #2982
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

27·3·13 Posts
Default

Poly searches are organized by leading coefficient and software used.
In CADO, that's admin and admax; in msieve the coefficient range can be specified on the command line.

Suggested CADO settings:
incr of 210 or 420 for small leading coeff's, 2310 or 4620 for larger ones (a totally arbitrary cutoff of 10e6 is "large" to me for sextics). If I used nq=7776, I'd use a smaller incr.

nq of 7776 or 46656- note that 46656 will take 5-6x longer than 7776. These numbers are 6^5 and 6^6- CADO authors suggest powers of the poly degree for this setting, but it's not required. You could try e.g. 20000 to split the difference, but I've never tried.

P of whatever CADO default is for C220 should be fine. root-opt-effort should be set quite high, like 50; the root-opt portion of the search is so much shorter than size-opt searching that we may as well tell CADO to "work hard" on root-opt. You don't have to root-opt many candidates- maybe 20 per thread-week of size-opt searching?

Reserving 0-1e6 on CADO; I'll get started late Wednesday after a matrix finishes.
VBCurtis is offline   Reply With Quote
Old 2021-08-12, 05:27   #2983
bur
 
bur's Avatar
 
Aug 2020
79*6581e-4;3*2539e-3

39810 Posts
Default

So I'd use tasks.sieve.run=false and the respective admin/admax, incr/nq and root-opt-effort settings and just invoke cado as usual?

And a few specific questions:
  • If I understand the incr setting correctly, polysearch time decreases linearly with it? Small values are more thorough but take longer? Since I have no idea, which would you choose, 210 or 420?
  • For nq I'd go with 7776, or has the 46656 an advantage that warrants to 5-6 fold increase in time?
  • How much core-time is usually required per coefficient range?
  • size-opt-effort is kept at 0?

Last fiddled with by bur on 2021-08-12 at 05:34
bur is offline   Reply With Quote
Old 2021-08-12, 14:33   #2984
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

27×3×13 Posts
Default

These are great questions, and pretty thorough!

nq, is in some way, how many candidates are tried for each leading coefficient. I don't know in which way this "how hard to try" is different from the size-opt-effort "how hard to try", but limited experimentation has not yielded success when playing with size-opt-effort. We haven't done enough searches with degree 6 (used for, roughly, 212+ digit jobs) to learn whether the extra time for nq=6^6 yields better polys than 6^5; I can say with some certainty that 6^5 is better than 6^4, though.

Similarly, one could use nq=78125 rather than 15625 for 5th degree searches on other jobs; again, I haven't conclusively ruled out the higher setting as inferior, but I'm pretty certain 15625 is better than 3125. If you try 46656 on this search, try it on a small coeff range (say, 1e6 to 11e5), since it will take a while; you can compare lognorm (the score reported from size-opt before root-opt takes place) of a 100k run at 46656 and a 600k run at 7776 to see if the higher setting has merit.

The reason to use a smaller incr is that small coeff values tend to yield good polys more often, so we wish to search more of them. So, I'm going to use incr=210 for 0-4e5 and incr=420 for 4e5-1e6 (two separate runs, I mean). For runs above 1e6, I think I'll use incr=420; once we get above 2e7 I'd change to 2310 or 4620 (adding in 11 as a factor "should" yield good polys a bit more often, but the 11 seems relatively less important than trying more small coeffs, so we only use it once coeffs aren't "small", with "small" really quite arbitrary).
VBCurtis is offline   Reply With Quote
Old 2021-08-12, 15:12   #2985
Gimarel
 
Apr 2010

23×23 Posts
Default

In my experience lower leading coefficients lead to better polys on average. I'd say the higher nq the better. But cado polyselect seems to have a bug, polyselect sometimes stops to output polys for a specific leading coefficient but still uses 100% cpu. So you risk to loose a lot of time if you use a high nq with cado.

Last fiddled with by Gimarel on 2021-08-12 at 15:14
Gimarel is offline   Reply With Quote
Old 2021-08-12, 15:34   #2986
charybdis
 
charybdis's Avatar
 
Apr 2020

17·29 Posts
Default

Quote:
Originally Posted by Gimarel View Post
But cado polyselect seems to have a bug, polyselect sometimes stops to output polys for a specific leading coefficient but still uses 100% cpu.
Sounds like this should be reported to the CADO mailing list if this is actually a bug?
charybdis is offline   Reply With Quote
Old 2021-08-13, 05:35   #2987
bur
 
bur's Avatar
 
Aug 2020
79*6581e-4;3*2539e-3

39810 Posts
Default

Ok, thanks everybody. What about adrange? Should I keep it at the default 5e3? Does it even matter besides less frequent ETA updates?


Quote:
I'd say the higher nq the better.
So 6^6 would yield that much better results to make the increase in time useful?


And about root-opt-effort, is it possible that for small test ranges 50 is a bit high? I test-searched 1e6 to 1.01e6 and size-opt took about 10 minutes, but root-opt is also still going after 10 minutes. I can't imagine it should have that time ratio for larger ranges?


And finally: does the time per range scale linearly? I want to estimate a suitable range to start with so it doesn't take a month.

Last fiddled with by bur on 2021-08-13 at 05:57
bur is offline   Reply With Quote
Old 2021-08-13, 08:18   #2988
Gimarel
 
Apr 2010

23×23 Posts
Default

Quote:
Originally Posted by charybdis View Post
Sounds like this should be reported to the CADO mailing list if this is actually a bug?
I'm not sure. It could be bad parameter selection on my side. I have to do more testing when I have time.
Gimarel is offline   Reply With Quote
Old 2021-08-13, 08:31   #2989
Gimarel
 
Apr 2010

B816 Posts
Default

Quote:
Originally Posted by bur View Post
So 6^6 would yield that much better results to make the increase in time useful?
I have done a short test with
Code:
polyselect -n 5272066026958413205513021090082556639441277154855572268239336980532402881465013381219738819137405617219594641652778228990107677072837959240400905630530715435664638237254654768053674178165309345879869729405448588458952991 -d 6 -t 1 -admin 120 -admax 180 -incr 60 -nq <6^[4567]> -v -P 10000000
Code:
nq  discarded size-optimized    time  time/poly
6^4         4              1   19.12s     3.824s
6^5        20              8  107.95s     3.855s
6^6        85             92  661.50s     3.737s
6^7       473            464 4041.48s     4.313s
So 6^6 seems to be best.
Gimarel is offline   Reply With Quote
Old 2021-08-13, 08:46   #2990
bur
 
bur's Avatar
 
Aug 2020
79*6581e-4;3*2539e-3

2×199 Posts
Default

That nq result is very interesting, so we should really use 6^6?


And to get me started, can anyone give a short estimate on range vs time/core? Can I just use the result from 1e6 to 1.01e6? That would indicate that vbcurtis range would only take half a day on a ten core. Is that correct?


And about root-opt-effort, is it possible that for small test ranges 50 is a bit high? I test-searched 1e6 to 1.01e6 and size-opt took about 10 minutes, but root-opt is also still going after 10 minutes. I can't imagine it should have that time ratio for larger ranges?


(sorry for reposting, but sometimes things get lost after a few posts)
bur is offline   Reply With Quote
Old 2021-08-13, 13:06   #2991
charybdis
 
charybdis's Avatar
 
Apr 2020

17·29 Posts
Default

Quote:
Originally Posted by bur View Post
And about root-opt-effort, is it possible that for small test ranges 50 is a bit high? I test-searched 1e6 to 1.01e6 and size-opt took about 10 minutes, but root-opt is also still going after 10 minutes. I can't imagine it should have that time ratio for larger ranges?
The time taken for rootopt does not depend at all on the size of the range searched. The top "nrkeep" polynomials from sizeopt are fed to rootopt, and it generally only takes a very small range to find this many polynomials (the default c220.params has nrkeep=200), so rootopt for a 10k range will take just as long as rootopt for a 10M range. If you're only searching a small range, I would reduce nrkeep rather than ropteffort. While the 100th best sizeopt hit in your range could produce the best poly *in your range* after rootopt, it's extremely unlikely it would be one of the best polys found in the entire search.

Can't answer the other questions as I've never done degree-6 poly searching before.
charybdis is offline   Reply With Quote
Old 2021-08-13, 15:17   #2992
bur
 
bur's Avatar
 
Aug 2020
79*6581e-4;3*2539e-3

2·199 Posts
Default

Thanks for the explanation. For the start I only want a 24 h or so search to catch errors early on. Since I have no idea what nrkeep value would be useful for that amount of time, I'll wait if vbcurtis has some idea.

Last fiddled with by bur on 2021-08-13 at 15:18
bur is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Reserved for MF - Sequence 276 kar_bon Aliquot Sequences 133 2021-10-16 17:21
Reserved for MF - Sequence 3408 RichD Aliquot Sequences 476 2021-10-04 20:47
Reserved for MF - Sequence 3366 RichD Aliquot Sequences 524 2021-09-06 21:00
Assignments are reserved but not showing up prism019 GPU to 72 6 2020-09-21 22:11
80M to 64 bits ... but not really reserved petrw1 Lone Mersenne Hunters 82 2010-01-11 01:57

All times are UTC. The time now is 08:31.


Mon Oct 18 08:31:33 UTC 2021 up 87 days, 3 hrs, 0 users, load averages: 1.31, 1.33, 1.25

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.