Compiling Msieve 1.39 on Windows

[Jeff Gilchrist]

Hi Jason,

A quick question for you. I have compiled msieve 1.39 for Windows 64bit using VS2008 with the build.vc project that is supplied in the tar ball. The compile completes just fine linking with my already compiled gmp-ecm code (so I'm assuming it will use the good polynomial selection code).

But it creates an x64/Release directory which contains both:
gnfs.exe
and
mpqs.exe

They are both the same size, have different MD5 hashes, and look like they have the same command line switches. What is the difference between these two binaries and what do you use to create your "msieve.exe" pre-compiled Windows binary that you make available for download on your website?

Thanks,
Jeff.

[jasonp]

When I started the GNFS code a few years ago, the polynomial selection needed to perform a nasty numerical integration, for which I used the GSL library. To avoid burdening all the users who just wanted the QS code from having to download and compile GSL (and/or make their code GPL licensed), the Makefile split out compilation of the NFS source. Thus, you could optionally compile just the QS code, which was self-contained.

Now the NFS code is much more mature, and is always compiled in. Both binaries should act pretty much the same. I don't know why they would be different, perhaps the compiler used different options on one or the other. The binary from my web page is compiled with gcc under MinGW and includes all the optional features in the library. Brian Gladman reports that using the Intel compiler instead of gcc will make QS run noticeably faster.

[Jeff Gilchrist]

Looking at the two VC project files I can see only a couple of differences:

The mpqs version also includes this directory: "..\..\mpqs" and this file "..\..\include\msieve.h"

The gnfs project file includes "..\..\gnfs\gnfs.h"

The demo.c file used as main() are the same files. But whatever it is linking with seems to allow QS code to run with gnfs.exe like here (using VC8 32kb sieve core):

Msieve v. 1.39
Thu Jan 08 07:41:07 2009
random seeds: 412dfbf1 4cb1dfb3
factoring 921347893274892137489213789421738947218394732478932748921734892173485
(69 digits)
searching for 15-digit factors
commencing quadratic sieve (61-digit input)
using multiplier of 5
using VC8 32kb sieve core
sieve interval: 6 blocks of size 32768
processing polynomials in batches of 34
using a sieve bound of 69149 (3400 primes)
using large prime bound of 3457450 (21 bits)
using trial factoring cutoff of 22 bits
polynomial 'A' values have 8 factors

sieving in progress (press Ctrl-C to pause)
3585 relations (1629 full + 1956 combined from 16906 partial), need 3496
3585 relations (1629 full + 1956 combined from 16906 partial), need 3496
sieving complete, commencing postprocessing
begin with 18535 relations
reduce to 5262 relations in 2 passes
attempting to read 5262 relations
recovered 5262 relations
recovered 4555 polynomials
attempting to build 3585 cycles
found 3585 cycles in 1 passes
distribution of cycle lengths:
   length 1 : 1629
   length 2 : 1956
largest cycle: 2 relations
matrix is 3400 x 3585 (0.5 MB) with weight 98776 (27.55/col)
sparse part has weight 98776 (27.55/col)
filtering completed in 3 passes
matrix is 3178 x 3242 (0.4 MB) with weight 87787 (27.08/col)
sparse part has weight 87787 (27.08/col)
commencing Lanczos iteration
memory use: 0.6 MB
lanczos halted after 52 iterations (dim = 3173)
recovered 62 nontrivial dependencies
p1 factor: 5
p2 factor: 67
p3 factor: 499
p3 factor: 967
prp20 factor: 10441567216470713251
prp42 factor: 545866109743310638237257515591452570387277
elapsed time 00:00:07

The mpqs.exe gives the same results. If I trying using s GNFS command like -np both executables will allow that but both of them fail after a few seconds.

Msieve v. 1.39
random seeds: 0445c0c8 124b5a16
factoring 542199118360122645149018222712631403787793963895701957093138322222784637474878020968003860466806398192243491945916177216280574963 (129 digits)
searching for 15-digit factors
commencing number field sieve (129-digit input)
commencing number field sieve polynomial selection
time limit set to 13.65 hours
searching leading coefficients from 25202 to 91114
expand failed
expand failed
expand failed
expand failed
expand failed
expand failed
expand failed
expand failed
expand failed
expand failed
expand failed
expand failed
...
polynomial selection complete
warning: polynomial is corrupt
elapsed time 00:00:05

So I get a continuous flow of "expand failed" errors until I hit CTRL-C and it says the polynomial is corrupt. So something seems to be messed up with the VC build files now as it is not generating a working copy of msieve and it is confusing to have both a gnfs.exe and mpqs.exe since they both seem to be identical when compiled.

Jeff.

[jasonp]

I don't know that anyone has tested NFS polynomial selection when compiling with MSVC, so it's not completely surprising that it has problems. Unfortunately I don't have the means to do so myself.

Also, I'd suggest that everyone hold off trying to fix that because the NFS polynomial selection is an undocumented mess right now.

[Jeff Gilchrist]

Is there any way to produce a 64bit binary on Windows with MinGW then?

So far the 32bit msieve you provide has been able to do anything I have asked it to, I'm not sure if a 64bit version would have any improvements or the ability to deal with larger numbers?

Jeff.

[jasonp]

There is supposed to be a MinGW set of cross-compilation tools that can produce 64-bit binaries, but all of it is in alpha state right now. If you use msieve for NFS postprocessing then I know that binaries produced with 64-bit MSVC do work.

64-bit postprocessing is pretty much needed for NFS inputs larger than a moderately small size. By the time you get to 135-140 digit GNFS or 210-220 digit SNFS, you're really pushing the boundaries of what can fit into a 2GB process memory space.

[Jeff Gilchrist]

I just tried the gnfs.exe 64bit version to post-process one of my recently completed GNFS jobs so you are right, that code works fine compiled with Visual Studio, I guess it is just the polynomial stuff that is messed up.

Good to know, I can use my msieve64.exe for everything except polynomial selection, and the 32bit one for that. Keep up the good work Jason, msieve is very useful. Thanks for putting so much time and effort into it.

[jasonp]

My pleasure, keep pushing the limits of the stuff that I can't test. It's a nice program today because of all the man-years that everyone has spent doing that.

[Brian Gladman]

If anyone has examples of things that: (a) succeed in 32-bits but fail in 64-bits; (b) are repeatable; (c) fail in a short time from start up, and (d) don't require too much data to be downloaded, I would be happy to try to isolate the problem or problems. Subject, of course to Jason's entreaty that it might not be the right time to debug some of the code.

Having good examples of failures is the biggest problem in finding these bugs.

It is possible to do 64-bit compilation with mingw64 but it is still quite hard work.

Brian Gladman

[FactorEyes]

Originally Posted by Jeff Gilchrist

Keep up the good work Jason, msieve is very useful. Thanks for putting so much time and effort into it.

Seconded.

I've enjoyed both the code and the application.

[dleclair]

I'd like to add my special thanks to Mr. Gladman. The ongoing work he has done to build and maintain Visual Studio projects for gmp, gmp-ecm, msieve and others is difficult, time consuming and, I'm sure, largely thankless. The work to convert assembly code must be particularly onerous. So I'd like to say "thank you" as his efforts have made it incredibly easy for me to build many various applications using GMP as well as my own builds of msieve.

-Don Leclair