@jasonp:
Thank you very much for your answer. My hopes to kill the C204 of N200 from the Bernoulli thread are all gone now :razz: I have to stay on factoring C120 with yafu (which uses the CPU version of msieve only) and use the GPU for something else (like mfaktx or cudalucas) that give me less headache to maintain running and do not need more then entry-level factoring knowledge :smile:.

SVN 727 now has a major overhaul of the handling of command line arguments, so that free-form strings of key-value pairs can be passed into the library. Everyone's standard command lines should still work, but now you have control of much more of the NFS internals. Check out the new usage text to see what you can do now.

For example, if you know the poly selection parameters you want, then you can pass all the stuff on the command line that used to be in Msieve's internal tables, but can change a little bit (like the polynomial degree :) or configure polynomial selection for an input size that Msieve doesn't currently know about.

Please let me know if anybody's scripts break with the new scheme.

[QUOTE=jasonp;306320]SVN 727 now has a major overhaul of the handling of command line arguments, so that free-form strings of key-value pairs can be passed into the library. [/QUOTE]
Cool! A request: please add an option to skip building of the matrix on -nc2 and instead use an existing matrix. With this, I can retire my patch to comment out the matrix building code. Thanks. :smile:

I'd forgotten about that; SVN729 has the code to do it, but the demo is under construction with more poly selection changes so documenting it will have to wait a bit

Now SVN 732 has the changes that will make testing out polynomial selection for very large GNFS jobs easier. Stage 2 has been split into size optimization and root optimization, and the two can be run independently. The parameters are printed out and can be used to fine-tune the choice of bound without having to recompile anything.

The next step will be removing most of the debug info and starting to run some longer tests.

Let me know if you see anything fishy with the new changes.

[quote]Now SVN 732 has the changes that will make testing out polynomial selection for very large GNFS jobs easier. Stage 2 has been split into size optimization and root optimization, and the two can be run independently. The parameters are printed out and can be used to fine-tune the choice of bound without having to recompile anything.[/quote]
Great :smile:

For testing purposes, I've started msieve -np1 -nps on [url]http://factordb.com/index.php?id=1100000000422935437[/url] , for OddPerfect. Stage 1 is performed by a Nvidia GT 540M.

How can I programmatically sort the contents of the .dat.ms file, so as to let the msieve -npr process only several hundreds of the most promising entries ? IIRC from watching the screen output of msieve on previous polynomial selection runs, a lower transition code is better, but it's not obvious (to me, at least) how to obtain it from lines such as
[code]12 61765287500 123806484245375823010 -762447079898759816039 -322693759176415246027392380483 620549008422040121637362019719 20180412165247 -446269005578891270376925706187
12 -48689202038 74478806675952624690 496383863140506971709 -368049650259856571886422453189 -663163494375397326396941049147 19004170159879 -446269041774671942795591426194
12 8771763996 -37487637400072795 49351373043636400336061619 22262886741162973524462273952223 -33175480607070110072234462882573510382425 520668666264919 -446268950233355877290430810988[/code]

There is currently no way to rank the output from the size optimization; perhaps the easiest way to do that is to turn on the code at line 425 of gnfs/poly/stage2/optimize.c, which prints out the optimized polynomial and its score.

So, I dug a bit into msieve, starting from the file you indicated :smile:

In find_poly_core (gnfs/poly/poly_skew.c), I found the following code snippet, for reading the output of msieve -nps:
[code] while (1) {
int c;
char *tmp = buf;

/* this reading scheme is unintuitive but more
resistant to corrupted input lines */

if (fgets(tmp, sizeof(buf), sizeopt_outfile) == NULL)
break;

for (i = 0; i <= degree; i++) {
if (gmp_sscanf(tmp, "%Zd%n",
alg_coeffs[degree - i], &c) != 1)
break;
tmp += c;
}

if (gmp_sscanf(tmp, "%Zd %Zd",
rat_coeffs[1], rat_coeffs[0]) != 2)
continue;

/* make later code figure out the initial poly score */

poly_rootopt_run(&rootopt_data, alg_coeffs, rat_coeffs, 0, 0);
if (obj->flags & MSIEVE_FLAG_STOP_SIEVING)
break;
}[/code]That seemed to mean that arbitrary data between the polynomial's algebraic and rational coefficients, and the end of the line, is ignored. So I've tried to print the score and projected alpha:
[code]Index: gnfs/poly/poly_skew.c
===================================================================
--- gnfs/poly/poly_skew.c (révision 733)
+++ gnfs/poly/poly_skew.c (copie de travail)
@@ -102,7 +102,8 @@
for (i = deg; (int32)i >= 0; i--)
gmp_fprintf(mfile, "%Zd ", alg_coeffs[i]);

