Polynomial Request Thread - Page 57

VBCurtis · 2016-05-20, 01:08

I use factmsieve to generate a job file and command-line invocation of lasieve. Then I quit the script, and to test-sieve I type the exact command-line that the script generates.

I open the job.T0 file, edit the sieve range to 2000 (say, 5650000 to 5652000). Run lasieve, note the number of relations and time sec/rel.

Open the job file, change the q's to something much larger (say, 25650000 to 25652000). I generally do 4 tests from lowest to highest-expected q, so the middle two are roughly 1/3rd and 2/3rds of the way from starting q to (expected/guessed) final q.

Note the 4 yields and 4 sec/rel times. If each test takes less than 10 min, use a wider q-range (I use 5000 for GNFS below 160). The larger the q range (and the more tests you do), the more accurate the timings are. But then, if two polys are within 1% sec/rel, it's probly better to decide by yield than by sec/rel.

Then, repeat with a new poly, or with new parameters in the .job file. You might change LP from 31 to 32, or invoke 15e instead of 14e, etc.

If you change polys, you'll need to delete all the relations and job files (or use a fresh directory). Each time you start a new run, lasieve may tell you it can't run because a save file already exists- delete it. Also, the afb files are the factor base files- those should be deleted each test if you're changing the factor base (which you will, because most sieve tests are below the FB limit so you need to edit the fb number to match the q you edited).

I haven't done this in a while to give more detailed guidance, but that should get you started and able to experiment.

wombatman · 2016-05-20, 01:25

Excellent. Thanks! I'll play around with it and see what I get.

Dubslow · 2016-05-20, 01:43

Yafu has a -nt option which *should* automatically trial sieve a list of poly files (including parameter generation, if necessary, and even parameter adjustment in rare circumstances), but last time I tried it, it was rather buggy. (Great testament to my programming abilities, since I wrote it!

)

Dubslow · 2016-05-20, 06:35

Okay, I've both fixed the bugs in yafu -nt and tested it by trying the top three from each of the three batches for the C173 under recent consideration. The results, with some caveats below:

Code:

(gdb) run "nfs($(cat num))" -nt hybrid1.job,hybrid2.job,hybrid3.job,cpucado1.job,cpucado2.job,cpucado3.job,gpumsieve1.job,gpumsieve2.job,gpumsieve3.job -v -threads 8
Starting program: /home/bill/yafu/yafu "nfs($(cat num))" -nt hybrid1.job,hybrid2.job,hybrid3.job,cpucado1.job,cpucado2.job,cpucado3.job,gpumsieve1.job,gpumsieve2.job,gpumsieve3.job -v -threads 8
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/lib/x86_64-linux-gnu/libthread_db.so.1".


05/19/16 23:29:55 v1.34.5 @ Gravemind, System/Build Info: 
Using GMP-ECM 7.0-dev, Powered by GMP 6.0.0
detected        Intel(R) Core(TM) i7-2600K CPU @ 3.40GHz
detected L1 = 32768 bytes, L2 = 8388608 bytes, CL = 64 bytes
measured cpu frequency ~= 3392.300400
using 1 random witnesses for Rabin-Miller PRP checks

===============================================================
======= Welcome to YAFU (Yet Another Factoring Utility) =======
=======             bbuhrow@gmail.com                   =======
=======     Type help at any time, or quit to quit      =======
===============================================================
cached 78498 primes. pmax = 999983


>> test: starting trial sieving
nfs: parsed lpbr = 0, lpba = 0
test: warning: "hybrid1.job" is missing some paramters (0XFF). filling them.
nfs: parsed lpbr = 0, lpba = 0
test: warning: "hybrid2.job" is missing some paramters (0XFF). filling them.
nfs: parsed lpbr = 0, lpba = 0
test: warning: "hybrid3.job" is missing some paramters (0XFF). filling them.
nfs: parsed lpbr = 0, lpba = 0
test: warning: "cpucado1.job" is missing some paramters (0XFF). filling them.
nfs: parsed lpbr = 0, lpba = 0
test: warning: "cpucado2.job" is missing some paramters (0XFF). filling them.
nfs: parsed lpbr = 0, lpba = 0
test: warning: "cpucado3.job" is missing some paramters (0XFF). filling them.
nfs: parsed lpbr = 0, lpba = 0
test: warning: "gpumsieve1.job" is missing some paramters (0XFF). filling them.
nfs: parsed lpbr = 0, lpba = 0
test: warning: "gpumsieve2.job" is missing some paramters (0XFF). filling them.
nfs: parsed lpbr = 0, lpba = 0
test: warning: "gpumsieve3.job" is missing some paramters (0XFF). filling them.
test: trial sieving hybrid1.job

