Msieve 1.40 Beta Feedback

[tmorrow]

Jason, I've downloaded and built 1.40 beta from source. Just offering some feedback as you requested. Build details follow.

Compiled under Windows XP SP3 (32 bit) in a cygwin environment
gcc version 3.4.4 (cygming special, gdc 0.12, using dmd 0.125)

Linked msieve with ECM 6.2.1 and GMP 4.2.4.

# Makefile variations for cputype and GMP + ECM includes and static libraries
OPT_FLAGS = -O3 -fomit-frame-pointer -march=k8 -DNDEBUG
CFLAGS += -I/cygdrive/c/tim/mingprojects/ecm/include -I/cygdrive/c/tim/mingprojects/gmp/include
LFLAGS += -L/cygdrive/c/tim/mingprojects/ecm/lib -L/cygdrive/c/tim/mingprojects/gmp/lib

# Build command
make x86 ECM=1 2>&1 | tee build.log

Compile Warnings (not new, have been there for a long time)

gcc -D_FILE_OFFSET_BITS=64 -O3 -fomit-frame-pointer -march=k8 -DNDEBUG  -Wall -W -Wconversion -I. -Iinclude -Ignfs/poly -I/cygdrive/c/tim/mingprojects/ecm/include -I/cygdrive/c/tim/mingprojects/gmp/include -DHAVE_GMP_ECM -DHAVE_GMP -c -o common/fastmult.o common/fastmult.c
common/fastmult.c: In function `fastmult_info_free':
common/fastmult.c:73: warning: passing arg 1 of `dd_clear_precision' with different width due to prototype

gcc -D_FILE_OFFSET_BITS=64 -O3 -fomit-frame-pointer -march=k8 -DNDEBUG  -Wall -W -Wconversion -I. -Iinclude -Ignfs/poly -I/cygdrive/c/tim/mingprojects/ecm/include -I/cygdrive/c/tim/mingprojects/gmp/include -DHAVE_GMP_ECM -DHAVE_GMP -Ignfs -c -o gnfs/poly/polyutil.no gnfs/poly/polyutil.c
gnfs/poly/polyutil.c: In function `analyze_one_poly':
gnfs/poly/polyutil.c:145: warning: passing arg 1 of `dd_clear_precision' with different width due to prototype

gcc -D_FILE_OFFSET_BITS=64 -O3 -fomit-frame-pointer -march=k8 -DNDEBUG  -Wall -W -Wconversion -I. -Iinclude -Ignfs/poly -I/cygdrive/c/tim/mingprojects/ecm/include -I/cygdrive/c/tim/mingprojects/gmp/include -DHAVE_GMP_ECM -DHAVE_GMP -Ignfs -c -o gnfs/poly/stage2/stage2.no gnfs/poly/stage2/stage2.c
gnfs/poly/stage2/stage2.c: In function `poly_stage2_run':
gnfs/poly/stage2/stage2.c:257: warning: passing arg 1 of `dd_clear_precision' with different width due to prototype

Since dd_precision (from dd.h) is being defined on this platform as "typedef uint16 dd_precision_t;", the -Wconversion option is raising those warnings. Unless you've got a special need for it you might consider removing the -Wconversion option from WARN_FLAGS in your Makefile. With modern code this option is not normally useful - see for example
http://sourceware.org/ml/glibc-linux.../msg00083.html
http://gcc.gnu.org/ml/gcc/2002-12/msg01431.html

Feature request - Have msieve indicate which versions (if used) of GMP & ECM that msieve was linked with.

I have not yet conducted extensive tests on 1.40 yet.

I'll build msieve 1.40 on a emt x64 RHat5 Linux server tomorrow and let you know how it goes.

[akruppa]

I'm not really sure if this is something you planned to fix in 1.40, but I ran poly selection on the c160 of 3,527- again, and I still get lots of "warning: skipping corrupt polynomial" messages. So far after 90 minutes search, no valid poly seems to be found.

Alex

[jasonp]

