mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > YAFU

Reply
 
Thread Tools
Old 2021-04-06, 16:52   #1
Kvasir
 
Dec 2020

22×5 Posts
Default Bad poly select estimates

When I'm running YAFU and it switches to nfs mode after ECM, it has a habit of producing very optimistic estimates (or very bad performance) for number in the low 100's (100-110 digits or so). The following is an example of poly selection for a C100:

elapsed time of 3861.2958 seconds exceeds 128 second deadline; poly select done.

Why is this? On higher number the estimate is more correct, and the poly selection is often faster.
Kvasir is offline   Reply With Quote
Old 2021-04-07, 13:41   #2
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

2×32×191 Posts
Default

Quote:
Originally Posted by Kvasir View Post
When I'm running YAFU and it switches to nfs mode after ECM, it has a habit of producing very optimistic estimates (or very bad performance) for number in the low 100's (100-110 digits or so). The following is an example of poly selection for a C100:

elapsed time of 3861.2958 seconds exceeds 128 second deadline; poly select done.

Why is this? On higher number the estimate is more correct, and the poly selection is often faster.
I have seen windows builds sometimes take super long on some poly ranges. I have no idea why that happens (yafu relies on msieve here) and it doesn't seem to happen using the linux build.

Assuming that's not the problem here, I would recommend using -psearch avg or -psearch good instead of the default poly search. These options stop as soon as an average (good) poly is found rather than using the timing table, which is in need of an update (especially for smaller C100-C110 numbers).
bsquared is offline   Reply With Quote
Old 2021-04-07, 16:26   #3
charybdis
 
charybdis's Avatar
 
Apr 2020

263 Posts
Default

I think this revision to msieve may be partly responsible? Particularly "deadline_per_coeff = 8640000", which essentially means each leading coefficient is search-range-limited rather than time-limited, so yafu poly selection continues until each thread is done with its first coefficient which could take much longer than the deadline.
charybdis is offline   Reply With Quote
Old 2021-04-07, 17:32   #4
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

D6E16 Posts
Default

Quote:
Originally Posted by charybdis View Post
I think this revision to msieve may be partly responsible? Particularly "deadline_per_coeff = 8640000", which essentially means each leading coefficient is search-range-limited rather than time-limited, so yafu poly selection continues until each thread is done with its first coefficient which could take much longer than the deadline.
Looking into that, thanks.

Here are example runs using a couple different poly search methods on a C100 on Linux. I will repeat this for windows since that seems to be where the problems are. I'm using my development source, but I think it's substantially the same as branches/wip.

with -psearch avg -threads 16
Code:

min E-value: 9.96e-09
poly select deadline: 638
time limit set to 0.18 CPU-hours
expecting poly E from 1.30e-08 to > 1.50e-08
searching for best poly...
new best score = 9.970000e-09, new best line = 1
new best score = 9.999000e-09, new best line = 2
new best score = 1.058000e-08, new best line = 4
new best score = 1.074000e-08, new best line = 10
new best score = 1.167000e-08, new best line = 15
new best score = 1.229000e-08, new best line = 22
new best score = 1.266000e-08, new best line = 61
nfs: best score is currently 1.266e-08
nfs: found poly better than avg quality
elapsed time: 23.4539 seconds (1221 second deadline); poly select done
best poly:
# norm 1.329616e-13 alpha -4.762021 e 1.266e-08 rroots 2
n: 1367334477485823565093737451423720863788304129290026132972003205143914928887277670302322035345002167
skew: 518246.35
c0: 84865267905977794683633125
c1: -1981237361723192340991
c2: -2697204802913816
c3: 5458443142
c4: 12180
Y0: -578836284879405326839926
Y1: 13343770334947

RelProcTime: 76
BLanczosTime: 97
sqrtTime: 14
NFS elapsed time = 770.6109 seconds.
with -psearch fast -threads 16
Code:
elapsed time: 76.4923 seconds (76 second deadline); poly select done
searching for best poly...
new best score = 9.970000e-09, new best line = 1
new best score = 9.999000e-09, new best line = 2
new best score = 1.058000e-08, new best line = 4
new best score = 1.074000e-08, new best line = 10
new best score = 1.167000e-08, new best line = 15
new best score = 1.229000e-08, new best line = 22
new best score = 1.266000e-08, new best line = 61
new best score = 1.428000e-08, new best line = 129

best poly:
# norm 1.695913e-13 alpha -5.449176 e 1.428e-08 rroots 0
n: 1367334477485823565093737451423720863788304129290026132972003205143914928887277670302322035345002167
skew: 460542.11
c0: 264364209926768035382073459
c1: 789976835377316218189
c2: -3043500066840224
c3: -5903074724
c4: 18480
Y0: -521548409549556316408492
Y1: 21442439626079

RelProcTime: 81
BLanczosTime: 112
sqrtTime: 39
NFS elapsed time = 785.6548 seconds.
So, -psearch avg ran poly search 3x faster and ended up with a slightly worse poly. But in the end the times were about a wash. In the first case it spent 3% of the time in poly search and in the second case about 10%. I think either of these is reasonable.

