mersenneforum.org NFS Square Root failed
 Register FAQ Search Today's Posts Mark Forums Read

 2019-05-26, 00:46 #1 wreck     "Bo Chen" Oct 2005 Wuhan,China 167 Posts NFS Square Root failed When factoring R507, we meet a problem at the stage of square root. the log is something like Code: Msieve v. 1.54 (SVN 1018) Sat May 25 15:07:05 2019 random seeds: 793bae58 dd6e995c factoring 46802612901958501868841642965751124516436202272587430374287737787818526612306217484595957815607978887434356766596560265669642422106894901815250576734687838908431237216708427946009827065503443998015551 (200 digits) searching for 15-digit factors commencing number field sieve (200-digit input) R0: -489207429141011531399145000684883987953 R1: 4672294682135028058 A0: -1141622752347875247016534173692198727370239170296 A1: 606229025806036192373697162986942868196 A2: 142633534281473766366139546615926 A3: -540694411833242620565099 A4: -2965749858137203 A5: 3340680 skew 269920746.28, size 1.143e-019, alpha -7.036, combined = 4.526e-015 rroots = 3 commencing square root phase handling dependencies 1 to 64 reading relations for dependency 1 read 20047248 cycles cycles contain 70891558 unique relations read 70891558 relations multiplying 70891558 relations GNU MP: Cannot allocate memory (size=4294914080) C:\GNFS507\SU> This computer has 64GB memory, and I look at the task manager each minute. When running msieve, I close most of the other programmes, the free memory is about 50 GB. The maximum memory msieve use is about 6GB. I am not sure why it can not allocate 4.29GB memory. I look at the msieve code, and found that there is a function named multiply_relations, it is a recursive function, in our case, index1 = 0, index2 = 70891557 The maximum recursive depth is about 27. There are frequent memory alloc and free in this function, I am not sure whether there is connection between the 'not enough memory' and frequent alloc and free operation. I also record the memory and CPU msieve use each minutes, Code: CPU MEM Time hint 6.3% 3.075,8 MB 21:08 cycles contains ... 6.5% 3.594,1 MB 21:08 6.3% 4.185,1 MB 21:09 6.1% 5.066,1 MB 21:10 6.7% 8.190,1 MB 21:15 read 70891558 ... 7.1% 9.019,8 MB 21:16 6.4% 1.172,6 MB 21:22 multiplying ... 6.7% 1.492,0 MB 21:24 6.6% 2.072,8 MB 21:29 6.9% 3.025,5 MB 21:55 7.0% 4.275,5 MB 21:58 6.7% 3.261,2 MB 22:13 6.9% 5.005,1 MB 22:36 7.1% 6,045.1 MB 22:39 exit 22:50 GNU MP: Cannot allocate memory (size=4294914080) I am trying to remove the recursive by one by one in function multiply_relations Code: /* remove the recursion, to reduce the memory use. author: boc date:2019-05-25 */ static void multiply_relations(relation_prod_t *prodinfo, uint32 index1, uint32 index2, mpz_poly_t *prod) { /* multiply together the relations from index1 to index2, inclusive. We proceed recursively to assure that polynomials with approximately equal- size coefficients get multiplied, and also to avoid wasting huge amounts of memory in the beginning when all the polynomials are small but the memory allocated for them is large */ uint32 i; mpz_poly_t prod1, prod2; if (index1 == index2) { /* base case of recursion */ relation_to_poly(prodinfo->rlist + index1, prodinfo->c, prod); return; } mpz_poly_init(&prod1); mpz_poly_init(&prod2); if (index1 == index2 - 1) { /* base case of recursion */ /*relation_to_poly(prodinfo->rlist + index1, prodinfo->c, &prod1); relation_to_poly(prodinfo->rlist + index2, prodinfo->c, &prod2); */ } else { /* recursively compute the product of the first half and the last half of the relations */ /* uint32 mid = (index1 + index2) / 2; multiply_relations(prodinfo, index1, mid, &prod1); multiply_relations(prodinfo, mid + 1, index2, &prod2); remove recursive code. */ } relation_to_poly(prodinfo->rlist + index1, prodinfo->c, &prod1); for (i = index1 + 1; i <= index2; i++) { relation_to_poly(prodinfo->rlist + i, prodinfo->c, &prod2); mpz_poly_mul(&prod1, &prod2, prodinfo->monic_poly, 1); } /* multiply them together and save the result */ /* mpz_poly_mul(&prod1, &prod2, prodinfo->monic_poly, 1); */ for (i = 0; i <= prod1.degree; i++) mpz_swap(prod->coeff[i], prod1.coeff[i]); prod->degree = prod1.degree; mpz_poly_free(&prod1); mpz_poly_free(&prod2); } We try to build msieve with this patch without success, could anybody help to build a windows x86_64 msieve binary with this code? This code is at gnfs/sqrt/sqrt_a.c, line 300. My rough guess is that: 1. there are some bad relations in the unique relations; 2. 64GB physical is not enough when factoring a gnfs200. Any suggestion would be appreciate.
 2019-05-26, 05:20 #2 frmky     Jul 2003 So Cal 23×32×29 Posts Try running another dependency. -nc3 2,2 Try in 64-bit Linux. Hmmm....
 2019-05-26, 22:18 #3 ATH Einyen     Dec 2003 Denmark 2×7×223 Posts I'm having trouble compiling the newer svn versions. Here is svn 1018 with your patch, compiled with: make all WIN=1 WIN64=1 ECM=1 CUDA=1 NO_ZLIB=1 VBITS=64 msieve-svn1018patched.zip
 2019-05-28, 00:38 #4 jasonp Tribal Bullet     Oct 2004 33·131 Posts It could be a limit in the number of limbs older versions of GMP are allowed to allocate for a single number.
 2019-05-28, 15:17 #6 DukeBG   Mar 2018 3·43 Posts This probably won't help, but worth trying if you haven't anyway. Did you try doing it after a fresh reboot without any programs working on that machine yet? I.e. the memory is not just free, but also wasn't allocated at all by any other program yet. Maybe it needs a contiguous block of memory to allocate and the free memory is segmented after use (there are actually different kinds of free memory under the hood in windows, but I don't want to get into it right now). Also, is this Windows 10 or some older version of Windows? P.S. 4294914080 bytes is actually slightly below 4GB, not 4.29GB. Last fiddled with by DukeBG on 2019-05-28 at 15:17
 2019-05-28, 22:30 #7 frmky     Jul 2003 So Cal 23·32·29 Posts If you can post the files for download, I can try to run it here.
 2019-05-28, 23:29 #8 Max0526   "Max" Jun 2016 Toronto 13138 Posts doesn't hurt to try safe mode @wreck I had a similar (not the same) problem with msieve long time ago. My message said "reallocate" instead of "allocate". Booting Windows into safe mode helped that time. Ask Kurt to boot his Win 10 into safe boot mode: https://pureinfotech.com/safe-mode-w..._mode_msconfig and retry solving one of the dependencies. That might help. Worth a try and 2 hours instead of 1500 hours to rebuild the matrix, I guess. I also very much doubt that four bad relations can screw up all the work so far. Does msieve not ignore them anyways?
 2019-05-28, 23:43 #9 jasonp Tribal Bullet     Oct 2004 33·131 Posts Note also that when a GNFS job gets its relations multiplied together, each relation contributes the leading algebraic coefficient to the product, and this is always larger than the leading algebraic coefficient in SNFS jobs. So the size of the numbers to be multiplied is going to be a lot larger for GNFS jobs. Are you sure you are linking to a 64-bit GMP when building?
 2019-05-28, 23:57 #10 Max0526   "Max" Jun 2016 Toronto 5×11×13 Posts GMP -param 0 Is there a chance to rebuild msieve with "-param 0" option for GMP? There is a post from 2016 describing the problem in detail: https://www.mersenneforum.org/showpo...04&postcount=6 (also read the beginning of the thread)
 2019-05-29, 05:41 #11 ATH Einyen     Dec 2003 Denmark C3216 Posts -param 0 is a runtime option for GMP-ECM, not a build option for GMP or GMP-ECM.

 Similar Threads Thread Thread Starter Forum Replies Last Post chris2be8 Msieve 13 2020-10-14 07:08 davar55 Lounge 0 2016-03-16 20:19 bsquared Msieve 17 2010-04-09 14:11 Damian Math 3 2010-01-01 01:56 davar55 Puzzles 3 2007-09-05 15:59

All times are UTC. The time now is 09:23.

Thu May 6 09:23:25 UTC 2021 up 28 days, 4:04, 0 users, load averages: 1.61, 1.51, 1.47