Some results from a live GNFS180 polsel
 

frmky and I have done the polynomial selection for EM43; c5 = 0 through 110000, on four GPUs (my GTX275 and three-quarters of frmky's Tesla S1070). It took about six GPU-weeks.

I think the Murphy_E bound somewhere around 2.7e-14 at 180 digits is significantly too low - we got about ten million polynomials in that range, and wouldn't have complained (although it would have taken several days to see the first polynomial) to get only the ones with E>4.0e-14, or even 4.5e-14. I'm the only person who can be blamed about this, since I set the bound in the first place, but I think it would be better to put it a bit higher.

I don't know how to go about shifting the stage-1 and stage-2 bounds in the face of evidence; is it possible to determine from a final polynomial what its scores at stage-1 and stage-2 were, or do I have to instrument msieve-gpu and run another large polsel? I suppose I can easily run 110k to 150k, it'll slow down the 2-941 linalg but not by all that much, and if we get an unexpectedly good polynomial before EM43 tasks start getting handed out, it's probably easy to change.

For a few highly productive c5's, stage 2 ran for over 10 hours leaving the GPU idle. What probably should have been a 4-5 day run took nearly 8 days.

Raising the target E value and lowering the initial stage 2 norm will make the root sieve run much faster. It sounds like at a minimum stages 1 and 2 should run in separate threads; see the GPU thread for some musings on that.

PS: What do the best polynomials look like? Serge reported some experiments where the reported E value only weakly predicted how well a polynomial would find relations, and that a pol5 polynomial with a much better E value sieved significantly worse. Especially when a search produces hundreds of 'best' polynomials, maybe we should customize the factor base bounds in the E-value computation for the size of the polynomials, instead of using the same values all the time. We wouldn't be able to compare with pol5 anymore, but could probably sieve more effectively.

So what was the final best Murphy E?

And try "my" new (hopefully useful) formula to find an equivalent SNFS digit difficulty (fitted from a couple dozen jobs):

SNFS_equivalent_difficulty = -30 log[sub][SIZE=1]10[/SIZE][/sub]E - 128

What is your equivalent SNFS difficulty?
(For B+D gnfs-180, 2,2254L, a poly with 6.41e-14 suggests ~= snfs-268.
Msieve_144gpu, sadly, didn't produce any polys and died. 6.41e-14 is the pol51 poly.)

_____
[SIZE=1]I have finally figured out for myself what Murphy E means. It is proportional to the inverse of the total project sieving time. On the same machine or a cluster, a job with E=6e-14 will take fairly exactly 10x more time than a job with E=6e-13 and a 100x more time than a job with E=6e-12. [/SIZE]
[SIZE=1][/SIZE]
[SIZE=1]I'll write a separate thing about the quintics, quartics etc.: this measure helps to quantify the proverbial suboptimal-degree penalty.[/SIZE]

Technically the E value is the probability that one sieve value will be smooth, given the sieving area and the factor base bounds. That probability goes up with increasing factor base bounds, and may go up or down as the sieving area increases. Both pol5 and msieve fix all of those parameters, so that E values across factorizations are all directly comparable.

tangential Re: posts #3 and #5.

Actually, [FONT=Courier New]pol51opt[/FONT] has hidden -f, -F, -A parameters which (if supplied and roughly correspond to the future sieving use) affect the E value towards incomparability (cf. post #5) _[I]but[/I]_ the output polynomials eventually sieve better in real life, indeed!

I have more than once used these for the final polishing of the best candidates: for that, you put a few "*.51.m" lines that were the parents of the better initial offspring and repeat the [FONT=Courier New]pol51opt[/FONT] with somewhat increased search space plus the increased real-life -f, -F, -A values. This is similar to the suggested course in #3.

The poly is
[CODE]# norm 9.833432e-18 alpha -9.052498 e 6.697e-14
skew: 536967657.44
c0: 486705885709926708065232033951307588813625602275
c1: 5584390886742987582391695130327092942465
c2: -2589293749660254385400621955533
c3: -205785074447711087191729
c4: -211349858750
c5: 101640
Y0: -77187904731145180346916804885190882
Y1: 27609235740881943367
n: 278490841076279407188741439481565179355926725853710201632331620642982062389901741890579963524423782637435949041666525000702723914662388812510545494307250950777886431051612811386531
[/CODE]
so your formula gives 267.2 for a GNFS of 179.4 digits.

That's a great one. ...And look at that alpha! :shock:
(and you probably had even larger abs-value alphas!)


Could you please run (just for a day) our number?
It was posted [URL="http://mersenneforum.org/showthread.php?p=195887#post195887"]here[/URL].

(you will observe that [I]p[/I] and [I]q[/I] are almost but just shy of 32-bit in size and resultant is 63.4 bits in size... some tricky carryovers crept in?)

Is that a record alpha?

Some of the Bochum slides make it sound like spectacular alpha values like that would be common if you pour a great deal of effort into stage 2, and the input is very large so a big search space is available.

That actually was the best alpha as well. The five best alphas were
[CODE]# norm 9.833432e-18 alpha -9.052498 e 6.697e-14
# norm 9.443674e-18 alpha -8.816673 e 6.512e-14
# norm 9.033319e-18 alpha -8.728573 e 6.310e-14
# norm 8.474841e-18 alpha -8.636510 e 5.865e-14
# norm 8.823795e-18 alpha -8.603598 e 6.228e-14
[/CODE]
and the best E's were
[CODE]# norm 9.833432e-18 alpha -9.052498 e 6.697e-14
# norm 9.443674e-18 alpha -8.816673 e 6.512e-14
# norm 9.033319e-18 alpha -8.728573 e 6.310e-14
# norm 8.823795e-18 alpha -8.603598 e 6.228e-14
# norm 9.606499e-18 alpha -7.836603 e 6.225e-14
[/CODE]
Note the significant overlap. All 6 of these polys were found at c5 of 101640.
[QUOTE=Batalov;197966]
Could you please run (just for a day) our number?
It was posted [URL="http://mersenneforum.org/showthread.php?p=195887#post195887"]here[/URL].
[/QUOTE]
Sure.

Thanks. Because sometimes...

[QUOTE=frmky;197965]The poly is
...[/QUOTE]

I just did a test run (Core 2 Duo @ 2.0 GHz, 64-bit-Linux):

[CODE]# norm 9.833432e-18 alpha -9.052498 e 6.697e-14
n: 278490841076279407188741439481565179355926725853710201632331620642982062389901741890579963524423782637435949041666525000702723914662388812510545494307250950777886431051612811386531
skew: 536967657.44
c0: 486705885709926708065232033951307588813625602275
c1: 5584390886742987582391695130327092942465
c2: -2589293749660254385400621955533
c3: -205785074447711087191729
c4: -211349858750
c5: 101640
Y0: -77187904731145180346916804885190882
Y1: 27609235740881943367
rlim: 130000000
alim: 130000000
lpbr: 31
lpba: 31
mfbr: 62
mfba: 62
rlambda: 2.6
alambda: 2.6
# Parameters not optimized![/CODE]

./gnfs-lasieve4I15e -a em43.poly -o em43_test1.out -f 60000000 -c 5000
Warning: lowering FB_bound to 59999999.
[COLOR="Blue"]total yield: 4645, q=60005047 (1.06234 sec/rel)[/COLOR]

[QUOTE=Batalov;197973]Thanks. Because sometimes...[/QUOTE]

I suppose the result of that is:

[QUOTE=Batalov;197966]
Could you please run (just for a day) our number?
It was posted [URL="http://mersenneforum.org/showthread.php?p=195887#post195887"]here[/URL].
[/QUOTE]
Here's the best from a 1 day (4 GPU-day) run:

[CODE]# norm 6.382388e-18 alpha -6.977213 e 4.690e-14
skew: 96396127.95
c0: -21089523035205834558658893161383589790490875
c1: 25365708430996095210154238905975753526
c2: -72843247438343083950607872141
c3: -286810051133678582204076
c4: 1191598470970
c5: 75300
Y0: -104562293217428138402097394839773048
Y1: 30927533733738342637

# norm 6.052477e-18 alpha -7.456015 e 4.572e-14
skew: 71177217.42
c0: -176168744305195828043372966990512601113397184
c1: -48474401617643499835075365201872549504
c2: 63762059797096003748769347572
c3: 446546902426598975662414
c4: -125855215039143
c5: 60120
Y0: -109378093201325720088775462145703197
Y1: 28451743180686818239
[/CODE]

Thanks, Greg (and Jason, in the GPU thread) -- that's good enough.
(I have a 6.3e-14 poly from pol51, anyway.)
Then it was the old card that was the problem, not the code.

[QUOTE=jasonp;197955]Technically the E value is the probability that one sieve value will be smooth, given the sieving area and the factor base bounds. That probability goes up with increasing factor base bounds, and may go up or down as the sieving area increases. Both pol5 and msieve fix all of those parameters, so that E values across factorizations are all directly comparable.[/QUOTE]

Are you talking about these values?:

[code] const double rfb_limit = 5000000;
const double afb_limit = 10000000;
const double sieve_area = 1e16;[/code]
Besides becoming incompatible with pol5, is there danger in raising these limits unconditionally? Say, would raising them make the score [i]less[/i] accurate for smaller numbers? Please forgive my ignorance.

Those three are what we're referring to.

The numbers are already used for inputs that are much smaller than would be appropriate if you actually used those values for the sieving, so I doubt it makes much difference.

In fact it might be cool to try to optimize those three at the same time that translation and skew are optimized, in the last part of stage 2; but I doubt that would work, because the E value would never drop as a result of a larger factor base. You'd need to add another term into the objective function that quantified the runtime of a siever, maybe by multiplying the E value by the number of relations needed and the time to find one relation. In that case the objective function becomes the total sieving time, which is really what we want to minimize, but now we're not dealing with a continuous function anymore.

[QUOTE=jasonp;199526]Those three are what we're referring to.

The numbers are already used for inputs that are much smaller than would be appropriate if you actually used those values for the sieving, so I doubt it makes much difference.

In fact it might be cool to try to optimize those three at the same time that translation and skew are optimized, in the last part of stage 2; but I doubt that would work, because the E value would never drop as a result of a larger factor base. You'd need to add another term into the objective function that quantified the runtime of a siever, maybe by multiplying the E value by the number of relations needed and the time to find one relation. In that case the objective function becomes the total sieving time, which is really what we want to minimize, but now we're not dealing with a continuous function anymore.[/QUOTE]

I take it then that the final norm limit needs to be raised as well if the afb/rfb limit is increased. Quickly testing a c110 shows that increasing afb/rfb to 1e8 causes the 'e' score to be multiplied (vs using default alim/rlim) on average by about a factor of 91, and for a c129, about 152.

Is there a quick way to estimate how much to adjust the final norm limit for a given input size if afb/rfb are multiplied by fixed constant?

[QUOTE=jrk;199540]Quickly testing a c110 shows that increasing afb/rfb to 1e8 causes the 'e' score to be multiplied (vs using default alim/rlim) on average by about a factor of 91, and for a c129, about 152.[/QUOTE]
And for a c151, about 330. So it is not a log scale factor w.r.t. input length.

Looks like the factor that is needed to scale the 'e' cutoff when afb/rfb are increased to 1e8 fits nicely to this curve:

3.15 * exp(0.0134 * log(N))

(for degree 5 at least, did not check degree 4 or 6)

Later tonight I will re-test some polys using the new score and see if they are ordered more accurately (according to their sieving speed).

It turns out that scaling the 'e' cutoff by the factor written above does not work as expected. No polynomials are found then, even though polys scoring higher than the scaled cutoff can be found otherwise

(e.g. there is a 3.17e-10 with the new scoring but it isn't found when the cutoff is 2.69e-10). Something else is happening. Perhaps no scaling is needed at all, then?

There isn't any simple relationship between the parameters and the E value; the parameters act to scale the argument to Dickman's function, which is integrated over the sieving region.