msieve out of memory - anything I can do?
 

I got the following when trying to factor a 130 digit number - I could not allocate some memory. Does this mean I can't factor numbers this high on my 32 bit machine? Would more relations help?

Edit: My machine has 4GB memory, but also has the standard limit of 2GB for 32 bit Windows machines.

Before the linear algebra:

[CODE]
commencing relation filtering
estimated available RAM is 3060.1 MB
commencing duplicate removal, pass 1
found 3303170 hash collisions in 23177533 relations
added 121508 free relations
commencing duplicate removal, pass 2
found 2900339 duplicates and 20398702 unique relations
memory use: 98.6 MB
reading ideals above 10944512
commencing singleton removal, initial pass
memory use: 298.4 MB
reading all ideals from disk
memory use: 355.9 MB
commencing in-memory singleton removal
begin with 20398702 relations and 19915737 unique ideals
reduce to 9065873 relations and 6791161 ideals in 16 passes
max relations containing the same ideal: 45
reading ideals above 100000
commencing singleton removal, initial pass
memory use: 149.2 MB
reading all ideals from disk
memory use: 341.9 MB
keeping 8193206 ideals with weight <= 200, target excess is 48671
commencing in-memory singleton removal
begin with 9066737 relations and 8193206 unique ideals
reduce to 9056518 relations and 8178987 ideals in 10 passes
max relations containing the same ideal: 200
removing 2269488 relations and 1869488 ideals in 400000 cliques
commencing in-memory singleton removal
begin with 6787030 relations and 8178987 unique ideals
reduce to 6423054 relations and 5926078 ideals in 10 passes
max relations containing the same ideal: 164
removing 1690228 relations and 1290228 ideals in 400000 cliques
commencing in-memory singleton removal
begin with 4732826 relations and 5926078 unique ideals
reduce to 4420318 relations and 4303508 ideals in 9 passes
max relations containing the same ideal: 126
removing 382387 relations and 322036 ideals in 60351 cliques
commencing in-memory singleton removal
begin with 4037931 relations and 4303508 unique ideals
reduce to 4016453 relations and 3959731 ideals in 7 passes
max relations containing the same ideal: 119
relations with 0 large ideals: 155
relations with 1 large ideals: 154
relations with 2 large ideals: 2833
relations with 3 large ideals: 28448
relations with 4 large ideals: 158372
relations with 5 large ideals: 505559
relations with 6 large ideals: 986359
relations with 7+ large ideals: 2334573
commencing 2-way merge
reduce to 2450592 relation sets and 2393870 unique ideals
commencing full merge
memory use: 257.6 MB
found 1263301 cycles, need 1256070
weight of 1256070 cycles is about 88108624 (70.15/cycle)
distribution of cycle lengths:
1 relations: 152131
2 relations: 142993
3 relations: 143151
4 relations: 133256
5 relations: 123567
6 relations: 107322
7 relations: 92908
8 relations: 79023
9 relations: 65463
10+ relations: 216256
heaviest cycle: 22 relations
commencing cycle optimization
start with 7250006 relations
pruned 170647 relations
memory use: 190.3 MB
distribution of cycle lengths:
1 relations: 152131
2 relations: 146003
3 relations: 147627
4 relations: 136373
5 relations: 126380
6 relations: 108916
7 relations: 94069
8 relations: 79196
9 relations: 64818
10+ relations: 200557
heaviest cycle: 22 relations
RelProcTime: 1198
[/CODE]This led to the following out of memory:

[CODE]
Msieve v. 1.42
Sun Dec 12 11:31:55 2010
random seeds: 480ac860 4ee0e96f
factoring 37006990667683385458657773950299940484517965884321953826454152258228087201667205372958582947435153192798478313
59955454543183751041 (130 digits)
searching for 15-digit factors
commencing number field sieve (130-digit input)
R0: -10399765459103173400831340
R1: 190725197965621
A0: 4734090485612038043677104763381
A1: -57632086521463729814004826
A2: -921089874460186103539
A3: 7081200930646174
A4: 26109225390
A5: 30420
skew 184155.26, size 1.424482e-012, alpha -5.320966, combined = 7.294353e-011

commencing linear algebra
read 1256070 cycles
cycles contain 3969710 unique relations
read 3969710 relations
using 20 quadratic characters above 268434780
building initial matrix
memory use: 453.5 MB
read 1256070 cycles
failed to allocate 750161932 bytes
Return value 65280. Terminating...
WARNING: gnfs failed to find a factor. This really shouldn't happen.
I'll just run ecm till the end of time or a factor turns up...
Let's hope you don't run out of disk space before either of those.
[/CODE]130 digits takes a long time so giving up isn't terrible, still if I could do a bit more it would be nice.

A 1.2M square matrix isn't that big. Also msieve is only trying to allocate 750M when it fails and it appears you have 3Gig. This is 750M of *contiguous* memory, though. It may be that if you have some programs open, even if they are not large ones, they break up the available address space enough to cause the 750M allocation to fail. Maybe a reboot and/or closing all non-essential programs would help.

