Poly Search vs Sieving times

EdH · 2013-10-12, 14:24

Sorry for the neophyte question, but for smaller composites ~150 digits across multiple machines, is there a real gain in overall sieving if a poly with a greater than expected E score is found early in the search?

Specifics:

Code:

Msieve v. 1.52 (SVN 886)
random seeds: 55df12b7 e5d3c816
factoring 218876969782929216599190531580538390484044829345681891460187089862281796240529496476113446316632558113449224677358919720113328517497603198421529 (144 digits)
searching for 15-digit factors
commencing number field sieve (144-digit input)
commencing number field sieve polynomial selection
polynomial degree: 5
max stage 1 norm: 8.34e+21
max stage 2 norm: 1.39e+20
min E-value: 1.03e-11
poly select deadline: 311905
time limit set to 86.64 CPU-hours
expecting poly E from 1.12e-11 to > 1.29e-11

(The msieve machine has four cores and I hard set the search time to 12 hours.)

The following poly was found within the first few minutes:

Code:

# norm 8.158791e-14 alpha -8.748871 e 1.309e-11 rroots 5
skew: 52981938.39
c0: 5925697648913135366967245004294844179177
c1: 468536815244189902014756820336233
c2: -26076232373209850831435621
c3: -542019174557361769
c4: 10239243052
c5: 48
Y0: -21467961164039091417408999106
Y1: 1118175346469539

I'm running several machines and expect the sieving and LA to take approximately four days. (Of course, I may be way off.)

Would a better poly outweigh the 11 hours of search time left for a 48-60 hour project?

Thanks...

VBCurtis · 2013-10-12, 17:38

If the "expected score" is accurate at this size, you should not search further. You may well find a poly that's 5% faster by completing the search, but it's pretty clear that 5% of sieve time is greater than the poly-search time.

However, the Expected Score code is simply guesswork- without previous experience about its accuracy, you don't know if you might improve by 10% or more. I'd compromise, and search a couple more hours- if nothing comes close in that time, I'd assume I got lucky at the outset and proceed to sieving.

