New polynomial finder discussion - Page 3

Batalov · 2008-11-24, 04:19

Running another gnfs-120: in parallel on Windows (your binary) and on x86_64.

There are no "expand failed" messages on Windows - this may be a 64-bit portability thing. The (single, so far) inf is generated as well, and very fast, maybe in a minute or so (therefore, probably a good debug case).

For debugging: the number is 2648195527610722149244619035624215921962390457850886740531905304699190651782516458062408766925167070534368118892625076601
(a residue from $8*10^{185}+9$ )... The inf on Windows is reported as

Code:

...
integrator failed 1.#INF00e+000 1.#INF00e+000
save 1.388040e+017 -5.489537 301942.756791 1.#INF00e+000
save 1.041019e+017 -6.593728 272493.776973 1.172948e-011
...

<S>

jasonp · 2008-11-24, 04:26

Thanks for the test case, the fix ignores the poly like it should now.

Batalov · 2008-11-24, 06:16

Quote:

Originally Posted by Batalov

There are no "expand failed" messages on Windows - this may be a 64-bit portability thing.

and it is probably important. Windows binary finds very good polys where Opteron does not. (probably skips them as "expand failed"). This needs to be debugged, too. I can try tomorrow evening.

bsquared · 2008-11-24, 14:01

The poly finder has been running for 10 hours now on a C150 and the .p file has yet to be updated (still 0 bytes). Is this expected for a number this size? The screen has updated once (running with -v), announcing a new batch:

Code:

Msieve v. 1.39
Sun Nov 23 22:31:40 2008
random seeds: 8ce70500 156790da
factoring 25737375569340135791371992988682955710239484900835570085332268342915936020415749506274062633497655703373923520
4025432832861137197259731899771993528783 (150 digits)
searching for 15-digit factors
commencing number field sieve (150-digit input)
commencing number field sieve polynomial selection
time limit set to 193.75 hours
searching leading coefficients from 752845 to 1181920
deadline: 400 seconds per coefficient
coeff 752880-755820 293727099 381845228 381845229 496398797 lattice 589038241
p 293727099 381845228 381845229 496398797 lattice 589038241
batch 5000 294349931
deadline: 400 seconds per coefficient
coeff 755880-758820 293843699 381996808 381996809 496595851 lattice 590127269
p 293843699 381996808 381996809 496595851 lattice 590127269
batch 5000 294468443

If the code is in fact producing polys, maybe update the file a little more often? My normal mode of operation would probably be to run a few dozen of these jobs in parallel, so 193.75 hrs / 32 = 6 hrs for each job (with staggered input ranges, of course).

- ben.

bsquared · 2008-11-24, 14:43

Quote:

Originally Posted by bsquared

The poly finder has been running for 10 hours now on a C150 and the .p file has yet to be updated (still 0 bytes). Is this expected for a number this size?

Apparently i'm not patient enough... I now have one poly!

Code:

# norm 7.233e+021 alpha -8.081373 skew 1437016.24 e 1.082e-014
R0 -50840325583863057597193107695
R1  121639974074579617
A0 -3784593166700196886977944728073992896
A1 -77530703470713794970192367917116
A2  23657834822589684322966464
A3  22883647631768638059
A4 -23304955363210
A5  757800

Though the Murphy-e is low (compared to pol51* value of 5.12e-12).

jasonp · 2008-11-24, 15:08

The .p file is updated whenever a polynomial is found; there's no point in batching output when it happens so rarely. For big inputs like this the lack of optimization in the code really shows; it's also possible that the smallest leading coefficient that is tried is too large, and removes the possibility of finding a really good polynomial. Look at that alpha value though!

It's typical for the poly finder to spend a long time finding nothing and then suddenly big batches of excellent polynomials start pouring out. Another possibility is that the GGNFS parameters for jobs this large are bad, so that many other polynomials should be getting found.

Also, if running poly selection in parallel, with lower and upper coefficient bounds specified, then the time limits for the whole job are ignored (but the time limits on an individual batch are still kept).

Serge, I'll spend some time on the 64-bit problems tonight, you don't have to reverse-engineer my undocumented mess

Andi_HB · 2008-11-24, 15:09

Hi!
Is it normal that the range from A5 is not going up continous?
In the .p file the Index from A5 is going up mostly but sometimes its going back.

Code:

factoring 26586039827446669611337466195690846127967101614742727267571866417745134397128623516193481405551589715561984226324824523445254699125192138989 (140digits)
# norm 9.869e+019 alpha -6.758662 skew 1040502.36 e 1.107e-013
R0 -663915625912491596425039124
R1  4606286845389727
A0  427927001411518453817677112302609335
A1  386852088508790881123208663217
A2 -1308542692399626135679435
A3 -835220885991722581
A4  766617569636
A5  206100
# norm 2.505e+020 alpha -7.569786 skew 1032272.69 e 1.109e-013
R0 -664039862507344487421732553
R1  4655783520883379
A0  47904891485003053585178348796431868
A1 -1583917582084597488069488059698
A2  1811789752504735806847876
A3  1754454399354612523
A4 -1057223755124
A5  205920

jasonp · 2008-11-24, 15:18

Yes, leading coefficients are searched in batches of 10-50 (this makes the inner loops much more efficient), so for smaller problems it's possible for the A5 value to jump around.

bsquared · 2008-11-24, 15:29

