How to test-sieve

[charybdis]

Originally Posted by bur

So having an SNFS-177 take as long as a GNFS-139 really seems a bit long? I thought it might be due to the large coeffcient but the steep increase surprised me.

It was the 4-digit increase in GNFS equivalent difficulty for a 3-digit increase in SNFS difficulty that surprised me. Judging by the E scores of the polynomials, I would have expected them to sieve more like GNFS-134 and 135, so the second number has taken longer than it should have done. I'm especially surprised given that you used the same parameters for both numbers. Are you sure you didn't have any other processes slowing the second job down?

I'd have used roughly c135 parameters for both jobs given the E scores.

I managed to build a matrix using msieve with 60M relations. From my experience msieve tends to require more relations than cado to build a matrix (why is that?), so for the current factorization I decreased rels_wanted to 60M.

I think the CADO filtering tools are just slightly better tuned than msieve. I've never tried this, but it's possible that playing around with some of the additional arguments for -nc1 might allow msieve to build a matrix with slightly fewer relations.

If the rels_wanted figure was off for the c135 parameters, maybe it was off for the c130 parameters too. That still doesn't explain the discrepancy between the two numbers.

By the way, it is essential to add tasks.sieve.adjust_strategy = 2 whenever you use tasks.A = [even number] rather than tasks.I. There should be a noticeable speedup.

[bur]

Originally Posted by charybdis

By the way, it is essential to add tasks.sieve.adjust_strategy = 2 whenever you use tasks.A = [even number] rather than tasks.I. There should be a noticeable speedup.

Then that might be a big part of the problem, I didn't include it in the params file.


Other than that, I don't remember the exact point of this increase but it was quite sudden. I found a possible explanation though. I don't do every number by SNFS since most are factored by easy ECM. So it might have been that I compared a number with an exponent divisible by 5 to one that was == 4 (mod 5).


SNFS-179 number 1281979*2^594+1 with polynomial 1281979*2^4*(2^118)^5+1 has an E-score of 3.365E-11 while the SNFS-175 number 1281979*2^580+1 yields an E-score of 5.747E-11. I am not sure how strongly that affects sieving times, but the former E-score is 42% lower, so it might be quite significant?


Add to that the problem with the missing adjust_strategy and it might explain everything.

[charybdis]

Originally Posted by bur

SNFS-179 number 1281979*2^594+1 with polynomial 1281979*2^4*(2^118)^5+1 has an E-score of 3.365E-11 while the SNFS-175 number 1281979*2^580+1 yields an E-score of 5.747E-11. I am not sure how strongly that affects sieving times, but the former E-score is 42% lower, so it might be quite significant?

The E-score is supposed to be directly proportional to yield for a fixed set of parameters, so you'd expect the number with the lower score here to take about 70% longer if the parameters remain the same. You can reduce that 70% figure a bit by using slightly different parameters for the two jobs, but this E-score ratio is consistent with a 3-4 digit increase in GNFS equivalent difficulty.

[bur]

Alright, thanks. The tasks.sieve.adjust_strategy = 2, is there a general rule if it's useful for SNFS or not? And if I was to test and change this back to 0, I should probably also revert to tasks.I? From the manual either 13 or 14 would correspond to A = 26, correct?

[charybdis]

tasks.I = n corresponds to tasks.A = 2n-1, so A=26 is between I=13 and I=14.

If you're using an even value of A, you should use adjust_strategy = 2 whatever the circumstances. For tasks.I (in other words, odd values of A), VBCurtis's testing showed that adjust_strategy = 2 is advantageous for GNFS from around 125 digits upwards, though the difference in speed is very small. I don't think much SNFS testing has been done but I'd expect the dynamics to be similar, i.e. use strategy 2 for SNFS jobs of difficulty equivalent to GNFS-125 or higher.

[bur]

Yes, according to CADO manual A can be used to fine-tune that parameter. So for integer values of I (or odd values of A) it doesn't matter which one is used?


This 188 digit 2^602*1281979+1 took 9:20 for sieving, even with adjust_strategy. So I guess it is just a peculiarity of these SNFS numbers that the E-scores are low and sieving takes long.


Btw, is the only difference between GNFS and SNFS that the latter has a simple polynomial? Earlier I was under the impression that SNFS was having a different sieving process, but it doesn't seem so. Or does cado recognize the SNFS type polynomial and internally switches to "SNFS"?

[charybdis]

The advantage for adjust_strategy=2 with integer I seems to get greater for larger jobs. I don't know why this happens, but it does. So if you're doing a big job then you definitely will want strategy 2: saving 5% of sieving time on a c180 GNFS is absolutely worth it.

I don't know how your timings for GNFS and other SNFS jobs compare, so I can't tell what counts as slow. If you're meaning that these SNFS jobs take longer than the "rules of thumb" for SNFS-GNFS conversion indicate, then yes - that's because of the large c5 coefficient.

There is no difference between the SNFS and GNFS algorithms once we've got a polynomial. SNFS just means the special form of the number allows a polynomial to be easily found, usually with small coefficients. (Historical note: in the early days, there was more of a difference, because SNFS was initially only developed for numbers of the form b^n +- c where the algebraic number theory is easier.)

[bur]

Ok thanks, good to know.