mersenneforum.org Reserved for MF - Sequence 4788
 Register FAQ Search Today's Posts Mark Forums Read

 2021-08-23, 12:23 #3048 charybdis     Apr 2020 1F316 Posts 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.
2021-08-23, 12:36   #3049
EdH

"Ed Hall"
Dec 2009

4,003 Posts

Quote:
 Originally Posted by charybdis . . . 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.

2021-08-23, 12:49   #3050
charybdis

Apr 2020

499 Posts

Quote:
 Originally Posted by EdH 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.

 2021-08-23, 13:40 #3051 swellman     Jun 2012 3,203 Posts 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.
2021-08-23, 14:03   #3052
Gimarel

Apr 2010

23×23 Posts

Quote:
 Originally Posted by charybdis 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.

2021-08-23, 17:13   #3053
charybdis

Apr 2020

499 Posts

Quote:
 Originally Posted by Gimarel 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.

2021-08-23, 17:32   #3054
bur

Aug 2020
79*6581e-4;3*2539e-3

18F16 Posts

Quote:
 Originally Posted by charybdis 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?

2021-08-23, 18:57   #3055
charybdis

Apr 2020

499 Posts

Quote:
 Originally Posted by bur 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.

2021-08-23, 20:09   #3056
ryanp

Jun 2012
Boulder, CO

1010000112 Posts

Quote:
 Originally Posted by charybdis 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.

2021-08-23, 21:42   #3057
VBCurtis

"Curtis"
Feb 2005
Riverside, CA

22×1,249 Posts

Quote:
 Originally Posted by ryanp 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

2021-08-23, 23:44   #3058
charybdis

Apr 2020

499 Posts

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

Quote:
 Originally Posted by VBCurtis 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

 Similar Threads Thread Thread Starter Forum Replies Last Post kar_bon Aliquot Sequences 133 2021-10-16 17:21 RichD Aliquot Sequences 476 2021-10-04 20:47 RichD Aliquot Sequences 524 2021-09-06 21:00 prism019 GPU to 72 6 2020-09-21 22:11 petrw1 Lone Mersenne Hunters 82 2010-01-11 01:57

All times are UTC. The time now is 06:36.

Thu Oct 21 06:36:12 UTC 2021 up 90 days, 1:05, 1 user, load averages: 1.69, 1.20, 1.06