mersenneforum.org > YAFU yafu-1.33
 Register FAQ Search Today's Posts Mark Forums Read

 2012-10-25, 22:58 #1 bsquared     "Ben" Feb 2007 361710 Posts yafu-1.33 Now available. Mostly "user experience" updates and bug fixes, but enough of them to warrant a new version. Happy factoring!
 2012-10-26, 00:34 #2 kar_bon     Mar 2006 Germany 1011100010002 Posts The zip-file is not readable.
 2012-10-26, 01:03 #3 bsquared     "Ben" Feb 2007 361710 Posts Things acted a bit funny when I first uploaded it. I re-uploaded, so try it again. thanks.
 2012-11-07, 03:29 #4 swellman     Jun 2012 66718 Posts SNFS # of relations? When "type: SNFS" is added to the nfs.job file, the estimated required number of relations seems higher than I had been led to expect from SNFS. What's the formula for this estimate? Also the # rels/spec_q ratio for my poly drops horribly when changing type from GNFS to SNFS (and the estimated time goes up), despite the usual rule of thumb recommending use of SNFS for my composite. Didn't expect that. Maybe I'm comparing apples and oranges here...
2012-11-07, 03:40   #5
Dubslow

"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3×29×83 Posts

Quote:
 Originally Posted by swellman When "type: SNFS" is added to the nfs.job file, the estimated required number of relations seems higher than I had been led to expect from SNFS.
It's case sensitive, and I've seen lowercase from most examples, so that's what YAFU looks for. Thus, it doesn't see the type is SNFS, and the minrels estimate is for a GNFS job of that size, which is why it's so high.
Quote:
 Originally Posted by swellman What's the formula for this estimate?
Code:
(2*fudge * (pow(2.0,(double)lpb) / log(pow(2.0,(double)lpb))))
...where fudge also depends on lpb and is given by a table in the source.
Code:
case 27:
fudge = 0.70;
break;
case 28:
fudge = 0.76;
break;
case 29:
fudge = 0.84;
break;
case 30:
fudge = 0.89;
break;
case 31:
fudge = 0.91;
break;
Quote:
 Originally Posted by swellman Also the # rels/spec_q ratio for my poly drops horribly when changing type from GNFS to SNFS (and the estimated time goes up), despite the usual rule of thumb recommending use of SNFS for my composite. Didn't expect that. Maybe I'm comparing apples and oranges here...
