mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   YAFU (https://www.mersenneforum.org/forumdisplay.php?f=96)
-   -   Yafu SNFS difficulty calculation (https://www.mersenneforum.org/showthread.php?t=26498)

jyb 2021-02-16 06:07

Yafu SNFS difficulty calculation
 
Can anybody help me understand the values Yafu is claiming for the difficulty in this example?[code]
n: 401721424383720426137324949508336187045848565417289917430550907056665790265814883369879394476169080075318675151956526421358049691930517872710129161972339727160629599769770122149882863
# 7^307+6^307, difficulty: 260.29, anorm: 1.30e+037, rnorm: 1.27e+049
# scaled difficulty: 262.29, suggest sieving rational side
# size = 1.218e-012, alpha = 0.000, combined = 1.324e-013, rroots = 0
type: snfs
size: 260
skew: 0.9746
c6: 7
c0: 6
Y1: -4849687664788584363858837602739217760256
Y0: 12589255298531885026341962383987545444758743
...
[/code]

The actual SNFS difficulty given by these polynomials is 259.445, according to every definition of SNFS difficulty that I've ever seen. So what are "difficulty", "scaled difficulty" and "size" (the second one) supposed to represent here?

bsquared 2021-02-16 14:55

[QUOTE=jyb;571720]Can anybody help me understand the values Yafu is claiming for the difficulty in this example?[code]
n: 401721424383720426137324949508336187045848565417289917430550907056665790265814883369879394476169080075318675151956526421358049691930517872710129161972339727160629599769770122149882863
# 7^307+6^307, difficulty: 260.29, anorm: 1.30e+037, rnorm: 1.27e+049
# scaled difficulty: 262.29, suggest sieving rational side
# size = 1.218e-012, alpha = 0.000, combined = 1.324e-013, rroots = 0
type: snfs
size: 260
skew: 0.9746
c6: 7
c0: 6
Y1: -4849687664788584363858837602739217760256
Y0: 12589255298531885026341962383987545444758743
...
[/code]

The actual SNFS difficulty given by these polynomials is 259.445, according to every definition of SNFS difficulty that I've ever seen. So what are "difficulty", "scaled difficulty" and "size" (the second one) supposed to represent here?[/QUOTE]





Difficulty is computed in the normal way, except here it looks like I may have included the contribution of the leading coefficient twice. Thanks for that report. As for scaled difficulty, quoting here from the code:

[QUOTE=snfs.c]
// poly degrees yielding very unbalanced norms are less desirable for sieving.
// reflect this by scaling the difficulty of these polys. Since special-q can
// bring the norm down on one side or another (at the expense of the other side),
// we add one to the difficulty for every order of magnitude imbalance beyond 6
// between the two sides (until we figure out something more accurate)[/QUOTE]

i.e., it's an attempt to call attention to polynomials that are very unbalanced (of undesirable degree). If the scaled difficulty is sufficiently bigger than the normal difficulty, yafu will try to compensate by increasing the factor base, large prime bounds, and trial factoring bounds. This happens in skew_snfs_params(). Looks like the scaled difficulty needs to be at least 4 bigger than normal (corresponding to 24 orders of magnitude difference in norms) before any parameters are altered.

Size is rounded difficulty. IIRC ggnfs doesn't use size for anything.

p.s.
I'm happy to consider alternatives if you have any suggestions! As indicated above, scaled difficulty was a mix of numerology and experience from back when I was actively performing snfs work.

charybdis 2021-02-16 18:08

[QUOTE=jyb;571720][code]anorm: 1.30e+037, rnorm: 1.27e+049[/code][/QUOTE]

These are a bit small, especially anorm; the code uses a = 1e6*sqrt(skew), b=1e6/sqrt(skew) which might work well for small jobs but for numbers this large 1e6 is a big underestimate.

Really it should be something like a = sqrt(2^(2I-1)*Q*skew)*const, b = sqrt(2^(2I-1)*Q/skew)*const where Q is a realistic average special-q; smaller a and b give more relations so const should maybe be around 0.2? Not sure how it would be best to code this, given that the scaled difficulty informs the choice of I and Q. Perhaps use some function of difficulty that's a reasonable approximation of sqrt(2^(2I-1)*Q)?

And really anorm ought to be multiplied by exp(alpha) to account for root properties of the algebraic polynomial, but if you're doing a job large enough that this matters, then you ought to be test-sieving anyway.

bsquared 2021-02-16 19:33

[QUOTE=charybdis;571762]...

Not sure how it would be best to code this, given that the scaled difficulty informs the choice of I and Q. Perhaps use some function of difficulty that's a reasonable approximation of sqrt(2^(2I-1)*Q)?
...

[/QUOTE]

Thanks for the suggestions! Using the siever area is simple and straightforward and by itself gets the estimates much closer to actual norm sizes. So I'm tempted to just use
sqrt(2^(2I-1)*1e6*skew) and sqrt(2^(2I-1)*1e6/skew) as I think finer adjustments to Q or using alpha would be in the noise of what this estimate is used for.

jyb 2021-02-24 16:23

Here's another one, though perhaps with the opposite cause. The correct difficulty is 255.99. It looks like in this case Yafu didn't add the leading coefficient at all (255.14 ≈ 245*log_10(11)).
[code]
n: 7384049810391587250211352363287406947175960642669013845450189424529816242856745368078260733462087073764724231472029401134928725306986130695481851831787933178814661362606610448657133293018573723301486442995118362671069447396748839101553572591556351201
# 11^244+7^244, difficulty: 255.14, anorm: 1.75e+031, rnorm: 1.02e+057
# scaled difficulty: 259.44, suggest sieving rational side
# size = 1.944e-017, alpha = 0.000, combined = 7.014e-014, rroots = 1
type: snfs
size: 255
skew: 1.0946
c5: 7
c0: 11
Y1: -256923577521058878088611477224235621321607
Y0: 1067189571633593786424240872639621090354383081702091
[/code]


All times are UTC. The time now is 02:22.

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.