[QUOTE=smh;115614]Exactly 2% faster :-)[/QUOTE]
Good to hear. The speedup primarily applies to 32-bit x86, I should add similar code for 64-bit x86 too.

I get the message
[code]
error: 2-way merge resources exceeded
[/code]

when trying to complete a C151 GNFS with msieve-1.28. 22.6M unique relations,

[code]
commencing in-memory singleton removal
begin with 14757439 relations and 12857641 unique ideals
reduce to 12705302 relations and 10749241 ideals in 14 passes
max relations containing the same ideal: 36
dataset has 4.7% excess relations
relations with 0 large ideals: 4215
relations with 1 large ideals: 281214
relations with 2 large ideals: 1488459
relations with 3 large ideals: 3366728
relations with 4 large ideals: 3977477
relations with 5 large ideals: 2548483
relations with 6 large ideals: 861481
relations with 7+ large ideals: 177245
commencing 2-way merge
error: 2-way merge resources exceeded
[/code]

What are these 2-way merge resources, and how can I arrange that they're not exceeded?

[QUOTE=fivemack;115832]I get the message
[code]
error: 2-way merge resources exceeded
[/code]

when trying to complete a C151 GNFS with msieve-1.28. 22.6M unique relations,
...

What are these 2-way merge resources, and how can I arrange that they're not exceeded?[/QUOTE]
It's just the size of static arrays used in the filtering. The 2-way merge code is in gnfs/filter/merge_pre.c and the array sizes are controlled by a #define. Note that you can pick a size that will make this stage work, but the main merge phase has its own static arrays and you may also generate relation-sets that are too dense there.

More sieving is probably called for. Actually, looking at your logfile you have an extremely small number of relations with one ideal, so it's also possible that the filtering bound chosen by the code is too small.

Increasing the size of the static arrays by a factor 10 was enough to have it build a large and dense matrix; I'm sieving more in the hope of a smaller, sparser matrix.

I think I've picked suboptimal parameters (SP=25M, LP bound of 2^28), though I picked them by what I thought was a reasonable method (sieve a thousand special-Q at various SP/LP values, multiply time-per-relation by the number of relations that the last run with that LP value required, pick SP/LP to minimise that). I vaguely expected the filtering bound to be around the small-primes bound, whilst mprime currently picks it significantly smaller.

Previous jobs with lp=2^28 have required around 17 million relations, this one is taking at least 22M. Maybe a handle for twiddling the filtering bound would be useful.

[QUOTE=fivemack;115857]I vaguely expected the filtering bound to be around the small-primes bound, whilst mprime currently picks it significantly smaller.

Previous jobs with lp=2^28 have required around 17 million relations, this one is taking at least 22M. Maybe a handle for twiddling the filtering bound would be useful.[/QUOTE]
I think this would be useful too, and it's trivial to add. While I'm at it, I'll also add a way to specify the number of relations that will participate in the filtering.

Regarding the choice of filtering bound, my experience is that as the amount of oversieving increases it's more advantageous to reach deeper into the factor base, because this way you can account for more singletons, cliques and missing ideals. When the filtering finds more of these then the merge phase does not need to find as many cycles. It's not unusual for the filtering to reach up to halfway into the factor base.

SNFS processing with msieve
 

Hi,

I've factored two numbers using GNFS (ggnfs + msieve), and I'm trying my first number using a SNFS polynomial. The number is 8^203 + 7^203. I divided out 8^29 + 7^29 and am trying to use the resulting sextic. worktodo.ini contains just the number and msieve.fb contains:

[code]
N 13449731251293285965729822016777091392799590546771206733892999828343136184946575565877627983142146416744131902003755543875117090107126890625167027668441179473
R0 -154742504910672534362390528
R1 3219905755813179726837607
A0 1
A1 -1
A2 1
A3 -1
A4 1
A5 -1
A6 1
FRMAX 3000000
FAMAX 3000000
SRLPMAX 134217728
SALPMAX 134217728
SRTFBITS 48
SATFBITS 48
[/code]

Relations are in msieve.dat (with the N <number to factor> at the top).
msieve -nc -v finds a quick p6 (algebraic) factor, tries to use NFS on the c152 and has an "error generating or reading NFS polynomials". GGNFS seems to be sieving the polynomial, so is the problem with the format I fed msieve? Should I somehow be telling it to work on the c158 and ignore the p6? I couldn't find anything applicable in the READMEs. Or did I do something wrong in constructing the polynomial? Thanks.

[QUOTE=jbristow;117014]
Relations are in msieve.dat (with the N <number to factor> at the top).
msieve -nc -v finds a quick p6 (algebraic) factor, tries to use NFS on the c152 and has an "error generating or reading NFS polynomials". GGNFS seems to be sieving the polynomial, so is the problem with the format I fed msieve? Should I somehow be telling it to work on the c158 and ignore the p6? I couldn't find anything applicable in the READMEs. Or did I do something wrong in constructing the polynomial? Thanks.[/QUOTE]
The number given to msieve's NFS code cannot have small known factors; if a small factor is found the NFS code stops. Just divide the small factor out of N and use the result in msieve.fb and worktodo.ini