Perhaps with your poly, sieving on the algebraic side is better...? (YAFU doesn't affect what the siever does other than tell it which side to sieve on.)

Last fiddled with by Dubslow on 2012-11-07 at 03:41 Reason: 2*fudge

 2012-11-07, 03:50 #6 swellman     Jun 2012 351310 Posts I use snfs in my poly (and Yafu recognizes it as such). It was just all caps here due to my silly iPhone autocorrect. Will post my example tomorrow to show specifics. Thanks for the formula.
2012-11-07, 04:00   #7
Dubslow

"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3·29·83 Posts

Quote:
 Originally Posted by swellman I use snfs in my poly (and Yafu recognizes it as such). It was just all caps here due to my silly iPhone autocorrect. Will post my example tomorrow to show specifics. Thanks for the formula.
When you first started YAFU with this job, did you have all the job parameters selected and in the file, or did you let YAFU fill them in? If the type was wrong the first time (even if it's correct now), then the parameters chosen would be horribly wrong. In any case, I look forward to the specifics, since it's apparently my code that's derping. (I might need help with figuring out if all the params are decent...)

Actually, do you have the "size: 190" (or whatever) in your job file? If you don't, YAFU assumes the SNFS difficulty is the size of the n: in the job file, and if there are other known factors those two sizes could be significantly different.

2012-11-07, 21:01   #8
swellman

Jun 2012

3·1,171 Posts

Quote:
 Originally Posted by Dubslow When you first started YAFU with this job, did you have all the job parameters selected and in the file, or did you let YAFU fill them in? If the type was wrong the first time (even if it's correct now), then the parameters chosen would be horribly wrong. In any case, I look forward to the specifics, since it's apparently my code that's derping. (I might need help with figuring out if all the params are decent...) Actually, do you have the "size: 190" (or whatever) in your job file? If you don't, YAFU assumes the SNFS difficulty is the size of the n: in the job file, and if there are other known factors those two sizes could be significantly different.
I did not have "size:" in my nfs.job file. Once I corrected this, a lot of my issues/confusion went away. Suggest use of "size" and "type" by SNFS within Yafu be more thoroughly documented - I can find nothing in the current docfile.txt (nor the ggnfs and mseive documentation).

As to estimating the number of relations required for SNFS, I had been using models from Kamada's site. For SNFS, they use

4*10^(d/70+4)

where d is the SNFS difficulty. The other parameters for a poly file are also modeled on that page, presumably based on successful factorizations. Anybody have a feel for how accurate the Kamada models are?

2012-11-07, 21:59   #9
Dubslow

"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

722110 Posts

Quote:
 Originally Posted by swellman I did not have "size:" in my nfs.job file. Once I corrected this, a lot of my issues/confusion went away. Suggest use of "size" and "type" by SNFS within Yafu be more thoroughly documented - I can find nothing in the current docfile.txt (nor the ggnfs and mseive documentation).
Sorry. That's because these are features I added myself last month, and it didn't occur to anyone to add it to the docfile. (I don't have write access to SVN either.) I'll write up a few notes and send them to b2. In the meantime, the bottom part of this post is the closest there is to documentation.
Quote:
 Originally Posted by swellman As to estimating the number of relations required for SNFS, I had been using models from Kamada's site. For SNFS, they use 4*10^(d/70+4) where d is the SNFS difficulty. The other parameters for a poly file are also modeled on that page, presumably based on successful factorizations. Anybody have a feel for how accurate the Kamada models are?
Neat! I recognize some of the names, so the figures are probably pretty accurate; for the estimation in YAFU, the rels required are nominally pi(rlim/alim)+1, but the large prime method makes the required rels non-deterministic, though it still depends almost entirely on what lpb is, with some dependence on *lim. The formula I quoted above is related to the density of the primes, though I'm not sure of the details (others can fill in them in; in any case, note that the formula above is the asymptotic approximation of pi(2^lpb), as given in the second link). (Edit: mfb also plays a role in it, or more specifically, the ratio mfb/lpb plays a role.)

As for the regression you quote, that's due to the fact that the choice of lpb is pretty well understood (read: consistent) for difficulties <= ~250 (and in turn the min_rels estimate is consistent).

Last fiddled with by Dubslow on 2012-11-07 at 22:04

 2012-11-07, 22:59 #10 swellman     Jun 2012 DB916 Posts Example Posting my example, which still has an odd warning message about ignoring the size parameter, even though Yafu appears to use it. But with the size parameter in place, things seem much better. Composite is C163_145_33 from the xyyx project. It has a SNFS difficulty of 221. My poly is as follows Code: n: 8044748335384450433189067533289903349948378898702376138454639872609531665263335556364761169996899460279132119953474639118706796845849163688530204021522714077427337 type: snfs size: 221 skew: 19.81 c0: 3048625 c5: 1 Y0: -108869005682301795684211705446369982097742753 Y1: 9294114390625 rlim: 34000000 alim: 34000000 lpbr: 29 lpba: 29 mfbr: 58 mfba: 58 rlambda: 2.600000 alambda: 2.600000 Executing Yafu on the rational side results in Code: c:>yafu "nfs(8044748335384450 43318906753328990334994837889870237613845463987260953166526333555636476116999689 9460279132119953474639118706796845849163688530204021522714077427337)" -v -r -R - ns 15000000,15001000 11/07/12 17:37:10 v1.33 @ NATINB84202, System/Build Info: Using GMP-ECM 6.3, Powered by GMP 5.0.1 detected Intel(R) Core(TM)2 Duo CPU P8700 @ 2.53GHz detected L1 = 32768 bytes, L2 = 3145728 bytes, CL = 64 bytes measured cpu frequency ~= 2419.123890 using 20 random witnesses for Rabin-Miller PRP checks =============================================================== ======= Welcome to YAFU (Yet Another Factoring Utility) ======= ======= bbuhrow@gmail.com ======= ======= Type help at any time, or quit to quit ======= =============================================================== cached 78498 primes. pmax = 999983 >> nfs: checking for job file - nfs: number in job file matches input nfs: checking for data file nfs: no data file found nfs: commencing nfs on c163: 804474833538445043318906753328990334994837889870237 61384546398726095316652633355563647611699968994602791321199534746391187067968458 49163688530204021522714077427337 nfs: found type: snfs nfs: found size: 221 nfs: parsed lpbr = 29, lpba = 29, type = snfs, setting lpb = 29 nfs: guessing snfs difficulty 221 is roughly equal to gnfs difficulty 153 nfs: continuing with sieving at user specified special-q 15000000 nfs: commencing rational side lattice sieving over range: 15000500 - 15001000 nfs: commencing rational side lattice sieving over range: 15000000 - 15000500 Warning: Ignoring input line: size: 221 Warning: Ignoring input line: size: 221 Warning: lowering FB_bound to 15000499. Warning: lowering FB_bound to 14999999. total yield: 1057, q=15001001 (0.32842 sec/rel) total yield: 1073, q=15000509 (0.34927 sec/rel) found 2130 relations, need at least 44869960 (filtering ETA: 2263h 37m), continu ing with sieving ... ***factors found*** ***co-factor*** C163 = 8044748335384450433189067533289903349948378898702376138454639872609531665 26333555636476116999689946027913211995347463911870679684584916368853020402152271 4077427337 ans = 80447483353844504331890675332899033499483788987023761384546398726095316652 63335556364761169996899460279132119953474639118706796845849163688530204021522714 077427337
2012-11-07, 23:45   #11
Dubslow

"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3·29·83 Posts

Quote:
 Originally Posted by swellman Posting my example, which still has an odd warning message about ignoring the size parameter, even though Yafu appears to use it.
That's because the warning is printed by GGNFS' lasieve, not by YAFU.

 Similar Threads Thread Thread Starter Forum Replies Last Post bsquared YAFU 1276 2019-01-12 04:46 EdH YAFU 8 2018-03-14 17:22 bsquared YAFU 119 2015-11-05 16:24 storflyt32 YAFU 2 2015-06-29 05:19 bsquared YAFU 21 2012-09-04 19:44

All times are UTC. The time now is 20:10.

Sat May 28 20:10:33 UTC 2022 up 44 days, 18:11, 0 users, load averages: 1.03, 1.18, 1.32