- gmp_fprintf(mfile, "%Zd %Zd\n", rat_coeffs[1], rat_coeffs[0]);
+ gmp_fprintf(mfile, "%Zd %Zd", rat_coeffs[1], rat_coeffs[0]);
+ fprintf(mfile, " %.7e %.7e\n", sizeopt_norm, projective_alpha);
fflush(mfile);
}[/code]The modified binary of msieve, invoked as `msieve -npr`, isn't unhappy with a short file it generated when invoked as `msieve -np1 -nps`.


My modifications are not going to change the ~100K lines generated so far by msieve -nps on the current C150. However, fiddling with the contents of poly_rootopt_run, changing the visibility of sizeopt_callback_log, and possibly other changes, might enable me to re-print the norms of the generated polynomials without too much hassle.
EDIT: yeah, that seems to do the job.

Okay... I've done some digging of my own, and now I even mostly understand the conversation above :smile:

Questions/notes (probably stupid):
[LIST][*]First, a typo in poly_param.c:
[code]249 tmp = strstr(obj->nfs_args, "stage1_norm=");
250 if (tmp != NULL)
251 params.stage1_norm = strtod(tmp + 12, NULL);
252
253 tmp = strstr(obj->nfs_args, "stage2_norm=");
254 if (tmp != NULL)
255 params.stage[B][I]1[/I][/B]_norm = strtod(tmp + 12, NULL);[/code]
[*]I see that rootopt_callback() prints polys in GGNFS format only? That probably means some other parts of the code need to be cleaned up (like write_poly()/read_poly() )...?

[*]How do we/you determine what decent S1/S2 max norm values are for RSA-1024? Do some testing with RSA-896? Perhaps run a few cycles here before sending out a BOINC app?

[*]Re coefficient search space: I'm not sure I've located the code that randomly chooses a portion to search, but is that portion something which could be passed in as an argument, so that the BOINC server can hand out specific ranges within a coefficient (analogous to YAFU specifying a sigma for each ECM curve it runs in parallel)? Or is the space per coeff [i]so[/i] huge that even with thousands of computers, the chance of overlap is minimal?

[*]Heck, before even thinking about each individual coeff, [STRIKE]how high should the coeff search should go (I can't find back that part of the code)[/STRIKE] ...how valid is the formula in the code for >300 digits? I computed a default high coeff of 6221527005 for RSA-1024, but of course there's conditions on the coeffs searched. How many coeffs in that range would need searching How does the estimated total time of a few core millenia compare to that number of coeffs? Should there really be a deadline per coefficient for a distributed poly select?[/LIST]

[QUOTE=Dubslow;307654]
First, a typo in poly_param.c:
[code]249 tmp = strstr(obj->nfs_args, "stage1_norm=");
250 if (tmp != NULL)
251 params.stage1_norm = strtod(tmp + 12, NULL);
252
253 tmp = strstr(obj->nfs_args, "stage2_norm=");
254 if (tmp != NULL)
255 params.stage[B][I]1[/I][/B]_norm = strtod(tmp + 12, NULL);[/code]
[/QUOTE]
Oops, now fixed.
[QUOTE]
I see that rootopt_callback() prints polys in GGNFS format only? That probably means some other parts of the code need to be cleaned up (like write_poly()/read_poly() )...?
[/QUOTE]
The printing in GGNFS format was to simplify cutting and pasting into other files for use with the lasieve tools; read_poly and write_poly work with the Msieve format only
[QUOTE]
How do we/you determine what decent S1/S2 max norm values are for RSA-1024? Do some testing with RSA-896? Perhaps run a few cycles here before sending out a BOINC app?
[/QUOTE]
For the stage 1 norm, you calculate how big a random polynomial coefficient is going to be, then calculate how much smaller you want the third-highest polynomial coefficient to be, and the skew you want to deal with. That gives an approximate range to specify.

In practice, people here typically start with a very permissive value of the norm, then dial it back until stage 1 hits almost stop coming. For RSA896 and leading coefficients around 1M a stage 1 norm of around 1e36 produces decent results. Of course as the code gets more efficient the stage 1 norm can get more stringent :)