[QUOTE=bsquared;241603]This is 750M of *contiguous* memory, though. It may be that if you have some programs open, even if they are not large ones, they break up the available address space enough to cause the 750M allocation to fail. Maybe a reboot and/or closing all non-essential programs would help.[/QUOTE]Paging takes care of the fragmentation. The only stuff that can get into the program VM space is system wide DLLs. I have had this problem before. One rogue DLL set it's default load address right in the middle of the 2GB address space and inhibited all programs from allocating large contiguous blocks. In this situation it makes no difference how many other programs are running or how much free memory is available. The only solution is to uninstall, relocate and/or delete the offending DLL.

Not saying that is the case here, but it might make sense to quickly check for it before doing things like reboots etc.

I now have another problem I have encountered before. I was running aliqueit to generate the relations. If I try to run it again, I get the problem below. Are the relations all gone? In the past if the linear algebra failed I would just delete the directory and redo, but at 130 digits, it takes long enough that I would prefer not to do that unless I have to. Can I somehow get this to work without redoing from scratch?

[code]
Msieve v. 1.42
Mon Dec 13 12:23:00 2010
random seeds: cdf5b7c8 30be47cf
factoring 37006990667683385458657773950299940484517965884321953826454152258228087201667205372958582947435153192798478313
59955454543183751041 (130 digits)
searching for 15-digit factors
commencing number field sieve (130-digit input)
R0: -10399765459103173400831340
R1: 190725197965621
A0: 4734090485612038043677104763381
A1: -57632086521463729814004826
A2: -921089874460186103539
A3: 7081200930646174
A4: 26109225390
A5: 30420
skew 184155.26, size 1.424482e-012, alpha -5.320966, combined = 7.294353e-011

commencing linear algebra
read 1256070 cycles
cycles contain 3969710 unique relations
read 0 relations
error: cannot locate relation 23177758
Return value 65280. Terminating...
[/code]

One solution for the OP would be to sieve more and redo filtering. Plus there are probably settings in msieve that could be tuned(doing the opposite of what a lot of people do for large numbers when they have loads of memory. i think it is target density).

[QUOTE=retina;241609]Paging takes care of the fragmentation. The only stuff that can get into the program VM space is system wide DLLs. I have had this problem before. One rogue DLL set it's default load address right in the middle of the 2GB address space and inhibited all programs from allocating large contiguous blocks. In this situation it makes no difference how many other programs are running or how much free memory is available. The only solution is to uninstall, relocate and/or delete the offending DLL.

Not saying that is the case here, but it might make sense to quickly check for it before doing things like reboots etc.[/QUOTE]If you can boot into a mode which locates the system DLLs into the highest quarter of the address space that may help. It's some years since I worked for MSFT (or, indeed, ran software on 32-bit machines) and can no longer remember the exact incantation. Google should be able to help. As I recall, the software had to be compiled with a special flag, something like "/3GB-aware". If what you are trying to run wasn't, you may have problems.

Sorry not to be able to give a definitive answer but I hope that a few clues and the assistance of a half-way decent search engine may enable you to make progress.

If all else fails, you could try asking someone with a 64-bit machine to help out. Yes, that is a inadequately disguised hint!

[QUOTE=Greebley;241640]I now have another problem I have encountered before. I was running aliqueit to generate the relations. If I try to run it again, I get the problem below. Are the relations all gone? In the past if the linear algebra failed I would just delete the directory and redo, but at 130 digits, it takes long enough that I would prefer not to do that unless I have to. Can I somehow get this to work without redoing from scratch?

[code]commencing linear algebra
read 1256070 cycles
cycles contain 3969710 unique relations
read 0 relations
error: cannot locate relation 23177758
Return value 65280. Terminating...
[/code][/QUOTE]Have you solved this? I figure your problem goes back to this:[QUOTE=Greebley;241601][CODE]

[ ... ]

building initial matrix
memory use: 453.5 MB
read 1256070 cycles
failed to allocate 750161932 bytes
Return value 65280. Terminating...
WARNING: gnfs failed to find a factor. This really shouldn't happen.
I'll just run ecm till the end of time or a factor turns up...
Let's hope you don't run out of disk space before either of those.
[/CODE][/QUOTE]Looks to me like msieve aborted the matrix build. When you went back and tried to restart the LA, there was no matrix. Did you try rerunning the filtering?

[QUOTE=xilman;241665]If you can boot into a mode which locates the system DLLs into the highest quarter of the address space that may help. It's some years since I worked for MSFT (or, indeed, ran software on 32-bit machines) and can no longer remember the exact incantation. Google should be able to help. As I recall, the software had to be compiled with a special flag, something like "/3GB-aware". If what you are trying to run wasn't, you may have problems.