I'll repeat using windows and see if it's much different.
bsquared is offline   Reply With Quote
Old 2021-04-07, 17:45   #5
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

D6E16 Posts
Default

Windows build:

with -psearch avg -threads 8
Code:
nfs: best score is currently 1.266e-08
nfs: found poly better than avg quality
elapsed time: 27.0977 seconds (1221 second deadline); poly select done
searching for best poly...
new best score = 9.970000e-09, new best line = 1
new best score = 1.040000e-08, new best line = 2
new best score = 1.074000e-08, new best line = 6
new best score = 1.167000e-08, new best line = 11
new best score = 1.229000e-08, new best line = 18
new best score = 1.266000e-08, new best line = 61
nfs: creating ggnfs job parameters for input of size 100
best poly:
# norm 1.329616e-13 alpha -4.762021 e 1.266e-08 rroots 2
n: 1367334477485823565093737451423720863788304129290026132972003205143914928887277670302322035345002167
skew: 518246.93
c0: 84865267905977794683633125
c1: -1981237361723192340991
c2: -2697204802913816
c3: 5458443142
c4: 12180
Y0: -578836284879405326839926
Y1: 13343770334947


with -psearch fast -threads 8
Code:
elapsed time: 156.7667 seconds (152 second deadline); poly select done
searching for best poly...
new best score = 9.970000e-09, new best line = 1
new best score = 1.040000e-08, new best line = 2
new best score = 1.074000e-08, new best line = 6
new best score = 1.167000e-08, new best line = 11
new best score = 1.229000e-08, new best line = 18
new best score = 1.266000e-08, new best line = 61
new best score = 1.428000e-08, new best line = 136
nfs: creating ggnfs job parameters for input of size 100
best poly:
# norm 1.695913e-13 alpha -5.449176 e 1.428e-08 rroots 0
n: 1367334477485823565093737451423720863788304129290026132972003205143914928887277670302322035345002167
skew: 460542.12
c0: 264364209926768035382073459
c1: 789976835377316218189
c2: -3043500066840224
c3: -5903074724
c4: 18480
Y0: -521548409549556316408492
Y1: 21442439626079
So, nothing amiss here. I am seeing this message:
"deadline: 638 CPU-seconds per coefficient"

So, I apparently haven't updated to the msieve version that makes this value huge. Although it isn't spending even close to 638 seconds per coefficient, so that may not be the problem.

I think more info is needed from the OP (or anyone else that is having this problem); if you can try to identify where it is getting stuck.

Last fiddled with by bsquared on 2021-04-07 at 17:46
bsquared is offline   Reply With Quote
Old 2021-04-07, 20:33   #6
bur
 
Aug 2020

167 Posts
Default

Quote:
Originally Posted by bsquared View Post
Assuming that's not the problem here, I would recommend using -psearch avg or -psearch good instead of the default poly search. These options stop as soon as an average (good) poly is found rather than using the timing table, which is in need of an update (especially for smaller C100-C110 numbers).
To me this sounds like using these options is a good idea regardless of the problem?

I remember I also saw poly times way above the deadline and wondered why that was the case. I'm running Windows as well. I can't find the exact output in factor.log, but maybe this is similar:

Code:
00:03 v1.34.5 @ DESKTOP-L52QKGR, nfs: commencing nfs on c104: 34993011070188327021795022422892723316227257164667460355154317602942007527742978416465823561057801912707
04/02/21 13:00:03 v1.34.5 @ DESKTOP-L52QKGR, nfs: commencing poly selection with 4 threads
04/02/21 13:00:03 v1.34.5 @ DESKTOP-L52QKGR, nfs: setting deadline of 417 seconds
04/02/21 13:20:10 v1.34.5 @ DESKTOP-L52QKGR, nfs: completed 4 ranges of size 250 in 1206.4288 seconds
 04/02/21 13:20:10 v1.34.5 @ DESKTOP-L52QKGR, nfs: best poly = # norm 4.345715e-014 alpha -5.924812 e 7.622e-009 rroots 4
The deadline is mostly 300-450 s and the actual time 1200-2600 s.

Last fiddled with by bur on 2021-04-07 at 20:34
bur is offline   Reply With Quote
Old 2021-04-08, 00:33   #7
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

7·683 Posts
Default

Bur-
The deadline is *per coefficient*, not per search.
1200 sec on poly select with a deadline per-coefficient of 417 seconds is perfectly consistent. The per-coefficient deadline is because there are occasionally specific first-coeff values that "get stuck" in poly select, so the deadline cuts off that particular search to proceed to the next one.

That deadline could be set quite a bit lower for small inputs (like under 120 digits), but for bigger jobs it does its job.
VBCurtis is online now   Reply With Quote
Old 2021-04-08, 02:13   #8
charybdis
 
charybdis's Avatar
 
Apr 2020

263 Posts
Default

Quote:
Originally Posted by VBCurtis View Post
Bur-
The deadline is *per coefficient*, not per search.
1200 sec on poly select with a deadline per-coefficient of 417 seconds is perfectly consistent. The per-coefficient deadline is because there are occasionally specific first-coeff values that "get stuck" in poly select, so the deadline cuts off that particular search to proceed to the next one.