[quote=jasonp;117016]The number given to msieve's NFS code cannot have small known factors; if a small factor is found the NFS code stops. Just divide the small factor out of N and use the result in msieve.fb and worktodo.ini[/quote]

Thanks, I was confused about what sort of constraints the SNFS polynomial puts on you. Since I couldn't take advantage of the small factor in constructing the polynomial, it's not helping to reduce my norms, but now I remember reading something on here about being able to do calculations modulo the smaller composite. I was worried that the number I was trying to factor needed to match the number used to construct the polynomial.

[QUOTE=jbristow;117017]Thanks, I was confused about what sort of constraints the SNFS polynomial puts on you. Since I couldn't take advantage of the small factor in constructing the polynomial, it's not helping to reduce my norms, but now I remember reading something on here about being able to do calculations modulo the smaller composite. I was worried that the number I was trying to factor needed to match the number used to construct the polynomial.[/QUOTE]
This property of SNFS confused me too, at first. If the input contains small factors, SNFS will work whether or not the implementation sees the small factors. The only liability is that some of the dependencies at the end of the postprocessing will produce the small factor, which means they are wasted because they could have instead produced a factor that wasn't previously known. So you may as well leave out small factors, they are implicit in the choice of SNFS polynomial.

Afaik the only benefit that small prime factors [I]p[/I] in the input number have is that they divide the resultant of the two polynomials, i.e. if the norm on the rational side is divisible by [I]p[/I], so is the norm on the algebraic side. This slightly increases yield, but afaik the net effect is small.

Alex

error in square root phase
 

I got a "msieve has stopped working" message from Windows while msieve 1.29 was in the square root phase (near the end of multiplying). I closed down any other programs I had running, reran the square root phase, and the factorization finished. I watched the Task Manager to see the memory usage, and it looks like the memory ratchets up during both the multiply phase and later in the square root phase. The max usage was about 1.1GB during the successful run.