test: generating factor bases
test: fb generation took 38.3197 seconds
test: commencing test sieving of polynomial 0 on the algebraic side over range 65600000-65602000
gnfs-lasieve4I15e (with asm64): L1_BITS=15, SVN $Revision: 430 $
...snip...

test: found 5146 relations in a range of 1967 special-q
test: new best estimated total sieving time = 44 days 20h 19m 50s (with 8 threads)


test: trial sieving hybrid2.job

test: generating factor bases
test: fb generation took 37.5610 seconds
test: commencing test sieving of polynomial 1 on the algebraic side over range 65600000-65602000
gnfs-lasieve4I15e (with asm64): L1_BITS=15, SVN $Revision: 430 $
...snip...
test: found 4452 relations in a range of 1967 special-q
test: estimated total sieving time = 45 days 14h 35m 45s (with 8 threads)


test: trial sieving hybrid3.job

test: generating factor bases
test: fb generation took 37.7180 seconds
test: commencing test sieving of polynomial 2 on the algebraic side over range 65600000-65602000
gnfs-lasieve4I15e (with asm64): L1_BITS=15, SVN $Revision: 430 $
...snip...

test: found 4320 relations in a range of 1967 special-q
test: estimated total sieving time = 47 days 18h 52m 4s (with 8 threads)


test: trial sieving cpucado1.job

test: generating factor bases
test: fb generation took 36.9282 seconds
test: commencing test sieving of polynomial 3 on the algebraic side over range 65600000-65602000
gnfs-lasieve4I15e (with asm64): L1_BITS=15, SVN $Revision: 430 $
...snip...

test: found 4251 relations in a range of 1967 special-q
test: estimated total sieving time = 45 days 1h 5m 25s (with 8 threads)


test: trial sieving cpucado2.job

test: generating factor bases
test: fb generation took 37.1016 seconds
test: commencing test sieving of polynomial 4 on the algebraic side over range 65600000-65602000
gnfs-lasieve4I15e (with asm64): L1_BITS=15, SVN $Revision: 430 $
...snip...

test: found 4973 relations in a range of 1953 special-q
test: estimated total sieving time = 51 days 9h 45m 19s (with 8 threads)


test: trial sieving cpucado3.job

test: generating factor bases
test: fb generation took 38.3977 seconds
test: commencing test sieving of polynomial 5 on the algebraic side over range 65600000-65602000
gnfs-lasieve4I15e (with asm64): L1_BITS=15, SVN $Revision: 430 $
...snip...

test: found 4647 relations in a range of 1967 special-q
test: estimated total sieving time = 54 days 9h 10m 12s (with 8 threads)


test: trial sieving gpumsieve1.job

test: generating factor bases
test: fb generation took 38.0256 seconds
test: commencing test sieving of polynomial 6 on the algebraic side over range 65600000-65602000
gnfs-lasieve4I15e (with asm64): L1_BITS=15, SVN $Revision: 430 $
...snip...

test: found 4331 relations in a range of 1967 special-q
test: estimated total sieving time = 48 days 11h 56m 49s (with 8 threads)


test: trial sieving gpumsieve2.job

test: generating factor bases
test: fb generation took 38.1018 seconds
test: commencing test sieving of polynomial 7 on the algebraic side over range 65600000-65602000
gnfs-lasieve4I15e (with asm64): L1_BITS=15, SVN $Revision: 430 $
...snip...

test: found 5251 relations in a range of 1953 special-q
test: estimated total sieving time = 47 days 54m 14s (with 8 threads)


test: trial sieving gpumsieve3.job

test: generating factor bases
test: fb generation took 38.1440 seconds
test: commencing test sieving of polynomial 8 on the algebraic side over range 65600000-65602000
gnfs-lasieve4I15e (with asm64): L1_BITS=15, SVN $Revision: 430 $
...snip...

test: found 5579 relations in a range of 1953 special-q
test: new best estimated total sieving time = 43 days 15h 35m 58s (with 8 threads)
test: test sieving took 6544.09 seconds
test: "gpumsieve3.job" is the fastest poly

