[QUOTE=10metreh;172205]What's your gnfs_cutoff? I would have thought GNFS would be faster for a C105.[/QUOTE]The PC has no perl interpreter so I can't run GGNFS on that pc.

Quick question about msieve poly selection. After the time limit is reached, does it read through the poly dat file to figure out which was the best polynomial or does it keep the best one to date in memory?

I have a system that lost its NFS connection to the drive I was writing to but if msieve keeps its best in memory and will write that out at the end, I should still be ok, but if it parses the file I will likely have to re-do it again.

Jeff: the save file is never read at all, it's there for reference only. The best poly found is kept in memory throughout the run; note that if msieve already found a good poly, polynomial selection will not restart unless you rename the .fb file

Ben: the big problem with msieve's current format is that it's stateful. You get one A value and then a block of relations that depend on it. As long as all you do is concatentate relation files it's fine, but many users have done things like make their distributed clients write to the same savefile, and in that case two clients colliding in the savefile will invalidate hundreds of relations, instead of just one. Also, the format itself is quite wasteful: you don't need to know that the polynomial value is negative, since you'll have to compute it and will find out anyway. Factors < 256 don't need to be stored, and the full multiplicity of each factor isn't needed because that will get discovered too. Finally, storing factor base offsets in order means all the sieving clients have to be using the same version of msieve.

[quote=jasonp;168335]The notion of optimality is difficult to apply here; NFS poly selection is a combinatorial optimization problem, and the search space is much too large to have any hope of getting completely explored.[/quote]

Wouldn't this be a good candidate for searching via Genetic Algorithm, which is excellent at exploring large search spaces?

[quote=jasonp;172248] Ben: the big problem with msieve's current format is that it's stateful. You get one A value and then a block of relations that depend on it. As long as all you do is concatentate relation files it's fine, but many users have done things like make their distributed clients write to the same savefile, and in that case two clients colliding in the savefile will invalidate hundreds of relations, instead of just one. [/quote]

I agree it's undesireable, but it's also easy to work around. A large distributed run pretty much begs for a script anyway, so why not increment the output savefile name for each instance of msieve in the script? *shrug* Probably the users aren't entirely aware of the consequences. To make the savefile non-stateful maybe store all 'A' coefficients in a separate msieve.A file, indexed by a hash of the coefficient or something? Then each relation in the savefile would need to store that hash and the 'B' index. The filtering routine would also need to be smart enough to resolve hash collisions. This would add back some file size that is saved by the ideas below...

[quote=jasonp;172248]
Also, the format itself is quite wasteful: you don't need to know that the polynomial value is negative, since you'll have to compute it and will find out anyway. Factors < 256 don't need to be stored, and the full multiplicity of each factor isn't needed because that will get discovered too. [/quote]

Yes, all good ideas.

[quote=jasonp;172248]
Finally, storing factor base offsets in order means all the sieving clients have to be using the same version of msieve. [/quote]

To be truly version independant wouldn't you need to store the primes themselves since the factor base could change from version to version? The fact that they are in order makes it easier to merge them with factor of A, but otherwise wouldn't be necessary, unless I'm forgetting something.

Your suggestions are exactly what I'm planning: every A value gets a small hash, and relations specify which hash they correspond to, with the relation-reading code resolving collisions. And yes, version independence means relations should store their primes, in arbitrary order, with the large primes somewhere in the list and not separated out like they are now.

Regarding the use of general combinatorial techniques like genetic search and simulated annealing, these have been described as 'the second best way of solving almost any problem'. Second to custom methods that exploit any of the underlying structure in the problem. Nevertheless, right now the method used to select polynomials with good size and root properties is to optimize for good size, then optimize for good roots, then fix the size that was messed up by the good roots. That doesn't sound very satisfying, it would be neat to optimize for size and roots simultaneously, but separating the search into two halves allows the fast part of the search to come first and eliminate most candidates, leaving the slow part of the search to find the best one.

I don't know how to change things to make a better search process, but even with Kleinjung's improved algorithm we only explore a small fraction of the available search space. Many have wondered about a better way.

Just a question:
When polynomial search was interrupted (e.g. due to a power outage) - is there an option just to read the outputfile and give the best polynomial which is stored in the outputfile, without doing any further poly search?

Afraid not; if you Ctrl-C out of the run then the best poly found so far is automatically saved, but that doesn't happen if there's a crash. You have to manually find the best E value in the file.

Store the leading coefficient range searched?
 

I have used the polynomial search capabilities several times by restarting and specifying the last leading coefficient as the place to start the new search.

Fortunately, I have always remembered, or been able to scroll up to, the previous upper bound of leading coefficients examined.

A record in the log of which coefficient ranges have been searched would help, for those obsessive-compulsives who think the magic polynomial lies just a few minutes past the last coefficient searched.

the known bug ...Laguerre?
 

Another core dump debug case, just in case; very small:
[CODE] N 5571256368958985423567427396399955429949048328116611460580828800356560407613375067108315353369597147516739093
SKEW 1.98
A5 44
A4
A3
A2
A1
A0 1325
R1 1
R0 -50000000000000000000000
FAMAX 580000
FRMAX 580000
SALPMAX 33554432
SRLPMAX 33554432[/CODE]
this is x86_64 linux. 1.41 crashes with segv; 1.36 runs through (but SKEW line has to be removed).

Yes, this is likely a rootfinder problem. SNFS polynomials tend to have floating point roots that all have nearly the same magnitude, and apparently this throws off the Laguerre rootfinder. As a workaround, if you just want the NFS postprocessing to run then comment out the call to analyze_one_poly in gnfs/gnfs.c

v1.42 will have a much more sophisticated rootfinder.