That deadline could be set quite a bit lower for small inputs (like under 120 digits), but for bigger jobs it does its job.
Actually 417 seconds is yafu's deadline for the whole search, which it prints to factor.log. This is different from the per-coefficient deadline, which only gets printed to the terminal as
Code:
deadline: 8640000 CPU-seconds per coefficient
_____


I don't think this is a Windows vs Linux issue; it's probably related to changes that have been made to msieve. I had a look back at some old logs and it seems the precompiled v1.34.5 Windows binary regularly overshot the deadline:
Code:
09/27/19 21:34:31 v1.34.5 @ scylla, nfs: commencing nfs on c99: 427342969728593249995852717142458734662938233797399924260645630851457103421951613776831171963394999
09/27/19 21:34:32 v1.34.5 @ scylla, nfs: commencing poly selection with 4 threads
09/27/19 21:34:32 v1.34.5 @ scylla, nfs: setting deadline of 289 seconds
09/27/19 21:49:41 v1.34.5 @ scylla, nfs: completed 4 ranges of size 250 in 909.3937 seconds
Clearly some coefficients were taking far too long: only one range was completed per thread. This issue only appeared with degree 4 poly selection, which would explain why Kvasir is seeing it only below 110 digits.

A mingw64 build of v1.35-beta (yafu r379 + msieve r1030) was more reasonable:
Code:
10/19/19 15:51:20 v1.35-beta @ scylla, nfs: commencing nfs on c99: 295246846667425141512796091316580174394940879595078179964227521694311641573564329291532389013361191
10/19/19 15:51:20 v1.35-beta @ scylla, nfs: commencing poly selection with 4 threads
10/19/19 15:51:20 v1.35-beta @ scylla, nfs: setting deadline of 289 seconds
10/19/19 15:51:20 v1.35-beta @ scylla, nfs: expecting degree 4 poly E from 1.33e-008 to > 1.52e-008
10/19/19 15:56:08 v1.35-beta @ scylla, nfs: completed 725 ranges of size 60 in 287.7674 seconds
I had set pbatch=60 to make the ranges smaller, but this would have been okay with the default of 250 too.

However, the search-range per coefficient seems to be much larger for degree 5, so the effect of the 8640000-second deadline is that there isn't time to search many ranges before yafu's whole-search deadline is reached. A single coefficient that takes a long time can still delay the search; this is likely to be a bigger problem on machines with lots of threads.

(this log is from a linux machine but that should be irrelevant)
Code:
05/03/20 09:10:01 v1.35-beta @ selenium, nfs: commencing nfs on c111: 752001002037101772932306843847522458195579123341389985942355224754269877604320469822501875579464492175993551297
05/03/20 09:10:01 v1.35-beta @ selenium, nfs: commencing poly selection with 6 threads
05/03/20 09:10:01 v1.35-beta @ selenium, nfs: setting deadline of 733 seconds
05/03/20 09:10:01 v1.35-beta @ selenium, nfs: expecting degree 5 poly E from 7.56e-10 to > 8.70e-10
05/03/20 09:29:13 v1.35-beta @ selenium, nfs: completed 24 ranges of size 60 in 1151.6684 seconds
This would likely have been worse with the default pbatch=250.

Msieve r1023, which I linked to a few posts back, had lots of changes to the polyselect parameters, so maybe it fixed the issue that Kvasir is seeing with degree 4 numbers, while creating a smaller problem for degree 5 ones. Making pbatch smaller and/or using -psearch avg or fast would seem to be the best workaround.

Perhaps it's time to put a new precompiled Windows binary on sourceforge? The current one is 8 years old.
charybdis is offline   Reply With Quote
Old 2021-04-08, 03:14   #9
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

7×683 Posts
Default

My apologies for the misinformation- I've only used msieve directly, not YAFU, for poly select, so I quoted how msieve works. Mea culpa, and thanks for the correction.
VBCurtis is online now   Reply With Quote
Old 2021-04-08, 08:12   #10
Kvasir
 
Dec 2020

22·5 Posts
Default

Is the -psearch parameter available when I call YAFU from aliqueit? Can it be set up in aliquiet.ini or yafu.ini or something?
Kvasir is offline   Reply With Quote
Old 2021-04-08, 11:26   #11
charybdis
 
charybdis's Avatar
 
Apr 2020

263 Posts
Default

You can set new defaults for yafu command line options in yafu.ini: just add "psearch=avg" or "psearch=fast".
charybdis is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Poly select and planning for 2,2330M VBCurtis Cunningham Tables 70 2021-02-16 06:32
Poly select and planning for 2,2210M swellman Cunningham Tables 51 2020-03-22 22:09
YAFU Poly Select Deadline amphoria YAFU 22 2016-09-17 09:47
msieve poly select: choosing Stage1norm VBCurtis Msieve 0 2016-04-11 21:33
Starting NFS skipping poly select jux YAFU 5 2016-01-02 01:01

All times are UTC. The time now is 05:53.

Thu May 13 05:53:49 UTC 2021 up 35 days, 34 mins, 0 users, load averages: 1.92, 2.16, 2.47

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.