The caveats are that this took more than an hour on my primary desktop, so I can't really guarantee homogeneous computing environment, though the last 5 or 6 I think were more stable than the first 3-4. Also note that yield doesn't really correlate with speed (despite what I'm reasonably certain is an identical minrels estimate for all polys, since IIRC yafu calculates that based on lpb bounds, nothing about the actual coefficients). The top yield is the fastest, but below that there's considerable fluctuation. I'm not sure how much of this is due to the background compute environment, though I suspect with 8 threads available and a decent scheduler, the background is a relatively small factor.

All in all it does seem to be relatively a crapshoot, and I'd bet there's a decent chance some of the other top ~15-20 polys might sieve better, but I don't really want to invest time into that. (Yafu runs -nt single threaded by design, though I definitely wish I could have made use of all 8 threads available on this processor to speed it up.)

Yafu chose the following identical sieve parameters for all polys:

Code:

rlim: 65600000
alim: 65600000
lpbr: 31
lpba: 31
mfbr: 62
mfba: 62
rlambda: 2.6
alambda: 2.6

VBCurtis · 2016-05-20, 16:13

Neat! Having something automated like this is very useful for trying a dozen or more polys, followed by taking (say) the best 3-4 from this test to test-sieve at other q-values. Sometimes one poly will be so much faster than add'l test-sieving won't be necessary.
That is, a test like this would help to locate the rare poly that sieves *much* better than its score; it's possible a 10th-best poly sieves fastest, but we rarely notice.

wombatman · 2016-05-20, 16:49

For comparison, here's what factmsieve chose:

Code:

rlim: 70800000
alim: 35399999
lpbr: 30
lpba: 30
mfbr: 60
mfba: 60
rlambda: 2.6
alambda: 2.6

I'm still working through trial-sieving.

wombatman · 2016-05-20, 19:50

Here's the results thus far for the 3 GPU-Msieve polynomials. They're identified by their e-score line. Q is the starting Q-value (all ranges were 2000) and yield is just the number of relations.

Code:

# norm 8.340529e-17 alpha -8.102789 e 2.259e-13 rroots 3
Q = 35400000
Yield: 3562
Sec/rel: 0.3

Q = 3540000
Yield: 1656
Sec/rel: 0.6

Q = 70000000
Yield: 2237
Sec/rel: 0.378

Q = 140000000
Yield: 1478
Sec/rel: 0.484
------------------------------------
# norm 8.321140e-17 alpha -6.359217 e 2.277e-13 rroots 5
Q = 35400000
Yield: 3018
Sec/rel: 0.322

Q = 3540000
Yield: 1312
Sec/rel: 0.644

Q = 70000000
Yield: 1882
Sec/rel: 0.41

Q = 140000000
Yield: 1541
Sec/rel: 0.50
----------------------------------
# norm 8.453764e-17 alpha -7.682575 e 2.284e-13 rroots 5
Q = 35400000
Yield: 3082
Sec/rel: 0.357

Q = 3540000
Yield: 2503
Sec/rel: 0.347

Q = 70000000
Yield: 2851
Sec/rel: 0.343

Q = 140000000
Yield: 2480
Sec/rel: 0.334

Basically, it looks like the 3rd MSieve polynomial is the best of the 3. I can test the CADO ones as well if needed.

VBCurtis · 2016-05-20, 21:40

Quote:

Originally Posted by wombatman

For comparison, here's what factmsieve chose:

Code:

rlim: 70800000
alim: 35399999
lpbr: 30
lpba: 30
mfbr: 60
mfba: 60
rlambda: 2.6
alambda: 2.6

I'm still working through trial-sieving.

Note that factmsieve sets alim= rlim, but lasieve cannot sieve when q is below alim. So, each time factmsieve creates a job file, it sets alim to be initial q minus 1. This is what I referred to when I suggested you edit alim each time you run a test at a different q.

If you leave alim equal to rlim, lasieve throws an error, but reduces alim itself and runs normally. So, test-sieving can set alim equal to rlim as far as I know.

Dubslow's tests found the same poly best that you did, so I think it's settled. We also have a new data point that indicates CADO is competitive with msieve-GPU; yafu's sieve-time estimates show the CADO poly within 5% or so of the best msieve, a gap that could be overcome with more CPU-search-time.

XYYXF · 2016-05-22, 20:51

Quote:

Originally Posted by XYYXF

There's also another GNFS task, C188_140_113:

Code:

51928438462607404737043189983177088594484655472144336181756537025533635370879714014750880494339341212074869710914584937712249921999507347297047835234867294560314897640299447799219467293637

About 50% of t60 is done on it; a factor still may fall out, but the chance is quite low.

t60 is 92% done :-)

XYYXF · 2016-05-29, 16:19

C188_149_78 is also passing through t60. About 70% is done.