The analysis for the stage 2 norm can't really work this way, because the definition of the norm function is much more complex (all the polynomial coefficients plus the skew contribute to it).
[QUOTE]
Re coefficient search space: I'm not sure I've located the code that randomly chooses a portion to search, but is that portion something which could be passed in as an argument, so that the BOINC server can hand out specific ranges within a coefficient (analogous to YAFU specifying a sigma for each ECM curve it runs in parallel)? Or is the space per coeff [i]so[/i] huge that even with thousands of computers, the chance of overlap is minimal?
[/QUOTE]
The choice of piece to search is deep in the guts of the stage 1 code (gnfs/poly/stage1/stage1_sieve_{cpu|gpu}.c), because the number of pieces depends on the size of the search space, which depends on the choice of a bunch of other things that isn't known until stage 1 actually runs (and is different for the GPU code). The number of pieces is capped at 450, but for large problems even one of those pieces is a huge chunk of work, and the birthday paradox says you'd need 20-25 computers searching the same range before it's likely that work will be duplicated.
[QUOTE]
...how valid is the formula in the code for >300 digits? I computed a default high coeff of 6221527005 for RSA-1024, but of course there's conditions on the coeffs searched. How many coeffs in that range would need searching How does the estimated total time of a few core millenia compare to that number of coeffs? Should there really be a deadline per coefficient for a distributed poly select?
[/QUOTE]
Nobody has looked seriously at the numbers for extremely large GNFS; consider them all to be garbage.

We've had a lot of discussion about how best to divide up an effectively infinite search space. The overall time limit is turned off if searching a range, but you don't want to spend days on one leading coefficient, even though you will if you don't stop early.

[QUOTE=jasonp;307659]
For the stage 1 norm, you calculate how big a random polynomial coefficient is going to be, then calculate how much smaller you want the third-highest polynomial coefficient to be, and the skew you want to deal with. That gives an approximate range to specify.

In practice, people here typically start with a very permissive value of the norm, then dial it back until stage 1 hits almost stop coming. For RSA896 and leading coefficients around 1M a stage 1 norm of around 1e36 produces decent results. Of course as the code gets more efficient the stage 1 norm can get more stringent :)[/quote]

Would it help to add some minor functionality to collect and print basic statistics collected during stage 1, perhaps as a compiler directive for the test runs?

[QUOTE=jasonp;307659]
The analysis for the stage 2 norm can't really work this way, because the definition of the norm function is much more complex (all the polynomial coefficients plus the skew contribute to it).[/quote]

:doh!: Is that a root norm or size norm? (I.e., can it be ignored for -ns?)

[QUOTE=jasonp;307659]
The choice of piece to search is deep in the guts of the stage 1 code (gnfs/poly/stage1/stage1_sieve_{cpu|gpu}.c), because the number of pieces depends on the size of the search space, which depends on the choice of a bunch of other things that isn't known until stage 1 actually runs (and is different for the GPU code). The number of pieces is capped at 450, but for large problems even one of those pieces is a huge chunk of work, and the birthday paradox says you'd need 20-25 computers searching the same range before it's likely that work will be duplicated.[/quote]

I'm glad I asked, because whatever answer I was expecting, that wasn't it. :smile: So it seems that having no more than 10-15 workers per coefficient will work fine...

[QUOTE=jasonp;307659]
Nobody has looked seriously at the numbers for extremely large GNFS; consider them all to be garbage.

We've had a lot of discussion about how best to divide up an effectively infinite search space. The overall time limit is turned off if searching a range, but you don't want to spend days on one leading coefficient, even though you will if you don't stop early.[/QUOTE]
...unless of course each coefficient would take a lifetime to search :smile: I take it that without the time limit, for a problem this large (or even much smaller problems), Msieve could go on forever with one coefficient? And that the time limit per coeff is simply the only reasonable/practical way to do it?