mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Aliquot Sequences

Reply
 
Thread Tools
Old 2021-08-24, 00:43   #3059
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

13CD16 Posts
Default

Quote:
Originally Posted by charybdis View Post
... But are close to 4G raw relations really necessary? Surely we want to choose parameters so that we don't have a duplication rate near 50%?

Edit: the usual doubling rule probably doesn't hold up around the degree 5/6 boundary does it? The degree 6 curve intercepts the degree 5 curve, so once you switch to degree 6 the number of digits per doubling should go up...
You're quite right- The 2330L Cunningham C207 job took 3300M raw relations to yield 1800M uniques, a terrible ratio. However, my point remains that if we went for bigger LP bounds than 34/35, we *would* risk needing more than 2^32 relations.

I imagine something like 2.8-3.0G raw relations to yield 2.0G uniques for this job? I was adding 15% to the previous job's numbers, forgetting just how bad the unique ratio was.

We don't have much data on deg 6 poly score scaling- pretty much just the CADO group's polys for RSA-220/230/240/250. It hasn't crossed my mind to fit a curve to those scores and test for scaling... Good idea!

Last fiddled with by VBCurtis on 2021-08-24 at 00:43
VBCurtis is online now   Reply With Quote
Old 2021-08-24, 01:13   #3060
charybdis
 
charybdis's Avatar
 
Apr 2020

2×3×7×13 Posts
Default

Quote:
Originally Posted by VBCurtis View Post
However, my point remains that if we went for bigger LP bounds than 34/35, we *would* risk needing more than 2^32 relations.
Indeed. And if msieve is used for postprocessing there's a 2^32 limit there too; duplicates could be removed beforehand, so 35/35 would be possible but maybe not 35/36.

Quote:
We don't have much data on deg 6 poly score scaling- pretty much just the CADO group's polys for RSA-220/230/240/250. It hasn't crossed my mind to fit a curve to those scores and test for scaling... Good idea!
Be careful with these types of score comparisons. Msieve/cownoise scores are not suitable for this purpose, as I discovered when comparing them with the CADO scores for my c220 polys. Cownoise still puts the polys pretty much in the same order as CADO, but the ratios are larger: for example, CADO scored the best poly 13% higher than the 10th best, but cownoise scored it 22% higher. I'm inclined to trust the CADO ratios more, because it estimated Murphy-E using the sieving parameters I gave it, rather than the standard values used by msieve/cownoise which are far too small for numbers of this size.

So if you want to compare the scores of the RSA polynomials, you'll need to use CADO's "polyselect3" with some appropriate parameters. This is left as an exercise for the reader :)
charybdis is offline   Reply With Quote
Old 2021-08-24, 06:06   #3061
bur
 
bur's Avatar
 
Aug 2020
79*6581e-4;3*2539e-3

419 Posts
Default

Quote:
Originally Posted by charybdis View Post
We must have spent at least 2 core-years on polyselect so far, and I've just queued up another ~1.5 core-years, or 1% of the estimated sieving time.
My mistake was I underestimated how quickly core-time racks up. Even my two small searches came to nearly 3 core-months already.
bur is offline   Reply With Quote
Old 2021-08-24, 06:24   #3062
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

37·137 Posts
Default

Quote:
Originally Posted by bur View Post
My mistake was I underestimated how quickly core-time racks up. Even my two small searches came to nearly 3 core-months already.
No mistake, sir- the typical rule of thumb is 5% of expected sieve time for poly-select time. We're at about 2%?

It's just that we found a poly scoring almost exactly what we hoped for. As you and Charybdis point out, finding one good one doesn't rule out finding an even-better one; I support a continued search, and finding additional 3.8's would support the idea that a 3.9 or higher is "out there" to be found. I'm taking a break from the search, but if we become convinced the 3.8 is not a massive outlier I'll return to this in a week or three.
VBCurtis is online now   Reply With Quote
Old 2021-08-24, 12:32   #3063
bur
 