tmorrow: -Wconversion catches lots of issues like function arguments to GMP calls that are not properly cast to mp_limb_t when this is a 64-bit type. In many cases the code doing the calling must take special measures when this is the case, so I prefer to keep it on. Most of the time it's just really verbose, and the warnings are harmless, but occaisionally it points out something I've forgotten.

Alex: I'd forgotten about your problems. Could you PM me the input number and which platform and gcc version you're running? The numerical integration code is probably the culprit here, it's much more robust in v1.40 but even in my internal tests it still occaisionally fails.

[Jeff Gilchrist]

When you type just "make" you get this output:

pick a target:
x86       32-bit Intel/AMD systems (required if gcc used)
x86_64    64-bit Intel/AMD systems (required if gcc used)
generic   portable code
also add 'ECM=1' if GMP-ECM is available or you want the
advanced NFS polynomial selection

Do you actually need ECM=1 to do NFS poly selection or just GMP (so GMP=1 would work)?

If the latter could you modify that output to be something like:

add 'ECM=1' if GMP-ECM is available (enables ECM and
advanced NFS polynomial selection)
or add 'GMP=1' if only GMP is available and you want the
advanced NFS polynomial selection

[jasonp]

I'll make the change; I've tried to keep it short because in MinGW, 'make' takes forever to echo text lines, like two per second max. That's not a sufficient excuse in this case because many have been confused about compiling the new poly selection.

PS: Brian Gladman has already pointed out that the MSVC code needs some fixing too, looks like I'll need to post an update tonight.

[akruppa]

I hadn't compiled with ECM=1 nor GMP=1, I'll try again.

Alex

[10metreh]

That old timer is having problems again:

