Assertion failure in 6.4.2

bsquared · 2013-02-28, 14:49

I ran across this in a recent build of 6.4.2 on win64 (using mingw-64):

Code:

PS S:\buhrow\ecm> echo 29747206910618763758463717487845886566632171552367213138044002990307740389645131368265139
1296916693853371361416178104220163452801113422142557346757459 | ..\gmp-ecm\bin\x64\Release\ecm.exe -pm1 15000000
GMP-ECM 6.4.2 [configured with GMP 5.1.1, --enable-asm-redc] [P-1]
Input number is 29747206910618763758463717487845886566632171552367213138044002990307740389645131368265139129691669385337
1361416178104220163452801113422142557346757459 (150 digits)
Using B1=15000000, B2=200794064686, polynomial x^1, x0=221988447
Step 1 took 4461ms
Assertion failed: h < pl, file mul_fft.c, line 2500

This application has requested the Runtime to terminate it in an unusual way.
Please contact the application's support team for more information.

make check said that All ECM tests are ok.

Is this maybe related to this?

akruppa · 2013-03-01, 12:52

No, this assertion is from the Schönhage-Strassen code that we use with Kronecker-Schönhage polynomial multiplication alternatively to the NTT. I don't think we've seen this bug before.

The code tries to compute a product n*m by computing n*m (mod 2^N-1) and n*m (mod 2^(aN)+1), a >= 1, and putting together the pieces by CRT. The assertion tests that the number of words h in 2^(aN) is less than the number of words pl in the product; if it isn't, then the parameter selection is obviously sub-optimal. As far as I can tell, the computed product should still be correct, so it should not be an ASSERT_ALWAYS - failing that condition is not a show stopper.

Can you please send/post your ecm-params.h file, or if it is one of the package's params file, tell me which? Then maybe I can reproduce why it chose the transform parameters so poorly.

bsquared · 2013-03-01, 14:54

Quote:

Originally Posted by akruppa

No, this assertion is from the Schönhage-Strassen code that we use with Kronecker-Schönhage polynomial multiplication alternatively to the NTT. I don't think we've seen this bug before.

The code tries to compute a product n*m by computing n*m (mod 2^N-1) and n*m (mod 2^(aN)+1), a >= 1, and putting together the pieces by CRT. The assertion tests that nm < 2^(aN); if it isn't, then the parameter selection is obviously sub-optimal. As far as I can tell, the computed product should still be correct, so it should not be an ASSERT_ALWAYS - failing that condition is not a show stopper.

Can you please send/post your ecm-params.h file, or if it is one of the package's params file, tell me which? Then maybe I can reproduce why it chose the transform parameters so poorly.

I guess I neglected the "make ecm-params; make" step... here is ecm-params.h

Code:

/* those parameters were obtained on toto.loria.fr with ecm-6.3-rc3
   gmp-5.0.1, and gcc 4.0.2 -m32 -O2 -pedantic -fomit-frame-pointer -mtune=pentium3 -march=pentium3 */
#define TUNE_MULREDC_THRESH 1
#define TUNE_SQRREDC_THRESH 1
#define MPZMOD_THRESHOLD 98
#define REDC_THRESHOLD 398
#define MPN_MUL_LO_THRESHOLD_TABLE {0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 10, 1, 1, 12, 12, 1, 14, 12, 13, 1, 15, 16, 15, 16, 19, 20, 22}
#define NTT_GFP_TWIDDLE_DIF_BREAKOVER 17
#define NTT_GFP_TWIDDLE_DIT_BREAKOVER 17
#define MUL_NTT_THRESHOLD 1024
#define PREREVERTDIVISION_NTT_THRESHOLD 16
#define POLYINVERT_NTT_THRESHOLD 256
#define POLYEVALT_NTT_THRESHOLD 512
#define MPZSPV_NORMALISE_STRIDE 1024

ET_ · 2013-03-01, 15:33

Does the result of "make ecm-params" vary when the PC in test has lots of CPU used by other processes?

Luigi

akruppa · 2013-03-01, 15:52

It uses getrusage() to get cpu time, which theoretically counts only the time the program actually executes and should not be affected (much) by the process being suspended to let other processes run. Telling apart the various processes' time on the cpu is not perfect, however, and then there are effects like delay from having to fetch data into cache again which was displaced during another process's time slice... in practice, it is noticeably affected. Digression: getting reproducible timings can be fairly tricky; to time short loops I found I get the best results without graphical desktop, with irq balancer disabled and binding the process to a cpu other than 0, so it does not get interrupted as much.

TL;DR: timings probably vary less if one or two cpus are "free."

2013-03-01, 12:52	#2
akruppa "Nancy" Aug 2002 Alexandria 9A3₁₆ Posts	No, this assertion is from the Schönhage-Strassen code that we use with Kronecker-Schönhage polynomial multiplication alternatively to the NTT. I don't think we've seen this bug before. The code tries to compute a product nm by computing nm (mod 2^N-1) and nm (mod 2^(aN)+1), a >= 1, and putting together the pieces by CRT. The assertion tests that the number of words h in 2^(aN) is less than the number of words pl in the product; if it isn't, then the parameter selection is obviously sub-optimal. As far as I can tell, the computed product should still be correct, so it should not be an ASSERT_ALWAYS - failing that condition is not a show stopper. Can you please send/post your ecm-params.h file, or if it is one of the package's params file, tell me which? Then maybe I can reproduce why it chose the transform parameters so poorly. Last fiddled with by akruppa on 2013-03-01 at 15:38 Reason: clarification of the condition*

2013-03-01, 15:33	#4
ET_ Banned "Luigi" Aug 2002 Team Italia 3×1,619 Posts	make ecm-params Does the result of "make ecm-params" vary when the PC in test has lots of CPU used by other processes? Luigi

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
GMP-ECM 7.0-dev assertion failed!	Antonio	GMP-ECM	9	2015-03-10 08:21
Assertion failed	Andi47	GMP-ECM	2	2009-08-04 14:11
GMP-ECM Assertion	yoyo	GMP-ECM	8	2009-01-16 20:57
LA Failure	R.D. Silverman	NFSNET Discussion	10	2007-05-23 21:53
Failure Functioins	Unregistered	Miscellaneous Math	0	2004-02-12 11:51

2013-03-01, 15:52	#5
akruppa "Nancy" Aug 2002 Alexandria 2,467 Posts	It uses getrusage() to get cpu time, which theoretically counts only the time the program actually executes and should not be affected (much) by the process being suspended to let other processes run. Telling apart the various processes' time on the cpu is not perfect, however, and then there are effects like delay from having to fetch data into cache again which was displaced during another process's time slice... in practice, it is noticeably affected. Digression: getting reproducible timings can be fairly tricky; to time short loops I found I get the best results without graphical desktop, with irq balancer disabled and binding the process to a cpu other than 0, so it does not get interrupted as much. TL;DR: timings probably vary less if one or two cpus are "free."