mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Aliquot Sequences

Reply
 
Thread Tools
Old 2021-08-23, 12:23   #3048
charybdis
 
charybdis's Avatar
 
Apr 2020

2·251 Posts
Default

The poly I posted yesterday was the best from my range, but not by that much. Here are the next best two, let's see if Gimarel can work his magic.

Code:
n: 5272066026958413205513021090082556639441277154855572268239336980532402881465013381219738819137405617219594641652778228990107677072837959240400905630530715435664638237254654768053674178165309345879869729405448588458952991
skew: 1907251.281
c0: 8236427797628293049599408725893247072637239772
c1: 19162528353248595305446715812300596109295
c2: -21091088260708627616667662646742165
c3: -12419116707177921879187220801
c4: 7785775652933998252593
c5: 948954265351506
c6: 43482600
Y0: -249636408603218968365364360310503950
Y1: 22334710996682366819620031
# cownoise: e 3.62425400e-16

n: 5272066026958413205513021090082556639441277154855572268239336980532402881465013381219738819137405617219594641652778228990107677072837959240400905630530715435664638237254654768053674178165309345879869729405448588458952991
skew: 1760341.42
c0: 15354638866604858505124720786978674723100123170
c1: -61469554170413960080201338721573680907367
c2: -29684864243265761798289322803166219
c3: 74136878484020854315362790097
c4: 5081461673273545660609
c5: -1949330215164330
c6: 699388200
Y0: -246835163382771953077067062497572256
Y1: 11904096208130921118914953
# cownoise: e 3.47247226e-16
If Gimarel can get one of these close to 3.8e-16, then it might not be worth calling off the search just yet, as it would suggest the 3.849 isn't a huge outlier. And for the record, both of these would have been found with P=10M too.
charybdis is offline   Reply With Quote
Old 2021-08-23, 12:36   #3049
EdH
 
EdH's Avatar
 
"Ed Hall"
Dec 2009
Adirondack Mtns

76628 Posts
Default

Quote:
Originally Posted by charybdis View Post
. . . we just aim for one that's good enough to do the job.
Couldn't almost any found poly be good enough to produce factors, while what we search for is the best poly, of those found, that will produce relations the fastest overall? And throughout the search, we try to balance the poly search time against the sieve time, minimizing the total?

When I was using Msieve across my farm (and working with smaller composites), I put a short hard time on polynomial searching and then went with whatever showed up in that limited search. Many of those polynomials weren't really good, but I still got factors.
EdH is online now   Reply With Quote
Old 2021-08-23, 12:49   #3050
charybdis
 
charybdis's Avatar
 
Apr 2020

50210 Posts
Default

Quote:
Originally Posted by EdH View Post
Couldn't almost any found poly be good enough to produce factors, while what we search for is the best poly, of those found, that will produce relations the fastest overall? And throughout the search, we try to balance the poly search time against the sieve time, minimizing the total?
Yes, I should have chosen my words better. What I meant is that we don't try to search for the best possible poly, but rather we stop when we find one good enough - where "good enough" means that further poly searching would be unlikely to save time overall.

Poly selection is possibly the part of GNFS with most room for improvement. For example, the best polys for this c220 might have degrees 3 and 4 rather than 1 and 6, but we don't have a good way to find such polys.
charybdis is offline   Reply With Quote
Old 2021-08-23, 13:40   #3051
swellman
 
swellman's Avatar
 
Jun 2012

3,203 Posts
Default

My redo of 40-41M with nq=6^7 and P=10M gave a best cownoise score of 2.898e-16.

10th best cownoise was 2.586e-16.

Going to finish my search range of 40-50M with P=10M and nq=6^6.
swellman is offline   Reply With Quote
Old 2021-08-23, 14:03   #3052
Gimarel
 
Apr 2010

23×23 Posts
Default

Quote:
Originally Posted by charybdis View Post
The poly I posted yesterday was the best from my range, but not by that much. Here are the next best two, let's see if Gimarel can work his magic.

If Gimarel can get one of these close to 3.8e-16, then it might not be worth calling off the search just yet, as it would suggest the 3.849 isn't a huge outlier. And for the record, both of these would have been found with P=10M too.
I'm on vacation right now. I'll see what I can do next week.
Gimarel is offline   Reply With Quote
Old 2021-08-23, 17:13   #3053
charybdis
 
charybdis's Avatar
 
Apr 2020

2×251 Posts
Default

Quote:
Originally Posted by Gimarel View Post
I'm on vacation right now. I'll see what I can do next week.
Might as well see if I can get any more hits in the meantime. Taking 25e6 to 40e6 at incr=420.
charybdis is offline   Reply With Quote
Old 2021-08-23, 17:32   #3054
bur
 
bur's Avatar
 
