Fast Breeding (guru management)

[swellman]

Originally Posted by jyb

So are there any guesses as to what confidence we should have that these really are the best polynomials? (Where by "best" I really mean "within a few percent of the best".)

As you can maybe tell, I'm a little disturbed that Yafu would choose such a non-obvious polynomial that turns out to be clearly worse than the obvious one. It would be a shame if it's doing that routinely and we're wasting 15% of our computing resources during sieving.

You raise a good point - how good are the polynomials produced by Yafu? I will counter that sometimes (anecdotally) the obvious polynomial is not always the best performing as measured by test sieving. Yafu uses brute force to evaluate dozens of polynomials quickly - many that no human would bother to consider - but then it does run some test sieving to fine tune the results. (Test sieving has its limitations too of course.)

Not sure there's an easy way to define the quality of Yafu's results. Compare it's results against the "obvious" one or two SNFS polynomials? Yafu often produces the obvious polynomial. Only use hand calculated results? Sometimes the odd looking poly spit out of Yafu will beat these. How would we know other than laborious test sieving? Which is what Yafu does...

Certainly some of the rules of thumb apply here - look for a small leading coefficient (1 being best), keep things simple, etc. Maybe there's a latent problem here that is now noticeable with higher SNFS difficulties?

I'll throw in one more piece of anecdotal/worthless data - over the past couple of years, a few Yafu polys I've posted have been questioned but none of the suggestions could beat the Yafu results, well until now.

[axn]

Originally Posted by swellman

I'll throw in one more piece of anecdotal/worthless data - over the past couple of years, a few Yafu polys I've posted have been questioned but none of the suggestions could beat the Yafu results, well until now.

Are there logs from the run? Is it possible to find out if YAFU even considered the simple poly?

[jyb]

Originally Posted by swellman

You raise a good point - how good are the polynomials produced by Yafu? I will counter that sometimes (anecdotally) the obvious polynomial is not always the best performing as measured by test sieving. Yafu uses brute force to evaluate dozens of polynomials quickly - many that no human would bother to consider - but then it does run some test sieving to fine tune the results. (Test sieving has its limitations too of course.)

Not sure there's an easy way to define the quality of Yafu's results. Compare it's results against the "obvious" one or two SNFS polynomials? Yafu often produces the obvious polynomial. Only use hand calculated results? Sometimes the odd looking poly spit out of Yafu will beat these. How would we know other than laborious test sieving? Which is what Yafu does...

Certainly some of the rules of thumb apply here - look for a small leading coefficient (1 being best), keep things simple, etc. Maybe there's a latent problem here that is now noticeable with higher SNFS difficulties?

I'll throw in one more piece of anecdotal/worthless data - over the past couple of years, a few Yafu polys I've posted have been questioned but none of the suggestions could beat the Yafu results, well until now.

Yeah, all of these are good points. As I think about it, I'd say that with the kind of volume that we're dealing with in the 14e queue, having a tool like Yafu that can test a variety of polynomials is great, and probably worth it even it were routinely choosing a slightly suboptimal polynomial. Where it becomes more worrisome is with longer jobs like those in the 15e queue (or 16e, of course).

Mostly I'm just puzzled by this particular example. I'm not necessarily surprised that Yafu chose a non-obvious polynomial; I'm surprised that it chose one which appears to sieve markedly worse than the obvious one, since it surely would have tried the obvious one too (right?). Which of course brings up your point: "Test sieving has its limitations too." My own version of test sieving could well be insufficient to really capture the likely total sieve times. It might be prudent to get a second (third?) opinion on that before the number actually moves to the sieving state.

[swellman]

Originally Posted by axn

Are there logs from the run? Is it possible to find out if YAFU even considered the simple poly?

Yes Yafu generates a log file, though I don't keep them around. And I don't know how verbose it is, but I think there's a way to dump all onscreen data to a log file. I will investigate and post results in a new thread over on the Yafu sub project. I should be able to reproduce things - as far as I can tell Yafu's poly select algorithm is completely deterministic.

[swellman]

Originally Posted by jyb

Yeah, all of these are good points. As I think about it, I'd say that with the kind of volume that we're dealing with in the 14e queue, having a tool like Yafu that can test a variety of polynomials is great, and probably worth it even it were routinely choosing a slightly suboptimal polynomial. Where it becomes more worrisome is with longer jobs like those in the 15e queue (or 16e, of course).

Mostly I'm just puzzled by this particular example. I'm not necessarily surprised that Yafu chose a non-obvious polynomial; I'm surprised that it chose one which appears to sieve markedly worse than the obvious one, since it surely would have tried the obvious one too (right?). Which of course brings up your point: "Test sieving has its limitations too." My own version of test sieving could well be insufficient to really capture the likely total sieve times. It might be prudent to get a second (third?) opinion on that before the number actually moves to the sieving state.

Agreed. I have no wish to present suboptimal polynomials as the gold standard but one must feed the grid. But I don't think we have a rampant problem, just a one off. That said it would be nice to confirm polys, especially when dealing with higher SNFS difficulties.

I'll run a couple of the poly select routines in Yafu and post detailed logs over in the Yafu forum. B^2 (author of Yafu) and Dubslow may have some insights.

Does anyone see an issue with the eight polys I recently posted? Most have a leading coefficient of 1, 4 or 6, though C224_136_106 now gives me pause with its 53*x^5+68. Getting gun shy I suppose.

[jyb]

Originally Posted by swellman

Certainly some of the rules of thumb apply here - look for a small leading coefficient (1 being best)

Originally Posted by swellman