A5 coefficients below 10000 should not be searched- msieve takes longer at very low A5 values to do the same work. Also note skew is 50M, very high for this size of number; this occasionally causes hiccups in later stages (I have not run into such a hiccup yet, but I follow Frmky's advice to use large A5, say 5-50M for this size number). Large A5 coefficients have lower skews than very small values.

EdH · 2013-10-12, 18:32

Thanks!

My impatience got me to break in at about 2.5 hours of searching and that was the poly chosen - no others were close.

My first set of relations came in at 2.2% of the estimated minimum (32523338) in about 1.2 hours. This calculates to (very) roughly 55 hours for sieving, although a couple of the machines will be off at night.

I guess I'll see how it turns out...

EdH · 2013-10-12, 19:44

Wow! I have a new estimate for sieving time of ~26 hours. I guess the first estimate hadn't received relations from several of the machines. I'll have to see how it works out in reality.

The "Wow!" part is that I remember taking over two weeks to factor c100s...

EdH · 2013-10-13, 14:14

There I was!

closing in on a matrix,

when the power company lost control,

and my scripts weren't robust enough to carry through a restart,

so I had to resort to semi-manually* completing the job.

So much for an accurate timing for this composite factorization...

Oh, well, if anything good has come of it, it got me off my a** to place the main factoring machine on a UPS that was already sitting there, waiting to be put into use...

*semi-manually meaning a manual restart of factmsieve.py and manually concatenating all the relations from those machines that are still running...

EdH · 2013-10-13, 18:05

Well, that didn't work.

Now I'm lost!

factmsieve.py wouldn't restart - kept giving an error 255. Renamed number.dat.cyc and that cleared the factmsieve.py error. But, number.dat was trashed. Rebuilt that, but factmsieve.py wouldn't go anywhere, so I have moved to msieve direct entry. Now all I get are -11 errors for the entire 4G number.dat file. Currently, I'm retrieving the rels from the spairs.save.gz file to see if I can get anywhere from there.

wombatman · 2013-10-13, 19:45

One thing to try is restoring the relations found using the spairs.gz file like you're doing, deleting all the .cyc and such, and then rerunning using the "-nc" command. That should take of it, if I understand your error correctly. I've had to do that before when my .dat file disappeared.

EdH · 2013-10-13, 20:07

Quote:

Originally Posted by wombatman

One thing to try is restoring the relations found using the spairs.gz file like you're doing, deleting all the .cyc and such, and then rerunning using the "-nc" command. That should take of it, if I understand your error correctly. I've had to do that before when my .dat file disappeared.

Thanks! That's what I've done and it is working through the msieve steps, but I have encountered another stumbling block:

Code:

matrix needs more columns than rows; try adding 2-3% more relations

This keeps coming up even when I add more relations. This might be due to the poly. I'm suspecting this may be what VBCurtis posted about:

Quote:

Originally Posted by VBCurtis

A5 coefficients below 10000 should not be searched- msieve takes longer at very low A5 values to do the same work. Also note skew is 50M, very high for this size of number; this occasionally causes hiccups in later stages (I have not run into such a hiccup yet, but I follow Frmky's advice to use large A5, say 5-50M for this size number). Large A5 coefficients have lower skews than very small values.

I will keep adding for now, but at some point I may need to start over from scratch...

EdH · 2013-10-14, 15:56

The matrix finally built properly for a solve...

wombatman · 2013-10-14, 16:00

I have that issue sometimes as well--I've gotten to 120% of the estimated relations before the matrix builds, even when using a large interval step. Maybe somebody better versed in this can suggest a cause?

VBCurtis · 2013-10-14, 20:00

The estimates for # of relations in the factmsieve script are not very accurate- it uses an exponential with size of number as input, while the actual situation is more like a step function with the steps located where lpbr jumps bits. Serge (Batalov) posted a patch to fix this in some thread- I'll see if I can find and link it.

Actual rels needed is roughly 21M for 28-bit projects, 40M for 29-bit projects, and (I am told) the low 80s for 30-bit projects. Some polys produce more or fewer duplicate relations, and sometimes a matrix builds with fewer-than-typical relations, so there is a fair amount of variety from project to project.

My vague grasp of the "hiccup" mentioned above is that skew alters the area sieved for each special-Q, with higher skews associated with smaller areas. Very high skews may require more special-Q to be searched, and that requirement can lead to using special-Q higher than a poly's efficient sieve range. So it's not that reaching 120% of the script's expected rels is a hiccup- it's that the last few rels might be found at a rate half (or worse?) of the sec/rel you achieved during most of the sieving. If you read through threads of large forum-team-factorizations, you'll see discussions amounting to "we've run out of good Q, now what?". High-skew polys run out of good Q more often than low-skew polys.

At single-user-size projects, we can preempt this problem by choosing the next-higher siever version for a project we're even slightly nervous about. We might choose to use 14e instead of 13e for projects a few digits lower than the script's cutoff; in fact, I edited my factmsieve code to shift the cutoff a bit lower. As Mr Womack points out, this makes factorizations in the 135 to 150 digit level more fire-and-forget at the expense of a few hours of sieving. I have not yet attempted a 30-bit project myself to know how much of this extends upward.
-Curtis

2013-10-13, 18:05	#6
EdH "Ed Hall" Dec 2009 Adirondack Mtns 13204₈ Posts	Well, that didn't work. Now I'm lost! factmsieve.py wouldn't restart - kept giving an error 255. Renamed number.dat.cyc and that cleared the factmsieve.py error. But, number.dat was trashed. Rebuilt that, but factmsieve.py wouldn't go anywhere, so I have moved to msieve direct entry. Now all I get are -11 errors for the entire 4G number.dat file. Currently, I'm retrieving the rels from the spairs.save.gz file to see if I can get anywhere from there. Last fiddled with by EdH on 2013-10-13 at 18:08 Reason: removed erroneous info

2013-10-14, 20:00	#11
VBCurtis "Curtis" Feb 2005 Riverside, CA 3×1,999 Posts	The estimates for # of relations in the factmsieve script are not very accurate- it uses an exponential with size of number as input, while the actual situation is more like a step function with the steps located where lpbr jumps bits. Serge (Batalov) posted a patch to fix this in some thread- I'll see if I can find and link it. Actual rels needed is roughly 21M for 28-bit projects, 40M for 29-bit projects, and (I am told) the low 80s for 30-bit projects. Some polys produce more or fewer duplicate relations, and sometimes a matrix builds with fewer-than-typical relations, so there is a fair amount of variety from project to project. My vague grasp of the "hiccup" mentioned above is that skew alters the area sieved for each special-Q, with higher skews associated with smaller areas. Very high skews may require more special-Q to be searched, and that requirement can lead to using special-Q higher than a poly's efficient sieve range. So it's not that reaching 120% of the script's expected rels is a hiccup- it's that the last few rels might be found at a rate half (or worse?) of the sec/rel you achieved during most of the sieving. If you read through threads of large forum-team-factorizations, you'll see discussions amounting to "we've run out of good Q, now what?". High-skew polys run out of good Q more often than low-skew polys. At single-user-size projects, we can preempt this problem by choosing the next-higher siever version for a project we're even slightly nervous about. We might choose to use 14e instead of 13e for projects a few digits lower than the script's cutoff; in fact, I edited my factmsieve code to shift the cutoff a bit lower. As Mr Womack points out, this makes factorizations in the 135 to 150 digit level more fire-and-forget at the expense of a few hours of sieving. I have not yet attempted a 30-bit project myself to know how much of this extends upward. -Curtis Last fiddled with by VBCurtis on 2013-10-14 at 20:02 Reason: added info in first paragraph

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Poly search candidates	schickel	Msieve	32	2013-11-05 19:11
Resume msieve poly search job?	Andi47	Msieve	1	2011-03-28 04:30
gpu poly search error	bdodson	Msieve	10	2010-11-09 19:46
Poly search for c157 from 4788:2422	henryzz	Aliquot Sequences	59	2009-07-04 06:27
Poly search for c137 from 4788:2408	axn	Aliquot Sequences	15	2009-05-28 16:50

2013-10-12, 17:38	#2
VBCurtis "Curtis" Feb 2005 Riverside, CA 3·1,999 Posts	If the "expected score" is accurate at this size, you should not search further. You may well find a poly that's 5% faster by completing the search, but it's pretty clear that 5% of sieve time is greater than the poly-search time. However, the Expected Score code is simply guesswork- without previous experience about its accuracy, you don't know if you might improve by 10% or more. I'd compromise, and search a couple more hours- if nothing comes close in that time, I'd assume I got lucky at the outset and proceed to sieving. A5 coefficients below 10000 should not be searched- msieve takes longer at very low A5 values to do the same work. Also note skew is 50M, very high for this size of number; this occasionally causes hiccups in later stages (I have not run into such a hiccup yet, but I follow Frmky's advice to use large A5, say 5-50M for this size number). Large A5 coefficients have lower skews than very small values.

2013-10-12, 18:32	#3
EdH "Ed Hall" Dec 2009 Adirondack Mtns 2²×11×131 Posts	Thanks! My impatience got me to break in at about 2.5 hours of searching and that was the poly chosen - no others were close. My first set of relations came in at 2.2% of the estimated minimum (32523338) in about 1.2 hours. This calculates to (very) roughly 55 hours for sieving, although a couple of the machines will be off at night. I guess I'll see how it turns out...

2013-10-12, 19:44	#4
EdH "Ed Hall" Dec 2009 Adirondack Mtns 1011010000100₂ Posts	Wow! I have a new estimate for sieving time of ~26 hours. I guess the first estimate hadn't received relations from several of the machines. I'll have to see how it works out in reality. The "Wow!" part is that I remember taking over two weeks to factor c100s...

2013-10-13, 14:14	#5
EdH "Ed Hall" Dec 2009 Adirondack Mtns 1011010000100₂ Posts	There I was! closing in on a matrix, when the power company lost control, and my scripts weren't robust enough to carry through a restart, so I had to resort to semi-manually* completing the job. So much for an accurate timing for this composite factorization... Oh, well, if anything good has come of it, it got me off my a** to place the main factoring machine on a UPS that was already sitting there, waiting to be put into use... *semi-manually meaning a manual restart of factmsieve.py and manually concatenating all the relations from those machines that are still running...

2013-10-13, 19:45	#7
wombatman I moo ablest echo power! May 2013 2²×3×5×31 Posts	One thing to try is restoring the relations found using the spairs.gz file like you're doing, deleting all the .cyc and such, and then rerunning using the "-nc" command. That should take of it, if I understand your error correctly. I've had to do that before when my .dat file disappeared.

2013-10-14, 15:56	#9
EdH "Ed Hall" Dec 2009 Adirondack Mtns 2²×11×131 Posts	The matrix finally built properly for a solve...

2013-10-14, 16:00	#10
wombatman I moo ablest echo power! May 2013 11101000100₂ Posts	I have that issue sometimes as well--I've gotten to 120% of the estimated relations before the matrix builds, even when using a large interval step. Maybe somebody better versed in this can suggest a cause?