Aug 2020
79*6581e-4;3*2539e-3

2×3×67 Posts
Default

Quote:
Originally Posted by charybdis View Post
What I meant is that we don't try to search for the best possible poly, but rather we stop when we find one good enough - where "good enough" means that further poly searching would be unlikely to save time overall.
Is that point already reached? When I extrapolate from my few factorizations in the 160-170 range a c220 should take about 1000 core-years (veery roughly). So even shaving 1% of the sieving time should save a lot of time. Wouldn't a few more days do some good? Or is the probability to find something better too low?
bur is offline   Reply With Quote
Old 2021-08-23, 18:57   #3055
charybdis
 
charybdis's Avatar
 
Apr 2020

2·251 Posts
Default

Quote:
Originally Posted by bur View Post
Is that point already reached? When I extrapolate from my few factorizations in the 160-170 range a c220 should take about 1000 core-years (veery roughly). So even shaving 1% of the sieving time should save a lot of time. Wouldn't a few more days do some good? Or is the probability to find something better too low?
1000 is an overestimate; a very rough estimate from some quick test-sieving (I=16, lim 500M/800M, lpb 34/35, mfb 64/101) is 150 core-years, and it's probably possible to improve this with better parameters. That said, if NFS@home end up sieving this then it will likely take longer than this because they don't go above 33-bit large primes.

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. As the current best poly doesn't look like an outlier to me, I reckon there's enough chance of beating it by a few percent to make the extra polyselect time worthwhile.
charybdis is offline   Reply With Quote
Old 2021-08-23, 20:09   #3056
ryanp
 
ryanp's Avatar
 
Jun 2012
Boulder, CO

1010010002 Posts
Default

Quote:
Originally Posted by charybdis View Post
1000 is an overestimate; a very rough estimate from some quick test-sieving (I=16, lim 500M/800M, lpb 34/35, mfb 64/101) is 150 core-years, and it's probably possible to improve this with better parameters. That said, if NFS@home end up sieving this then it will likely take longer than this because they don't go above 33-bit large primes.
I volunteer to sieve this, once you've finalized the poly and params.
ryanp is offline   Reply With Quote
Old 2021-08-23, 21:42   #3057
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

3·1,667 Posts
Default

Quote:
Originally Posted by ryanp View Post
I volunteer to sieve this, once you've finalized the poly and params.
Thanks Ryan!

If you end up with a matrix 80 million dimensions or smaller, I can do the matrix-solving (though it would take me 3-4 months for a 70-80M matrix on a dual-10-core 128GB ram machine).

As for sieve-time estimates: the C207 team sieve we did in 2019 took about 125 thread-years (some were not hyperthreaded, so say 70 core-years). C220 is more than two doublings bigger, so I estimate 250-300 core-years of sieve.

Note that using 34/35LP, as we did on the C207, will require nearly 4e9 raw relations- these are the largest LP settings that don't need the extra CADO-compile flag set to handle more than 2^32 raw relations. In hindsight, 33/34 would likely have been optimal for C207, so 34/35 should be fine for C220. We learned from other suboptimal sieve choices in that effort, and I am confident we could get the sieve time below 60 core-years for C207 if we did it again. For instance we started Q far too small, leading to yucky duplicate rates. We also shifted to I=15 to save memory and because it looked faster, which exacerbated the duplicate-relations problems.

I bring this stuff up since Ryan suggested we select the params...

Last fiddled with by VBCurtis on 2021-08-23 at 21:44
VBCurtis is offline   Reply With Quote
Old 2021-08-23, 23:44   #3058
charybdis
 
charybdis's Avatar
 
Apr 2020

2×251 Posts
Default

Quote:
Originally Posted by ryanp View Post
I volunteer to sieve this, once you've finalized the poly and params.
Awesome, thank you!

Quote:
Originally Posted by VBCurtis View Post
As for sieve-time estimates: the C207 team sieve we did in 2019 took about 125 thread-years (some were not hyperthreaded, so say 70 core-years). C220 is more than two doublings bigger, so I estimate 250-300 core-years of sieve.

Note that using 34/35LP, as we did on the C207, will require nearly 4e9 raw relations- these are the largest LP settings that don't need the extra CADO-compile flag set to handle more than 2^32 raw relations.
Okay, my 150 core-years was really 150 i5-8500-years and I know they're pretty fast for sieving, I don't know what Ryan uses. I'm willing to believe that I underestimated the number of required relations and 200 i5-8500-years was more like it. 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...

Last fiddled with by charybdis on 2021-08-23 at 23:53
charybdis 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 136 2021-10-21 16:17
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 18:53.


Sun Oct 24 18:53:02 UTC 2021 up 93 days, 13:22, 0 users, load averages: 0.82, 1.11, 1.18

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.