mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Aliquot Sequences

Reply
 
Thread Tools
Old 2021-08-25, 09:31   #3070
bur
 
bur's Avatar
 
Aug 2020
79*6581e-4;3*2539e-3

13·31 Posts
Default

Quote:
As for the second question, my comment was intended to be "for constant param choices", i.e. same incr such as Charybdis searching ~20M while you and I searched at 2 or 3M.
But won't a larger incr decrease the search time? It was recommended to use incr=2310 for larger value ranges, I assumed this was done because otherwise the search takes too long?
bur is offline   Reply With Quote
Old 2021-08-25, 11:52   #3071
charybdis
 
charybdis's Avatar
 
Apr 2020

5×101 Posts
Default

In previous searches (mostly degree 5), larger incr has been used to compensate for the disadvantage of searching at higher leading coefficients. Roughly speaking, polys with larger coeffs tend to have worse size properties, and using an incr value with more small prime factors gives a small boost to the root properties to make up for this.
charybdis is offline   Reply With Quote
Old 2021-08-25, 14:39   #3072
bur
 
bur's Avatar
 
Aug 2020
79*6581e-4;3*2539e-3

19316 Posts
Default

Ah, I thought incr controlled how thoroughly a range is searched and larger incr resulted in shorter search times. So it is the other way around? Would it have a slight advantage to use larger incr even for smaller coefficients (regardless of whether it's worth it)?
bur is offline   Reply With Quote
Old 2021-08-25, 15:00   #3073
charybdis
 
charybdis's Avatar
 
Apr 2020

5×101 Posts
Default

You've got it right: the leading coefficients that are searched are the multiples of incr, so a 1M range at incr=2310 will be much quicker than a 1M range at incr=420. We don't use larger incr from the start because we don't want to get to large coefficients too quickly.
charybdis is offline   Reply With Quote
Old 2021-08-25, 18:02   #3074
bur
 
bur's Avatar
 
Aug 2020
79*6581e-4;3*2539e-3

13×31 Posts
Default

At the risk of looking like an idiot, but I still don't get it.


Quote:
so a 1M range at incr=2310 will be much quicker than a 1M range at incr=420
Quote:
Smaller coeff's usually take a little longer to search; that is, 30-31M should run slightly faster than 2-3M
If larger incr is faster, I assume it's less thorough. If 30M-31M is faster than 1M-2M, then why do we use a large incr for 30M-31M? It is faster than 1M-2M even at the same incr, so why make it even faster and less thorough? Or isn't a large incr less thorough?

Last fiddled with by bur on 2021-08-25 at 18:04
bur is offline   Reply With Quote
Old 2021-08-25, 19:00   #3075
charybdis
 
charybdis's Avatar
 
Apr 2020

5·101 Posts
Default

The rate at which we find raw polynomials stays roughly constant (assuming fixed P), so we want the average score of the polynomials we find to be as high as possible through the search. In general, we observe:

1. If incr is kept constant, lower leading coeffs give higher average scores.

2. Among leading coeffs of similar size, those with more small prime factors give higher average scores. Note that this is why we choose incr values like 420 in the first place.

It's not hard to see the effects of point 2: look at the leading coefficients of the best polynomials from your searches, and see how smooth they tend to be, even given that they're multiples of 420. For example, the current leading poly came from a stage 1 hit with c6 = 18572400 = 2^4 * 3^2 * 5^2 * 7 * 11 * 67, so it would still have been found with incr = 2310 or 4620.

So if we started off at a larger incr, we would start off finding better polynomials than with incr=420 due to point 2... but we would run into the effects of point 1 much more quickly. Once we get to leading coeffs high enough that scores have dropped noticeably due to point 1, the theory is that increasing incr to 2310 or 4620 will then give a temporary boost to the average score.

I don't think we're seeing much of the effect of point 1 yet, which is why I've stuck with incr=420 for the 25M to 40M range. It's possible that incr=2310 or 4620 over a much larger range would have been better, but that's difficult to test in advance.

I wouldn't mind CADO adding an option to put a smoothness bound on the leading coefficients...

Last fiddled with by charybdis on 2021-08-25 at 19:05
charybdis is offline   Reply With Quote
Old 2021-08-26, 21:18   #3076
swellman
 
swellman's Avatar
 
Jun 2012

23·401 Posts
Default

41-45M best poly found was only 2.921e-16. 10th best was 2.506e-16.

I should be finished with 45-50M late Friday.
swellman is online now   Reply With Quote
Old 2021-08-27, 07:48   #3077
bur
 
bur's Avatar
 
Aug 2020
79*6581e-4;3*2539e-3

19316 Posts
Default

So large incr gives better polys on average due to the many small factors, but it skips a lot of coefficients of which it isn't a multiple? If so, then I finally understood.

6e6-7e6 is at 75%, should be finished in about 30 hours.
bur is offline   Reply With Quote
Old 2021-08-27, 08:25   #3078
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

116258 Posts
Default

Quote:
Originally Posted by bur View Post
If so, then I finally understood.
VBCurtis is online now   Reply With Quote
Old 2021-08-27, 17:02   #3079
bur
 
bur's Avatar
 
Aug 2020
79*6581e-4;3*2539e-3

1100100112 Posts
Default

Quote:
Originally Posted by VBCurtis View Post
Yes, I'm quite proud of myself. ;)


And yet one more question. Wouldn't it make sense to go over one of the lower ranges again with larger incr? Or does the same argument apply as with varying P that the time is better spent on a fresh range?
bur is offline   Reply With Quote
Old 2021-08-27, 17:19   #3080
charybdis
 
charybdis's Avatar
 
Apr 2020

1F916 Posts
Default

Going over a range with larger incr would be repeating work on the coefficients that are multiples of both incr values. If the new incr (say 4620) was a multiple of the old incr (say 420), you wouldn't be doing any new work at all.
charybdis is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Reserved for MF - Sequence 3366 RichD Aliquot Sequences 526 2021-10-27 19:01
Reserved for MF - Sequence 276 kar_bon Aliquot Sequences 136 2021-10-21 16:17
Reserved for MF - Sequence 3408 RichD Aliquot Sequences 476 2021-10-04 20:47
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 00:49.


Thu Oct 28 00:49:34 UTC 2021 up 96 days, 19:18, 0 users, load averages: 2.68, 2.86, 2.70

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.