Does anyone see an issue with the eight polys I recently posted? Most have a leading coefficient of 1, 4 or 6, though C224_136_106 now gives me pause with its 53*x^5+68. Getting gun shy I suppose.

This may just be a case of needing to correct my own ignorance, but I don't understand the guideline about leading coefficients being small. I thought that the polynomial was typically dealt with by the sievers in a homogeneous way, so that a small leading coefficient and a large constant term would pretty much be the same as a small constant term and a large leading coefficient. Is that incorrect?

E.g. I find it hard to believe that the polynomial for C208_148_104, which is 4x^6+231361, would be any better than 231361x^6+4 (with Y1 and Y0 reversed, of course). In fact, I would have guessed that 28561x^4+21904 (with an appropriately adjusted Y1 and Y0) would be better than both, since the skew is then very close to 1, and the SNFS difficulty is actually a little lower. Until I tried it, and found that in this case Yafu definitely seemed to find the better poly.

All of which is to say that my understanding of just what makes the best polynomial (other than actual sieve timing) is obviously somewhat fuzzy and I would love some further clarity. Especially about leading coefficient size.

[jyb]

Originally Posted by swellman

Does anyone see an issue with the eight polys I recently posted?

The poly for C239_150_41 was 6x^6+625. The slightly simpler 150x^6+1 gave a slightly better yield and improved relations/sec (maybe 5% faster).

[axn]

Originally Posted by jyb

E.g. I find it hard to believe that the polynomial for C208_148_104, which is 4x^6+231361, would be any better than 231361x^6+4 (with Y1 and Y0 reversed, of course).

I share in your disbelief. With Y1, Y0 reveresed and using the inverse of skew, they should sieve identically. What does actual test sieving tell us?

Originally Posted by jyb

In fact, I would have guessed that 28561x^4+21904 (with an appropriately adjusted Y1 and Y0) would be better than both, since the skew is then very close to 1, and the SNFS difficulty is actually a little lower. Until I tried it, and found that in this case Yafu definitely seemed to find the better poly.

How did you come up with that poly? The obvious deg-4 poly would be x^4+1, with Y1 =59325966985223687799599734398071581327609, Y0=94770632589105815346482739460795143007415425076212482965504

Originally Posted by jyb

All of which is to say that my understanding of just what makes the best polynomial (other than actual sieve timing) is obviously somewhat fuzzy and I would love some further clarity. Especially about leading coefficient size.

You should consider the size of both the algebraic and rational polys. You can improve one at the cost of worsening the other. The trick is to balance both sides so that you have an overall easier task of finding smooth pairs, even if it is at the cost of having a nominally higher SNFS difficulty.

[jyb]

Originally Posted by axn

I share in your disbelief. With Y1, Y0 reveresed and using the inverse of skew, they should sieve identically. What does actual test sieving tell us?

I didn't try them separately. My disbelief was sufficiently strong that I didn't think it was worth the time/effort.

Originally Posted by axn

How did you come up with that poly? The obvious deg-4 poly would be x^4+1, with Y1 =59325966985223687799599734398071581327609, Y0=94770632589105815346482739460795143007415425076212482965504

I came up with that poly via the very clever trick of having a typo. It should have said 28561x^6+21904. I'm pretty confident we don't want a quartic here.

Originally Posted by axn

You should consider the size of both the algebraic and rational polys. You can improve one at the cost of worsening the other. The trick is to balance both sides so that you have an overall easier task of finding smooth pairs, even if it is at the cost of having a nominally higher SNFS difficulty.

Thanks. Can you define "size" for me?

[axn]

Originally Posted by jyb

I came up with that poly via the very clever trick of having a typo. It should have said 28561x^6+21904. I'm pretty confident we don't want a quartic here.

Originally Posted by jyb

Thanks. Can you define "size" for me?

The size of the numbers you get when you evaluate alg/rat polys at a "typical" lattice point.

For example, let f(x)=c6*x^6+c0 & g(x) = Y1*x+Y0 be the polys. Then the values that we need to be smooth at lattice point (a,b) will be f(a/b) = c6*(a/b)^6+c0 = c6*a^6+c0*b^6, and g(a/b)=Y1*(a/b)+Y0=Y1*a+Y0*b (ignoring the denominators, b^6 & b, resp.)

"Typical" lattice point will vary with the size of sieve region, but might be between 10^4 & 10^7 (a & b values). Based on this we can see how big of a numbers we're dealing with.

[swellman]

Originally Posted by jyb

The poly for C239_150_41 was 6x^6+625. The slightly simpler 150x^6+1 gave a slightly better yield and improved relations/sec (maybe 5% faster).

Thanks for checking and queuing the polys. My hand calculations for C239_150_41 gave x^6+150 as a possible poly (with appropriate Y1 and Y0) though yoyo ultimately settled on 6x^6+625. Glad you found a superior choice. Like you and axn, I'm curious as to the performance of the various polys when swapping cn and c0. I'll run a few comparisons tonight.

Test sieving - yoyo test sieves over a range of 2000 spec_Q in poly selection. I've watched yoyo run a lot of test sieving over the years and I think this is a decent metric for comparison. Typically one or two polys will run nicely, with ETAs close and maybe one poly having a slightly better yield. The performance of the remaining poly(s) will typically be just awful. Test sieving it 5-10x longer isn't going to make it any better. One might argue for more extensive test sieving of the leading candidate polys but how much fine tuning is really needed on an SNFS 230 composite? I've read here in the forum that a minimum test sieving range of 1e5 is needed, preferably over 3-5 samples spread through the anticipated spec_Q range. A lot of work for a ~1% improvement via poly select. Maybe for high difficulty NFS efforts?