Code:

13491172052456269739341956417618996004920029783644716173916161037211832989375573077619750428074121959983565850095685624646347992341534091340006815261958418474059537715490281306983460649909

RichD · 2016-06-01, 02:03

My last number of this size (a C192) took nearly 3 months (wall clock time) to get a decent poly. I don't have the resources to even contribute one month at this time. Sorry.

2016-05-20, 16:49	#622
wombatman I moo ablest echo power! May 2013 1781₁₀ Posts	For comparison, here's what factmsieve chose: Code: rlim: 70800000 alim: 35399999 lpbr: 30 lpba: 30 mfbr: 60 mfba: 60 rlambda: 2.6 alambda: 2.6 I'm still working through trial-sieving. Last fiddled with by wombatman on 2016-05-20 at 16:54

2016-05-29, 16:19	#626
XYYXF Jan 2005 Minsk, Belarus 110010000₂ Posts	C188_149_78 is also passing through t60. About 70% is done. Code: 13491172052456269739341956417618996004920029783644716173916161037211832989375573077619750428074121959983565850095685624646347992341534091340006815261958418474059537715490281306983460649909

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
GIMPS wiki account request thread	ixfd64	mersennewiki	169	2018-09-21 05:43
Polynomial Discriminant is n^k for an n-1 degree polynomial	carpetpool	Miscellaneous Math	14	2017-02-18 19:46
Lost Prime Raider password request thread	cheesehead	Forum Feedback	6	2009-07-28 13:02
Polynomial	R.D. Silverman	NFSNET Discussion	13	2005-09-16 20:07
Deutscher Thread (german thread)	TauCeti	NFSNET Discussion	0	2003-12-11 22:12

2016-05-20, 01:08	#617
VBCurtis "Curtis" Feb 2005 Riverside, CA 2×2,437 Posts	I use factmsieve to generate a job file and command-line invocation of lasieve. Then I quit the script, and to test-sieve I type the exact command-line that the script generates. I open the job.T0 file, edit the sieve range to 2000 (say, 5650000 to 5652000). Run lasieve, note the number of relations and time sec/rel. Open the job file, change the q's to something much larger (say, 25650000 to 25652000). I generally do 4 tests from lowest to highest-expected q, so the middle two are roughly 1/3rd and 2/3rds of the way from starting q to (expected/guessed) final q. Note the 4 yields and 4 sec/rel times. If each test takes less than 10 min, use a wider q-range (I use 5000 for GNFS below 160). The larger the q range (and the more tests you do), the more accurate the timings are. But then, if two polys are within 1% sec/rel, it's probly better to decide by yield than by sec/rel. Then, repeat with a new poly, or with new parameters in the .job file. You might change LP from 31 to 32, or invoke 15e instead of 14e, etc. If you change polys, you'll need to delete all the relations and job files (or use a fresh directory). Each time you start a new run, lasieve may tell you it can't run because a save file already exists- delete it. Also, the afb files are the factor base files- those should be deleted each test if you're changing the factor base (which you will, because most sieve tests are below the FB limit so you need to edit the fb number to match the q you edited). I haven't done this in a while to give more detailed guidance, but that should get you started and able to experiment.

2016-05-20, 01:25	#618
wombatman I moo ablest echo power! May 2013 13×137 Posts	Excellent. Thanks! I'll play around with it and see what I get.

2016-05-20, 01:43	#619
Dubslow Basketry That Evening! "Bunslow the Bold" Jun 2011 40<A<43 -89<O<-88 3×29×83 Posts	Yafu has a -nt option which should automatically trial sieve a list of poly files (including parameter generation, if necessary, and even parameter adjustment in rare circumstances), but last time I tried it, it was rather buggy. (Great testament to my programming abilities, since I wrote it! )

2016-05-20, 16:13	#621
VBCurtis "Curtis" Feb 2005 Riverside, CA 1001100001010₂ Posts	Neat! Having something automated like this is very useful for trying a dozen or more polys, followed by taking (say) the best 3-4 from this test to test-sieve at other q-values. Sometimes one poly will be so much faster than add'l test-sieving won't be necessary. That is, a test like this would help to locate the rare poly that sieves much better than its score; it's possible a 10th-best poly sieves fastest, but we rarely notice.

2016-06-01, 02:03	#627
RichD Sep 2008 Kansas 3391₁₀ Posts	My last number of this size (a C192) took nearly 3 months (wall clock time) to get a decent poly. I don't have the resources to even contribute one month at this time. Sorry.