Very bad best-polynomial
 

A simple 'msieve -v -np 3358323032880372693143301502113331747565332737371006633015167519465812493720372585783051724897778685785848677' gives me a polynomial with
Wed Dec 17 23:01:22 2008 skew 64524.95, size 4.186314e-11, alpha -5.331026, combined = 2.475010e-10

which translates to ggnfs format as
[code]
n: 3358323032880372693143301502113331747565332737371006633015167519465812493720372585783051724897778685785848677
skew: 64524.95
Y0: -1411222728902026506433
Y1: 148807419971
c0: -868711284839411933038070832
c1: 23758183715177455719012
c2: 624286663027613216
c3: -11397252686095
c4: -86404576
c5: 600
type: gnfs
alim: 3200000
rlim: 3200000
lbpr: 27
lbpa: 27
mfbr: 54
mfba: 54
rlambda: 2.6
alambda: 2.6
[/code]

A few minutes with the GNFS polynomial selector gets me
[code]
n: 3358323032880372693143301502113331747565332737371006633015167519465812493720372585783051724897778685785848677
skew: 83663.30
# norm 2.12e+15
c5: 1080
c4: 862054902
c3: -28640400300919
c2: -5581482305346264623
c1: 23643249351648318166735
c0: 5094331293658883687679374825
# alpha -5.81
Y1: 208389411449
Y0: -1254666285515209326636
# Murphy_E 9.80e-10
# M 358576645929895826768194746682251522272972273829396424258748912720724782748344700120221675041459567221738673
type: gnfs
rlim: 3200000
alim: 3200000
lpbr: 27
lpba: 27
mfbr: 54
mfba: 54
rlambda: 2.6
alambda: 2.6
[/code]

But
[code]
/home/nfsworld/64bit_new/gnfs-lasieve4I12e -a msieve.poly -f 3200000 -c 1000
total yield: 146, q=3201007 (0.24219 sec/rel)
/home/nfsworld/64bit_new/gnfs-lasieve4I12e -a gnfs.poly -f 3200000 -c 1000
total yield: 9168, q=3201007 (0.00395 sec/rel)
[/code]

so the ggnfs tools have produced a polynomial about sixty times as good. I feel this is almost at the point of being a bug in the polynomial-assessment code, particularly since I've had msieve produce me some very good polynomials in the past.