Mon Mar 02 17:23:04 2009  
Mon Mar 02 17:23:04 2009  
Mon Mar 02 17:23:04 2009  Msieve v. 1.40
Mon Mar 02 17:23:04 2009  random seeds: 0010f447 0021e88e
Mon Mar 02 17:23:04 2009  factoring 3046940677438483872492570557601426992994034892890836252574868172241908349534364214600428141457053 (97 digits)
Mon Mar 02 17:23:06 2009  searching for 15-digit factors
Mon Mar 02 17:23:09 2009  commencing number field sieve (97-digit input)
Mon Mar 02 17:23:09 2009  R0: -6102425988474888054
Mon Mar 02 17:23:09 2009  R1:  9564234367
Mon Mar 02 17:23:09 2009  A0:  407934978221462444764895
Mon Mar 02 17:23:09 2009  A1: -154209112521686219328
Mon Mar 02 17:23:09 2009  A2: -7261393706314151
Mon Mar 02 17:23:09 2009  A3:  1675925509656
Mon Mar 02 17:23:09 2009  A4:  25858416
Mon Mar 02 17:23:09 2009  A5:  360
Mon Mar 02 17:23:09 2009  skew 10703.18, size 3.876917e-009, alpha -6.133547, combined = 5.255935e-009
Mon Mar 02 17:23:09 2009  
Mon Mar 02 17:23:09 2009  commencing relation filtering
Mon Mar 02 17:23:09 2009  commencing duplicate removal, pass 1
Mon Mar 02 17:23:20 2009  error -15 reading relation 301787
Mon Mar 02 17:23:28 2009  error -11 reading relation 601316
Mon Mar 02 17:23:43 2009  error -15 reading relation 1034599
Mon Mar 02 17:23:45 2009  error -4 reading relation 1066768
Mon Mar 02 17:23:49 2009  found 69307 hash collisions in 1216878 relations
Mon Mar 02 17:24:08 2009  added 462 free relations
Mon Mar 02 17:24:08 2009  commencing duplicate removal, pass 2
Mon Mar 02 17:24:14 2009  found 68434 duplicates and 1148906 unique relations
Mon Mar 02 17:24:14 2009  memory use: 33.2 MB
Mon Mar 02 17:24:16 2009  reading rational ideals above 851968
Mon Mar 02 17:24:16 2009  reading algebraic ideals above 851968
Mon Mar 02 17:24:16 2009  commencing singleton removal, pass 1
Mon Mar 02 17:29:16 2009  relations with 0 large ideals: 17926
Mon Mar 02 17:29:34 2009  relations with 1 large ideals: 150065
Mon Mar 02 17:29:34 2009  relations with 2 large ideals: 405869
Mon Mar 02 17:29:34 2009  relations with 3 large ideals: 405233
Mon Mar 02 17:29:34 2009  relations with 4 large ideals: 142375
Mon Mar 02 17:29:34 2009  relations with 5 large ideals: 14382
Mon Mar 02 17:29:34 2009  relations with 6 large ideals: 13055
Mon Mar 02 17:29:34 2009  relations with 7+ large ideals: 1
Mon Mar 02 17:29:34 2009  1148906 relations and about 1427416 large ideals
Mon Mar 02 17:29:35 2009  commencing singleton removal, pass 2
Mon Mar 02 17:31:29 2009  found 750409 singletons
Mon Mar 02 17:31:47 2009  current dataset: 398497 relations and about 413553 large ideals
Mon Mar 02 17:31:55 2009  commencing singleton removal, pass 3
Mon Mar 02 17:33:34 2009  found 172902 singletons
Mon Mar 02 17:33:44 2009  current dataset: 225595 relations and about 203432 large ideals
Mon Mar 02 17:33:52 2009  commencing singleton removal, final pass
Mon Mar 02 17:35:24 2009  memory use: 4.2 MB
Mon Mar 02 17:35:26 2009  commencing in-memory singleton removal
Mon Mar 02 17:35:26 2009  begin with 225594 relations and 205228 unique ideals
Mon Mar 02 17:35:26 2009  reduce to 83783 relations and 48307 ideals in 22 passes
Mon Mar 02 17:35:26 2009  max relations containing the same ideal: 15
Mon Mar 02 17:35:29 2009  reading rational ideals above 425984
Mon Mar 02 17:35:29 2009  reading algebraic ideals above 425984
Mon Mar 02 17:35:29 2009  commencing singleton removal, final pass
Mon Mar 02 17:35:34 2009  keeping 102447 ideals with weight <= 20, new excess is 72011
Mon Mar 02 17:35:34 2009  memory use: 4.3 MB
Mon Mar 02 17:35:35 2009  commencing in-memory singleton removal
Mon Mar 02 17:35:35 2009  begin with 84916 relations and 102447 unique ideals
Mon Mar 02 17:35:35 2009  reduce to 3257 relations and 1830 ideals in 13 passes
Mon Mar 02 17:35:35 2009  max relations containing the same ideal: 5
Mon Mar 02 17:35:35 2009  filtering wants 246315 more relations
Mon Mar 02 17:35:35 2009  elapsed time 00:02:20

This is for a C97 from alq(130396.1948), but the "elapsed time" should be 00:12:31. I started on normal priority, but switched it quickly to low. Could this be the cause of the problem?

[Jeff Gilchrist]

Originally Posted by jasonp

PS: Brian Gladman has already pointed out that the MSVC code needs some fixing too, looks like I'll need to post an update tonight.

I haven't had a chance to try the Windows compile yet, but MSVC would build 1.39 but the poly code was broken (in the 64bit version at least) so if he can fix 1.40 that would be a huge benefit.

[jasonp]

Originally Posted by 10metreh

This is for a C97 from alq(130396.1948), but the "elapsed time" should be 00:12:31. I started on normal priority, but switched it quickly to low. Could this be the cause of the problem?

Yes, the code now measures CPU time and not calendar time. I guess the end-to-end time needs to use the wall clock and everything else needs to use CPU elapsed time. You can fight it out with andi47 :)

Jeff, figuring out what's wrong with NFS poly selection in 64-bit MSVC will take remote debugging that I don't have the time to do. THe problems he reported are strictly the result of a lot of churn in the source over the last three months.

[akruppa]

With GMP=1, there are no error messages. It didn't find any polynomial so far, I aborted after 2 hours. Is there something I can do to get some (suboptimal) polynomials quickly, just to see that it works?

Alex

[XYYXF]

Originally Posted by jasonp

- A fix for a typo that made QS a lot slower

So now QS became much faster?