Quote:

Originally Posted by jasonp

The .p file is updated whenever a polynomial is found; there's no point in batching output when it happens so rarely. For big inputs like this the lack of optimization in the code really shows; it's also possible that the smallest leading coefficient that is tried is too large, and removes the possibility of finding a really good polynomial. Look at that alpha value though!

That alpha is amazing, yeah!

I'll let it run till it produces a few more polys, then test them out. I haven't done much experiementing with lower E, but better alpha, on yield, so this looks like a good chance to start.

Quote:

Originally Posted by jasonp

It's typical for the poly finder to spend a long time finding nothing and then suddenly big batches of excellent polynomials start pouring out. Another possibility is that the GGNFS parameters for jobs this large are bad, so that many other polynomials should be getting found.

Using the pol51* tools, I used the following parameters:
-a 9000 $ corresponding to A5=900000
-A 10000 $ corresponding to A5=1000000
-p 6 $ 6 primes, not sure how relevant that is to this new method
normmax = 5.15E+22 $ for stage 1
normmax1 = 1.96E+21
normmax2 = 6.82E+18
Murphy-E = 2.88E-12

Not sure how these relate to the given GGNFS parameters

10metreh · 2008-11-24, 15:40

Jasonp, when are you hoping msieve will be better than ggnfs for the whole of the GNFS factorization? 5 more years needed?

jasonp · 2008-11-24, 16:06

Ben: looks like the A5 range is too high on the new poly finder, it should be 100k at most. The big advantage here is that we will be finding many more stage 1 candidates when A5 is extremely small, which gives us a better chance of finding a polynomial with extremely high skew, and thus a large search space to find excellent root properties. I'm guessing the best range of A5 should be 10-50x smaller than what you would use for pol5.

10metreh: I have no idea. It will happen when it happens, or not. The first five years have been pretty nice.

2008-11-24, 04:19	#23
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 2505₁₆ Posts	Re: "integrator failed" and "expand failed" Running another gnfs-120: in parallel on Windows (your binary) and on x86_64. There are no "expand failed" messages on Windows - this may be a 64-bit portability thing. The (single, so far) inf is generated as well, and very fast, maybe in a minute or so (therefore, probably a good debug case). For debugging: the number is 2648195527610722149244619035624215921962390457850886740531905304699190651782516458062408766925167070534368118892625076601 (a residue from $8*10^{185}+9$ )... The inf on Windows is reported as Code: ... integrator failed 1.#INF00e+000 1.#INF00e+000 save 1.388040e+017 -5.489537 301942.756791 1.#INF00e+000 save 1.041019e+017 -6.593728 272493.776973 1.172948e-011 ... <S>

2008-11-24, 15:08	#28
jasonp Tribal Bullet Oct 2004 3,541 Posts	The .p file is updated whenever a polynomial is found; there's no point in batching output when it happens so rarely. For big inputs like this the lack of optimization in the code really shows; it's also possible that the smallest leading coefficient that is tried is too large, and removes the possibility of finding a really good polynomial. Look at that alpha value though! It's typical for the poly finder to spend a long time finding nothing and then suddenly big batches of excellent polynomials start pouring out. Another possibility is that the GGNFS parameters for jobs this large are bad, so that many other polynomials should be getting found. Also, if running poly selection in parallel, with lower and upper coefficient bounds specified, then the time limits for the whole job are ignored (but the time limits on an individual batch are still kept). Serge, I'll spend some time on the 64-bit problems tonight, you don't have to reverse-engineer my undocumented mess Last fiddled with by jasonp on 2008-11-24 at 15:14

2008-11-24, 15:18	#30
jasonp Tribal Bullet Oct 2004 3,541 Posts	Yes, leading coefficients are searched in batches of 10-50 (this makes the inner loops much more efficient), so for smaller problems it's possible for the A5 value to jump around. Last fiddled with by jasonp on 2008-11-24 at 15:19 Reason: typo

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Polynomial Discriminant is n^k for an n-1 degree polynomial	carpetpool	Miscellaneous Math	14	2017-02-18 19:46
Polynomial algorithm	diep	Factoring	7	2012-09-29 12:09
Question about polynomial finder	jordis	Msieve	1	2009-01-10 17:58
[Need help] about Matrix Polynomial	buan	Homework Help	3	2007-07-17 15:07
Polynomial	R.D. Silverman	NFSNET Discussion	13	2005-09-16 20:07

2008-11-24, 04:26	#24
jasonp Tribal Bullet Oct 2004 3,541 Posts	Thanks for the test case, the fix ignores the poly like it should now.

2008-11-24, 15:40	#32
10metreh Nov 2008 2·3³·43 Posts	Jasonp, when are you hoping msieve will be better than ggnfs for the whole of the GNFS factorization? 5 more years needed?

2008-11-24, 16:06	#33
jasonp Tribal Bullet Oct 2004 3,541 Posts	Ben: looks like the A5 range is too high on the new poly finder, it should be 100k at most. The big advantage here is that we will be finding many more stage 1 candidates when A5 is extremely small, which gives us a better chance of finding a polynomial with extremely high skew, and thus a large search space to find excellent root properties. I'm guessing the best range of A5 should be 10-50x smaller than what you would use for pol5. 10metreh: I have no idea. It will happen when it happens, or not. The first five years have been pretty nice.