(and, indeed, if I pick the best-alpha polynomial in the msieve.dat.p file, which is
[code]
# norm 2.331e+15 alpha -6.801395 skew 42631.87 e 2.113e-10
R0 -913468754412252477889
R1 178400848403
A0 -2023049826680594598977978748
A1 -76221025284510540482388
A2 175525284744444029
A3 11542556260238
A4 1248902864
A5 5280
[/code]
I get total yield: 8104, q=3201007 (0.00357 sec/rel)

Those times are very strange; the Murphy E code that I'm writing assigns an E value of 1.25e-9 to the msieve polynomial chosen, which is fully 27% better than the polynomial found by pol5. The msieve polynomial with the higher alpha has an E of only 1.1e-9, which is still higher than the pol5 choice, in approximately the ratio of the sieving times. My E code also agrees with the pol5 code for the GGNFS polynomial.

As Serge points out, the computation of E assumes that the factor base bounds and sieve area are specified, but GGNFS chooses different values for the actual sieving and for a C109 they are much smaller than the default parameters to the E computation. Also, the size score given by the current msieve version completely ignores translation and skewness of the polynomial; optimal values of these are computed via very clumsy means right now, after the size score indicates a good polynomial.

Please call me nine sorts of incompetent and tell me not to attempt to report subtle bugs after midnight; if you spell 'lpbr' as 'lbpr', the gnfs-lasieve4I12e program does not complain [i]but doesn't use large primes either[/i].

Could someone with commit access to GGNFS add a check for unrecognised A: B lines in the input parser?

[quote=fivemack;153847]Could someone with commit access to GGNFS add a check for unrecognised A: B lines in the input parser?[/quote]
Ok.
(...when I will be adding the -resume option...)

gnfs-lasieve4I14e -R
 

Ok. It's there (the sanity checks for the "lbpr" in the polynomial took several clumsy efforts to fix - versions 326, 327). Now, the resume option is in SVN [URL="http://ggnfs.svn.sourceforge.net/viewvc/ggnfs/trunk/src/lasieve4/gnfs-lasieve4e.c?r1=327&r2=328&pathrev=328"]version 328[/URL]. Please feel free to criticise.

The last relation line after a crash is often incomplete; I chose the least evil -- to add the endline after it. If the computer crashed (or you had to kill your process) all you now have to do is repeat the last command-line with added [B]-R[/B] option. I also added the denial of overwriting of an existing relations file...



[SIZE=1]P.S. On a second thought, watch out, your perl scripts might start bailing out. I think it is better to solemnly remove the "spairs.out" file by the perl script, than have a million rels erased by overwriting a file, when one is not careful... Apparently both things can happen. Those who use the perl scripts and don't know how to modify them - be damned. Sorry! :-) Learn perl!![/SIZE]

c135 - search range to high?
 

[QUOTE=Andi47;151102]I used 1.39 beta 2 to search for a poly for a [URL="http://mersennewiki.org/index.php/Base_10_Still_Open#HP548"]c136[/URL].....[/QUOTE]

The same as in my previous post, now for a [URL="http://mersennewiki.org/index.php/Base_10_Still_Open#HP548"]c135[/URL]: While one cpu of my Core2Duo was searching in the default range with msieve 1.39, the other one searched (with 1.39 too) from 1 upwards.

I got:

Poly #1, from the default range:

[code]n: 761102591343141130528734642782311280444504698188990752294818515177510480387765034971481816355403513713187530601982347688992389537498069
Y0 -98849402606734405519591518
Y1 1030641617930699
c0 -70398717449201429374085022202701305
c1 383062608256024444591653325702
c2 -377982730031082041008189
c3 -398992525424165632
c4 399578501904
c5 80640
skew: 1062985.67
# size 3.074325e-014, alpha -8.239577, combined = 4.792375e-013
rlim: 8000000
alim: 8000000
lpbr: 28
lpba: 28
rlambda: 2.55
alambda: 2.55
mfbr: 52
mfba: 52[/code]

Poly #2 (from the lower range):

[code]n: 761102591343141130528734642782311280444504698188990752294818515177510480387765034971481816355403513713187530601982347688992389537498069
Y0 -119709566397229356809815710
Y1 816398599490551
c0 9977520772231914172799523496170929
c1 60276799573547959982893215099
c2 -705506867921235653659
c3 -200379365107047219
c4 -21323879230
c5 30960
skew: 689634.49
# size 4.209382e-014, alpha -7.413720, combined = 4.982693e-013
rlim: 8000000
alim: 8000000
lpbr: 28
lpba: 28
rlambda: 2.55
alambda: 2.55
mfbr: 52
mfba: 52[/code]

In a search range (with gnfs-lasieve4I14e) from 8M to 8M+5000 I get:

Poly #1: yield 15801
Poly #2: yield 17995

So I think the search range is possibly a bit too high - or it definitively pays off to search a bit more for factorizations >c130

I'm contemplating the next job for the assembled hordes of sievers. I would be interested in 109!+1 which is a 177-digit GNFS. Is it likely that, if I do 10^263-1 first (ETA a couple of months), msieve will have reached the stage at which it can sensibly be used for polynomial selection for so large a number?

A few months should be enough time to soup up the code for the job. I've spent a bunch of time on the pol51opt-like part of the code and have implemented Murphy's scoring algorithm, so the next version will produce E values which are directly comparable to what GGNFS produces.

Still, I don't think everyone should risk pouring so much time into a choice made by unvetted code. Perhaps everyone would consider running msieve and pol5 in equal measure when selecting polynomials for very large jobs? Or use msieve for small A5 and pol5 for large A5? I can also port the stage 2 optimizations back into pol5 to put the two codes on a more even footing.

Actually, the big obstacle with poly selection for larger jobs is that nobody seems to have reliable parameters for factorizations > C155.

These parameters seem to fit a straight line easily. (The conventional ones at the low end, the best known params for the C180, C165, C160, multiple C156s are in the forum - at the top end). The top end of course is more implortant, but the low end is well established and tested.

[SIZE=1]A bit off-topic, or maybe not: I am running now a selection for a meager C146 (which is the only clear GNFS in homogeneous Cunnignams) - and it turned out to be an interesting excercise because it is right on the projected -p change from 6 to 7, so I am running both values for pol51. Of course -p 7 flies over X5s more than ten times faster, but both found over a night+day a few comparable polynomials. And I will run msieve's select, as well. Do you have (internally) and equivalent of the -p parameter? Then the result could be of interest. (I am far from done, but I will PM you later.) I remember that Tom used two values of -p in searches for the C180, too. So that is a good data point to know...[/SIZE]

Msieve's poly selection doesn't need an equivalent to -p. This specifies the number of 'special' factors in the leading rational coefficient, and Kleinjung's improved algorithm doesn't care whether factors are 'special' or not.

What parameters does your current algorithm need? With the two-stage one pol51m0b+pol51opt, pol51m0b needed one parameter which you tuned adaptively (I aimed for about one output line every ten seconds), and pol51opt needed two which I just searched for without much guidance keeping the ratio roughly right.

The Murphy-E score for the GNFS jobs I've done has generally fitted very nicely as

ln(score*10^12) = 21.335 - 0.131*log_10(N)

and so I've tended to run large polynomial-selection jobs until I get something of that score or above, and then for as long again in the hope of doing better.