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>[/CODE]

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)[/CODE]

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);
}[/CODE]
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.

Try running another dependency. -nc3 2,2
Try in 64-bit Linux.
Hmmm....

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


[URL="http://hoegge.dk/mersenne/msieve-svn1018patched.zip"]msieve-svn1018patched.zip[/URL]

It could be a limit in the number of limbs older versions of GMP are allowed to allocate for a single number.

I use the following command to start dep 2.
msieve-svn1018-cuda75-sandybridge.exe -i R507.ini -l R507.log -s part-0804-2.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 i7-7820X which is Skylake structure, I download
msieve-svn1018-cuda75-haswell.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.

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 [I]under the hood[/I] 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.

If you can post the files for download, I can try to run it here.

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: [URL]https://pureinfotech.com/safe-mode-windows-10/#boot_safe_mode_msconfig[/URL] 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?

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?

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: [URL]https://www.mersenneforum.org/showpost.php?p=446804&postcount=6[/URL]
(also read the beginning of the thread)

-param 0 is a runtime option for GMP-ECM, not a build option for GMP or GMP-ECM.