bur's Avatar
 
Aug 2020
79*6581e-4;3*2539e-3

419 Posts
Default

By mistake I meant that I'd have guessed we maybe did 3-4 core-months in total.

So I'll continue the poly search at 6e6-7e6, it might at least give some idea how rare 3.5+ polys are.
bur is offline   Reply With Quote
Old 2021-08-24, 17:05   #3064
bur
 
bur's Avatar
 
Aug 2020
79*6581e-4;3*2539e-3

419 Posts
Default

If it's not sure whether larger or smaller P is better and some polynomials will never be found with a specific P, wouldn't it make sense to search the small value ranges again with different P?


If small leading coefficients tend to produce better polys, then going through these ranges with several different P could be worthwhile.
bur is offline   Reply With Quote
Old 2021-08-24, 17:30   #3065
charybdis
 
charybdis's Avatar
 
Apr 2020

2·3·7·13 Posts
Default

Quote:
Originally Posted by bur View Post
If small leading coefficients tend to produce better polys, then going through these ranges with several different P could be worthwhile.
I'm not sure we've got to large enough coefficients that "small leading coefficients tend to produce better polys" is having much of an effect. For degree 5 jobs it would definitely be noticeable at this point, but so far the best 3 CADO polys have come from (pre-sizeopt) leading coeffs around 19e6, 21e6 and 23e6. In addition, basically every polynomial is getting its leading coefficient multiplied up in the optimization process, so there can't be too much harm in having a larger coefficient. In contrast, with large degree 5 searches there are usually a few polys in the top 10 that keep their original leading coefficient.
charybdis is offline   Reply With Quote
Old 2021-08-24, 19:04   #3066
bur
 
bur's Avatar
 
Aug 2020
79*6581e-4;3*2539e-3

1A316 Posts
Default

The searches of low value ranges are faster though, right? It might still make sense to go over them again with a different P. On the other hand, P=10e6 and P=12e6 still have a lot of overlap so the time could very well better be spend on a different range.


BTW, there is no random element to the search or is there?
bur is offline   Reply With Quote
Old 2021-08-24, 21:30   #3067
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

37·137 Posts
Default

No random element.

I believe altering P can be useful, but I wouldn't repeat coefficient ranges.

Smaller coeff's usually take a little longer to search; that is, 30-31M should run slightly faster than 2-3M.

Smaller P values do run faster.
VBCurtis is online now   Reply With Quote
Old 2021-08-25, 05:46   #3068
bur
 
bur's Avatar
 
Aug 2020
79*6581e-4;3*2539e-3

419 Posts
Default

Quote:
I believe altering P can be useful, but I wouldn't repeat coefficient ranges.
Because the limited time is better spend on doing a fresh range?

Quote:
Smaller coeff's usually take a little longer to search;
I thought it was the other way around since larger incr is used for larger value ranges to prevent long search times.
bur is offline   Reply With Quote
Old 2021-08-25, 08:07   #3069
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

37·137 Posts
Default

Changing P leads to some duplication of search, better to try an entirely new range. You'd need a P value half or double the previous one, and we have reason to think either of those options is suboptimal (though that's a judgement of "per unit time", not a prediction that you wouldn't find a better poly). We don't know what the "Best" P is for a given size of input, but hopefully we're close enough to "best" that halving or doubling P would be less efficient than running a new range with P altered by a little (say, something in a range of 8 to 20M). All the default CADO params files from C195 to C230 use P = 10e6, while only C180/185/190 use 5e6 and C240 uses 20e6. To me, that indicates that not much testing was done on the big sample-params files for "best" P, and we should experiment a little.

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.
VBCurtis is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Reserved for MF - Sequence 3366 RichD Aliquot Sequences 530 2021-12-01 20:45
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 22:05.


Wed Dec 1 22:05:43 UTC 2021 up 131 days, 16:34, 1 user, load averages: 0.85, 1.11, 1.20

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.