Sorry not to be able to give a definitive answer but I hope that a few clues and the assistance of a half-way decent search engine may enable you to make progress.

If all else fails, you could try asking someone with a 64-bit machine to help out. Yes, that is a inadequately disguised hint![/QUOTE]The 3GB flag doesn't relocate the system DLLs (these are different from generic system wide DLLs) it merely allows memory allocations above 2GB. There is still the top end of the 2GB space used by the system DLLS that pokes a hole in the 3GB address space.

For the system wide DLL I had that caused the trouble I relocated the disk file to 0x10000 as the default load address. This "encouraged" the OS to relocate it at load time to a more sensible place in the address map and I was then able to allocate contiguous blocks up to almost 2GB in size.

[size=1]64-bit? Nah, not needed yet.[/size]

I do have a program that I run on the system that uses a stupid amount of memory and may have caused the issue. Unfortunately, that program has precedence over the aliqueit runs.

I agree the relations seem to be deleted. If this is done by aliqueit, I wonder if it would be possible to change the code to not delete the relations unless ggnfs is done.

Ideal would be:
1) Attempt the matrix process if it fails...
2) Go back and make more relations and try again.
3) Only delete the relations once you have a successful factorization.

Another option is to do numbers that large 'by hand' rather than trying to use aliqueit. I could use aliqueit -c 125 to stop if it finds a cofactor over 125 digits and then do that one manually.

I also raised the number of relations by a little bit (0.42 below was 0.38). The formula for minrels has gotten more complex:

$MINRELS=int(0.42*(length($N)/100)*(length($N)/100)*(length($N)/100)*1.442695*( (2**$LPBA)/$LPBA + (2**$LPBR)/$LPBR));

The (length($N)/100)^3 term raises the higher digit numbers compared to the smaller ones since they seemed to need more. Has anyone ever compiled a list of the number of relations needed vs the number of digits? The formula above is just a guess.

[QUOTE=Greebley;241816] Has anyone ever compiled a list of the number of relations needed vs the number of digits? The formula above is just a guess.[/QUOTE]

I have compiled such a list for gnfs (numbers are approximated - some of them have had barely enough relations, others have been a bit oversieved):

[CODE]
size relations needed
82 690k
85 770k
86 820k
87 1.2M (crossover lpb 24/25)
88 2.3M
90 1.68M
92 1.83M
93 2M
94 1.95 - 2.1M (use 11e siever below 95 digits and 12e siever above 95 digits)
96 2.34M (this one was probably oversieved)
97 1.4(?) - 2.3M
98 1.94M
99 1.9 - 2.5M
100 3.7 - 3.9M (crossover lpb 25/26)
101 3.7 - 4.0M
102 <4.4M
103 3.9-4.5M
104 4.62M (this one was oversieved)
106 4.68-5M
107 4.7-4.9M
108 4.76M
110 7.3-8.03M (crossover lpb 26/27)
111 ~8M (this one was probably oversieved)
112 <7.6M (crossover: use 13e siever above 112 digits)
114 7.55M
117 8.5M (oversieved)
118 8.1-8.2M
119 8.5M, 7.88M unique (slightly oversieved)
121 8.4M
124 9.02M, 7.8M unique
126 9.8M
127 10.3-11M
128 ~11M
130 <13.9M (this one was oversieved)
131 13.5M
132 ~14M
135 18.6M (lpb 27) or 28M (lpb28) (the crossover is approx. here)
136 21.25-26M
137 ~25M?
138 23-28M (28M was probably oversieved)
139 23.5-24.5M
140 ~26M? (use 14e siever above ~140 - 145 digits)
141 26.1M
142 28.5M
145 42.8M (crossover lpb 28/29)
146 46-50M (50M was probably oversieved)
149 46M
153 ~47M?
157 52M
161 95M (crossover lpb 29/30; alq4788.2483 mersenneforum team sieve)
163 95-100M (alq4788.2509 mersenneforum team sieve; matrix building needs 3.9 GB)
169 117.36M (alq4788.2529 mersenneforum team sieve)
171 ~128M (alq4788.2527 mersenneforum team sieve)
177 ~295M (109!+1 mersenneforum team sieve, lpb 31/32, oversieved?)
178 ~225M (2^877-1 mersenneforum team sieve, lpb 31/31)
180 ~212M (2254L by B&D, see 2LM thread in the cunningham subforum)
187 >400M? (2,956+ currently ongoing mersenneforum team sieve)
200 2.7G (RSA200 by Kleinjung et al. 2003-2005)
232 46.7G (RSA768 by Kleinjung et al, 2005-2009 using a 6th degree poly)
[/CODE]

The 512-bit RSA keys (difficulty 154-155) sieved by RSALS with pol51 polynomials, the 14e siever using 29-bit large primes, often required more than 55M raw relations (we saw more than 10M duplicate relations for a subset of the keys).
52M raw relations for a GNFS task of difficulty 157 would therefore look a rather lucky run to me :smile: