mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > CADO-NFS

Reply
 
Thread Tools
Old 2020-08-04, 05:03   #111
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

19×227 Posts
Default

I view mfb and lambda both as methods to control the amount of wasted cofactor-splitting. For reasons unclear to me, CADO runs quite a bit faster (in extensive testing at 100-140 digits) with mfb set well below 2*lpb. I've been using lambda as a sort of floating-point control for mfb, and on small numbers I have lots of runs where changing lambda by 0.01 does change the yield per Q but also the number of relations needed (in the direction that suggests the job is effectively a smaller LP choice). I found that using LP choices 1 or 2 bits higher than traditional choices but tight mfb led to faster factorizations.

I suppose I won't be too surprised if that doesn't work at this size; 31/32 is pretty much traditional for this size of job, so perhaps a tight mfb or tight lambda setting is overly restrictive.
VBCurtis is offline   Reply With Quote
Old 2020-08-09, 01:49   #112
charybdis
 
Apr 2020

3×31 Posts
Default

c180 results:
Poly score 9.842e-14, within 2% of the score for the last c179.
65.1M CPU-sec sieving for 321M raw relations, 225M unique.
TD=110 produced a 16.6M matrix.

mfb0=59 doesn't seem worth it to me. Yield and rel/sec improve a few percent but so does the number of relations needed to build a matrix. More importantly, 59 gives bigger matrices than 58; I'd guess something like 8-10% more unique relations are needed at 59 to build a matrix comparable to what you'd get at 58.

There's one more c180 on the HCN list that's unambiguously a GNFS job (there are a couple that are SNFS 261/2, I suspect SNFS will be slightly faster there?) so I'll run it with mfb0=58 and lambda0=1.93 - intermediate between the previously tried 1.88 and CADO-default 58/31+0.1=1.97 - unless anyone has a better suggestion.
charybdis is offline   Reply With Quote
Old 2020-08-09, 03:42   #113
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

19·227 Posts
Default

I think 1.93 is an excellent idea.
mfb0=59 should produce a slightly larger matrix than 58, since more of the relations will have a largest-bit large prime. Sieving a few more relations should overcome that, but if that makes the sieving take longer than an MFB=58 job then it's a waste.
VBCurtis is offline   Reply With Quote
Old 2020-08-15, 01:44   #114
charybdis
 
Apr 2020

3×31 Posts
Default

Stats for c180 with lambda0=1.93:

Poly score 9.285e-14.
70.2M CPU-seconds sieving for 322M raw relations, 218M unique.
TD=110 produced a 15.8M matrix.

Poly is ~7% worse than the c179 that I ran with default lambda0 of ~1.97. Sieving is ~6% slower per raw relation but ~8% slower per unique relation, and the matrix ended up a little bigger too.

I doubt the poly scores predict sieving speed to the nearest 1%, but lambda 1.93 performs noticeably better than 1.88 and within a percent or so of 1.97. Suggests that the default 1.97 is close enough to optimal here that it's not worth trying to narrow it down further?

Next GNFS target in the HCN list is a c182. I'll keep most of the sieving params the same to get a direct comparison - experimentation can wait till the bunch of c184s if I decide to do them - but should lims go a bit higher? 105M/145M?

Last fiddled with by charybdis on 2020-08-15 at 01:45
charybdis is offline   Reply With Quote
Old 2020-08-15, 02:15   #115
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

19·227 Posts
Default

Quote:
Originally Posted by charybdis View Post
I doubt the poly scores predict sieving speed to the nearest 1%, but lambda 1.93 performs noticeably better than 1.88 and within a percent or so of 1.97. Suggests that the default 1.97 is close enough to optimal here that it's not worth trying to narrow it down further?

Next GNFS target in the HCN list is a c182. I'll keep most of the sieving params the same to get a direct comparison - experimentation can wait till the bunch of c184s if I decide to do them - but should lims go a bit higher? 105M/145M?
If I were to do another test, I'd try mfb0=59 with a tighter lambda setting; but you've shown 59 is slower than 58, and with 58 that not specifying lambda is as fast as 1.93. Your params are simpler, and likely faster than trying to find a fastest-lambda with 59.

As for changing lims: larger lims will improve relations per Q and may improve uniques per raw relations ratio, but at the expense of a slightly larger matrix. The rule of thumb I've been using is to target an ending Q somewhere near lim1; so, if your C180 runs have ending Q near 130M, I'd add 10M to both lims for C182. I don't have theory to back this, and keeping lim smallish while running Q well above lim1 may be faster overall.
The larger the job, the more Q will exceed lim1; my rule of thumb has helped me in the 140-175 digit range.
VBCurtis is offline   Reply With Quote
Old 2020-08-15, 02:19   #116
charybdis
 
Apr 2020

5D16 Posts
Default

Quote:
Originally Posted by VBCurtis View Post
The rule of thumb I've been using is to target an ending Q somewhere near lim1; so, if your C180 runs have ending Q near 130M, I'd add 10M to both lims for C182.
The last c180 did indeed finish around 130M; the other numbers had slightly better polys and finished closer to 120M.
charybdis is offline   Reply With Quote
Old 2020-08-16, 01:14   #117
charybdis
 
Apr 2020

3·31 Posts
Default

Quote:
Originally Posted by charybdis View Post
A further trawl through the documentation reveals that a lambda of mfb/lpb + 0.1 is used if we leave it unspecified.
Despite what sieve/README.descent says ("in the first case, lambda defaults to mfb0/lpb0+0.1 as everywhere else in cado-nfs"), it looks like I was wrong, and presumably that readme file is outdated.

From sieve/las-norms.cpp:
Code:
    /* when lambda = 0 (automatic), we take mfb/lpb + 0.3, which is
       experimentally close to optimal in terms of seconds per relation
       (+ 0.2 might be even better on the rational side) */
    if (lambda == 0.0)
        lambda = 0.3 + (double) sc.sides[side].mfb /
            (double) sc.sides[side].lpb ;
So the default lambda0 for lpb0=31, mfb0=58 is actually 2.17 not 1.97. Probably worth trying ~2.05 on my next run then.

Last fiddled with by charybdis on 2020-08-16 at 01:21
charybdis is offline   Reply With Quote
Old 2020-08-23, 16:22   #118
charybdis
 
Apr 2020

3×31 Posts
Default

c182 stats:

Poly score 6.643e-14.
98.0M CPU-seconds sieving (Q 20M-181.4M) for 321M raw relations, 218M unique.
TD=110 produced a 17.8M matrix.

The parameters are still holding up fairly well at c182 if we assume that the poly score is inversely proportional to difficulty; I don't know whether this is a good assumption to make.
The matrix has got bigger, as expected.
Final Q was well beyond lim1 so maybe lims could be higher, but before trying that out I'm going to test lambda0=2.07.
charybdis is offline   Reply With Quote
Old 2020-09-01, 23:43   #119
charybdis
 
Apr 2020

3·31 Posts
Default

The c183 stats below aren't directly comparable to those for the c182 above, for a couple of reasons.
Firstly, I ran the c183 on a slightly different set of machines, giving about a 1% speedup in CPU-time.
Secondly, one machine had some strange connection problems. I won't bother with the details, but the lowdown is that the server cancelled all the WUs from this client without receiving any relations. This meant that the final Q was a bit larger than it should have been, but the factorization will only have been slowed down by a fraction of a percent.

Poly score 6.356e-14 (4.5% worse than c182 above).
Sieved Q from 20M to 195.9M, with about 1.7M missing due to the bad client.
100.5M CPU-seconds for 321M raw relations, 218M unique.
TD=110 produced an 18.3M matrix. This is a bit bigger than the c182 matrix, but the all the figures looked very similar to the c182 run in the early stages of filtering, so I'm going to chalk the difference in matrix size up to the peculiarities of the polynomial.

Putting all the figures together, lambda0 = 2.07 (= mfb0/lpb0 + 0.2) might be 1% faster than the default (mfb0/lpb0 + 0.3). It looks like changing lambda from the default is unlikely to produce big gains at this size.

Next up will be the bunch of c184s. Would I be right in thinking lpb 32/32 deserves some testing here?
charybdis is offline   Reply With Quote
Old 2020-09-02, 22:30   #120
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

19·227 Posts
Default

Sorry for the delay, been busy with some data-gathering for nfs@home queue planning.

A params.C185 file should have the usual 25-30% increase in lim's, and we should test 32/32 against the current setting.

If we stay with 31/32, I'd add another 20-30M relations wanted. 32/32 should be 30% higher than that to start with.

Poly select should be about double the C180 file- say, 60% increase in admax and 25% increase in P.

Edit: I'd also raise qmin to 25M or 30M. The most recent CADO-factorization paper mentions that controlling the qmax/qmin ratio helps to control the duplicate rate; so as our jobs get tougher and sieve up to larger Q's, qmin should rise as well. If I understood what they said properly (a weak assumption), a ratio of 7 is a decent target, and duplicate-rates get poor once the ratio exceeds 10. We saw that back when I suggested qmin of 500k, and their paper agrees with the data you gathered. We expect Q-max of 175-200M, I think?

Last fiddled with by VBCurtis on 2020-09-02 at 22:56
VBCurtis is offline   Reply With Quote
Old 2020-09-02, 23:07   #121
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

10D916 Posts
Default

I decided to copy the params from a few posts up and make the changes I just recommended. Simpler this way. Also, I changed ncurves0 to 25 from 20.
Draft params.c185:
Code:
tasks.I = 15
tasks.qmin = 30000000
tasks.lim0 = 125000000
tasks.lim1 = 175000000
tasks.lpb0 = 32
tasks.lpb1 = 32
tasks.sieve.mfb0 = 60 #maybe 59?
tasks.sieve.mfb1 = 90 #maybe 91 to improve yield?
tasks.sieve.ncurves0 = 25
tasks.sieve.ncurves1 = 13
rels wanted = 340000000

Here's the poly-select settings:
Code:
tasks.polyselect.P = 3000000
tasks.polyselect.admin = 2e4
tasks.polyselect.admax = 35e5
tasks.polyselect.adrange = 1680
tasks.polyselect.incr = 210
tasks.polyselect.nq = 15625
tasks.polyselect.nrkeep = 120 
tasks.polyselect.ropteffort = 35
VBCurtis is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Integers congruent to last two decimal digits mod 23 enzocreti enzocreti 1 2020-03-03 18:38
Twin Primes with 128 Decimal Digits tuckerkao Miscellaneous Math 2 2020-02-16 06:23
Playing with decimal representation Nick Puzzles 9 2013-02-13 17:17
Decimal Value of Mersenne Prime vsuite GPU Computing 11 2011-02-02 04:47
Decimal Places Corbyguy Software 3 2008-06-09 18:09

All times are UTC. The time now is 01:25.

Tue Sep 22 01:25:37 UTC 2020 up 11 days, 22:36, 0 users, load averages: 1.29, 1.54, 1.62

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.