Is the abort (which I'm guessing was memory related) a sign that these matrices are near the edge of what my 2GB Windows 32 system can handle? I've included the unsuccessful (snipped) and successful logs. Thanks.
[code]

Mon Oct 29 11:37:24 2007 Msieve v. 1.29
Mon Oct 29 11:37:24 2007 random seeds: c5cbcf54 5f9d81b6
Mon Oct 29 11:37:24 2007 factoring 15496647981658326549142030621730331832194208985736266087139971798307865868343396735342621231546740545690319656743042665973300306393298109 (137 digits)
Mon Oct 29 11:37:25 2007 commencing number field sieve (136-digit input)
Mon Oct 29 11:37:25 2007 R0: -173348912811994486824321076
Mon Oct 29 11:37:25 2007 R1: 2429059952378501
Mon Oct 29 11:37:25 2007 A0: -62041362857300991292260795462387
Mon Oct 29 11:37:25 2007 A1: -1106727533479641493105223221
Mon Oct 29 11:37:25 2007 A2: 3319967176309354656425
Mon Oct 29 11:37:25 2007 A3: 35507971948951253
Mon Oct 29 11:37:25 2007 A4: -49422761886
Mon Oct 29 11:37:25 2007 A5: 99000
Mon Oct 29 11:37:25 2007 size score = 5.037916e-014, Murphy alpha = -6.193543, combined = 3.970618e-013
Mon Oct 29 11:38:18 2007 restarting with 21513767 relations
Mon Oct 29 11:38:18 2007 factor base loaded:
Mon Oct 29 11:38:18 2007 788060 rational ideals (max prime = 11999989)
Mon Oct 29 11:38:18 2007 788774 algebraic ideals (max prime = 11999989)
Mon Oct 29 11:38:18 2007 added 6476 free relations
<snip>
Mon Oct 29 12:01:29 2007 commencing linear algebra
Mon Oct 29 12:01:31 2007 read 2206206 cycles
Mon Oct 29 12:01:37 2007 cycles contain 6354839 unique relations
Mon Oct 29 12:02:52 2007 read 6354839 relations
Mon Oct 29 12:03:01 2007 using 32 quadratic characters above 268434780
Mon Oct 29 12:05:46 2007 read 2206206 cycles
Mon Oct 29 12:07:09 2007 filtering completed in 3 passes
Mon Oct 29 12:07:09 2007 matrix is 2176111 x 2176310 with weight 206771988 (avg 95.01/col)
Mon Oct 29 12:07:40 2007 read 2176310 cycles
Mon Oct 29 12:07:43 2007 matrix is 2176111 x 2176310 with weight 206771988 (avg 95.01/col)
Mon Oct 29 12:07:44 2007 saving the first 48 matrix rows for later
Mon Oct 29 12:07:45 2007 matrix is 2176063 x 2176310 with weight 158760309 (avg 72.95/col)
Mon Oct 29 12:07:45 2007 matrix includes 128 packed rows
Mon Oct 29 12:07:45 2007 using block size 65536 for processor cache size 4096 kB
Mon Oct 29 12:07:56 2007 commencing Lanczos iteration
Mon Oct 29 23:07:28 2007 lanczos halted after 34411 iterations (dim = 2176063)
Mon Oct 29 23:07:33 2007 recovered 43 nontrivial dependencies
Mon Oct 29 23:07:33 2007
Mon Oct 29 23:07:33 2007 commencing square root phase
Mon Oct 29 23:07:33 2007 reading relations for dependency 1
Mon Oct 29 23:07:38 2007 read 1087626 cycles
Mon Oct 29 23:07:41 2007 cycles contain 3803475 unique relations
Mon Oct 29 23:08:37 2007 read 3803475 relations
Mon Oct 29 23:09:01 2007 multiplying 5539876 relations
[/code]

[code]Mon Oct 29 23:36:37 2007 Msieve v. 1.29
Mon Oct 29 23:36:37 2007 random seeds: 64a82be8 6a738293
Mon Oct 29 23:36:37 2007 factoring 15496647981658326549142030621730331832194208985736266087139971798307865868343396735342621231546740545690319656743042665973300306393298109 (137 digits)
Mon Oct 29 23:36:38 2007 commencing number field sieve (136-digit input)
Mon Oct 29 23:36:38 2007 R0: -173348912811994486824321076
Mon Oct 29 23:36:38 2007 R1: 2429059952378501
Mon Oct 29 23:36:38 2007 A0: -62041362857300991292260795462387
Mon Oct 29 23:36:38 2007 A1: -1106727533479641493105223221
Mon Oct 29 23:36:38 2007 A2: 3319967176309354656425
Mon Oct 29 23:36:38 2007 A3: 35507971948951253
Mon Oct 29 23:36:38 2007 A4: -49422761886
Mon Oct 29 23:36:38 2007 A5: 99000
Mon Oct 29 23:36:38 2007 size score = 5.037916e-014, Murphy alpha = -6.092906, combined = 3.839630e-013
Mon Oct 29 23:36:38 2007
Mon Oct 29 23:36:38 2007 commencing square root phase
Mon Oct 29 23:36:38 2007 reading relations for dependency 1
Mon Oct 29 23:36:39 2007 read 1087626 cycles
Mon Oct 29 23:36:41 2007 cycles contain 3803475 unique relations
Mon Oct 29 23:36:57 2007
Mon Oct 29 23:36:57 2007
Mon Oct 29 23:36:57 2007 Msieve v. 1.29
Mon Oct 29 23:36:57 2007 random seeds: cc09c124 53b0e5dd
Mon Oct 29 23:36:57 2007 factoring 15496647981658326549142030621730331832194208985736266087139971798307865868343396735342621231546740545690319656743042665973300306393298109 (137 digits)
Mon Oct 29 23:36:58 2007 commencing number field sieve (136-digit input)
Mon Oct 29 23:36:58 2007 R0: -173348912811994486824321076
Mon Oct 29 23:36:58 2007 R1: 2429059952378501
Mon Oct 29 23:36:58 2007 A0: -62041362857300991292260795462387
Mon Oct 29 23:36:58 2007 A1: -1106727533479641493105223221
Mon Oct 29 23:36:58 2007 A2: 3319967176309354656425
Mon Oct 29 23:36:58 2007 A3: 35507971948951253
Mon Oct 29 23:36:58 2007 A4: -49422761886
Mon Oct 29 23:36:58 2007 A5: 99000
Mon Oct 29 23:36:58 2007 size score = 5.037916e-014, Murphy alpha = -6.107394, combined = 3.858218e-013
Mon Oct 29 23:36:58 2007
Mon Oct 29 23:36:58 2007 commencing square root phase
Mon Oct 29 23:36:58 2007 reading relations for dependency 1
Mon Oct 29 23:36:59 2007 read 1087626 cycles
Mon Oct 29 23:37:01 2007 cycles contain 3803475 unique relations
Mon Oct 29 23:37:55 2007 read 3803475 relations
Mon Oct 29 23:38:20 2007 multiplying 5539876 relations
Tue Oct 30 00:03:14 2007 multiply complete, coefficients have about 272.73 million bits
Tue Oct 30 00:03:25 2007 initial square root is modulo 78487
Tue Oct 30 00:30:41 2007 prp44 factor: 92032067272541258617274274530889901382225773
Tue Oct 30 00:30:41 2007 prp93 factor: 168383134715065946350807362892776809572312840207073578263044682409585696836605507154286041233
Tue Oct 30 00:30:41 2007 elapsed time 00:53:44[/code]