20190526, 00:46  #1 
"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 15digit factors commencing number field sieve (200digit input) R0: 489207429141011531399145000684883987953 R1: 4672294682135028058 A0: 1141622752347875247016534173692198727370239170296 A1: 606229025806036192373697162986942868196 A2: 142633534281473766366139546615926 A3: 540694411833242620565099 A4: 2965749858137203 A5: 3340680 skew 269920746.28, size 1.143e019, alpha 7.036, combined = 4.526e015 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> 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) Code:
/* remove the recursion, to reduce the memory use. author: boc date:20190525 */ 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); } 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. 
20190526, 05:20  #2 
Jul 2003
So Cal
2^{3}×3^{2}×29 Posts 
Try running another dependency. nc3 2,2
Try in 64bit Linux. Hmmm.... 
20190526, 22:18  #3 
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 msievesvn1018patched.zip 
20190528, 00:38  #4 
Tribal Bullet
Oct 2004
3^{3}·131 Posts 
It could be a limit in the number of limbs older versions of GMP are allowed to allocate for a single number.

20190528, 12:58  #5 
"Bo Chen"
Oct 2005
Wuhan,China
167 Posts 
I use the following command to start dep 2.
msievesvn1018cuda75sandybridge.exe i R507.ini l R507.log s part08042.out nf R507.fb nc3 "target_density=130 dep_first=16 dep_last=32" v t 16 That command start reading relations for dependency 16, cycles 20047610, 70899836 relations, crash after message GNU MP:Cannot allocate memory(size=4294914080) then I change it to dep 2 and remove option t 16, cycles 20043584, 70876804 relations, crash after the same message. Then I change it to dep 3, cycles 20049917, 70882146 relations, crash after same message. the cpu is i77820X which is Skylake structure, I download msievesvn1018cuda75haswell.exe from mersenneforum which upload by ATH, and change to dep 4, cycles 20042681, 70882146 relations, crash after same message. I ask ATH to help me compile a new binary with the code patch I provide, and ask Kurt to do nc3, crash again. We factor R447, R1030, R2700M, R343,R423 in the past 3 years, where R1030,R2700M,R343,R423 is factored by version "Msieve v.1.5.3 (SVN unknown)", R447 is factored by "Msieve v.1.5.4 (SVN 1018)", I guess R507 ' s nc1 and nc2 is the same as R447. There is 3 point I cannot understand, 1. R447 is snfs300, its nc3 size is similar with R507, only less than 1M relations, why it not crash? 2. R1030 is gnfs199, and its nc3 relation is about 1.5 larger than R507, if GMP memory count here, why R1030 not crash? 3. When we do the sieve R343, there is s version 997 binary post on mersenneforum, I ask Kurt give it a try, but it crash when doing nc2, whereas version "Msieve v.1.5.3 (SVN unknown)" still works. I dont know where is the difference. I ask Kurt sieve 30M more relations, use remdup, use "Msieve v.1.5.3",option density 120 to do nc1 nc2 nc3 again, to avoid bad relation, not enough memory,binary issue.The headache is that this try will take more than 1500 hours. About linux, I have access Ubuntu 16.04 less than 4 hours, 8GB memory, it could not use to do msieve postprocessing. Kurt's computer(i7,64GB) is Win10, no linux system, I am not sure whether he could install Ubuntu, he also use this computer to do other reality things, so perhaps he may has some inconvienence if use ubuntu. Thanks again to all. Last fiddled with by wreck on 20190528 at 13:03 
20190528, 15:17  #6 
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 20190528 at 15:17 
20190528, 22:30  #7 
Jul 2003
So Cal
2^{3}·3^{2}·29 Posts 
If you can post the files for download, I can try to run it here.

20190528, 23:29  #8 
"Max"
Jun 2016
Toronto
1313_{8} 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/safemodew..._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? 
20190528, 23:43  #9 
Tribal Bullet
Oct 2004
3^{3}·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 64bit GMP when building? 
20190528, 23:57  #10 
"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) 
20190529, 05:41  #11 
Einyen
Dec 2003
Denmark
C32_{16} Posts 
param 0 is a runtime option for GMPECM, not a build option for GMP or GMPECM.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
All square roots failed  chris2be8  Msieve  13  20201014 07:08 
Square Root Days  davar55  Lounge  0  20160316 20:19 
square root crash  bsquared  Msieve  17  20100409 14:11 
Square root of 3  Damian  Math  3  20100101 01:56 
Divisible up to Square Root  davar55  Puzzles  3  20070905 15:59 