mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > YAFU

Reply
 
Thread Tools
Old 2016-09-14, 15:32   #1
amphoria
 
amphoria's Avatar
 
"Dave"
Sep 2005
UK

2×19×73 Posts
Default YAFU Poly Select Deadline

I am using the YAFU factor() command to factor some C99s on a computer with 8 cores, so threads is set to 8. In factor.log I get the following messages for poly select:

commencing poly select with 8 threads
setting deadline of 148 seconds
completed 8 ranges of size 250 in 875 seconds

The third message is printed 875 seconds after the second message.

My query is that YAFU is spending almost 15 minutes on poly select when the lattice sieving is only taking about 10 minutes on 8 threads. This is excessive.

This is with YAFU v1.34 on Windows 10 64-bit. Is there a problem with the poly select deadline that YAFU is passing to msieve? I know that I can override the poly select deadline in YAFU but I can't work out how to do this with multiple threads.
amphoria is offline   Reply With Quote
Old 2016-09-14, 16:21   #2
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

63468 Posts
Default

Something is wrong... it should be doing way more than 8 ranges of 250. Here is test I just ran:

Code:
nfs: commencing nfs on c100: 18027160975221650182578588284151114970600...
nfs: commencing poly selection with 8 threads
nfs: setting deadline of 152 seconds
nfs: completed 350 ranges of size 250 in 160.2835 seconds
Yafu asks msieve to find polys in small ranges at a time precisely to avoid this problem (any one range taking excessively long to search). In your case it asked for a small range (for each thread, thus 8 total ranges) and those ranges for some reason took a very long time to complete.

Is there something non-standard about your msieve installation? Does it do this on every C99 you've tried or just this one?

Last fiddled with by bsquared on 2016-09-14 at 16:21 Reason: truncated input number
bsquared is offline   Reply With Quote
Old 2016-09-14, 16:24   #3
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

2·13·127 Posts
Default

The YAFU option, btw, that might help here is -pbatch. Change it to something much smaller than 250 (say, 10), and see what that does.

e.g.:
./yafu "nfs(foo)" -pbatch 10 -threads 8 -v
bsquared is offline   Reply With Quote
Old 2016-09-14, 16:47   #4
amphoria
 
amphoria's Avatar
 
"Dave"
Sep 2005
UK

2·19·73 Posts
Default

Quote:
Originally Posted by bsquared View Post
Is there something non-standard about your msieve installation? Does it do this on every C99 you've tried or just this one?
It's the compiled in msieve contained in yafu 1.34 as posted on SourceForge. I have seen the same behaviour on every C99 on this computer and another one with 16 cores and 16 threads with the same yafu version.

I will try reducing the batch size as suggested in your other post.
amphoria is offline   Reply With Quote
Old 2016-09-14, 17:03   #5
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

10110011001112 Posts
Default

Quote:
Originally Posted by amphoria View Post
It's the compiled in msieve contained in yafu 1.34 as posted on SourceForge. I have seen the same behaviour on every C99 on this computer and another one with 16 cores and 16 threads with the same yafu version.

I will try reducing the batch size as suggested in your other post.
That in itself is a bit old.
henryzz is offline   Reply With Quote
Old 2016-09-14, 18:35   #6
amphoria
 
amphoria's Avatar
 
"Dave"
Sep 2005
UK

2·19·73 Posts
Default

Quote:
Originally Posted by bsquared View Post
The YAFU option, btw, that might help here is -pbatch. Change it to something much smaller than 250 (say, 10), and see what that does.

e.g.:
./yafu "nfs(foo)" -pbatch 10 -threads 8 -v
I had to reduce it to pbatch=5 to get close to the deadline.

Quote:
Originally Posted by henryzz View Post
That in itself is a bit old.
I agree but I did not want to build it from source at the time. I am now going to bite the bullet. I have already built mpir and ecm with VS2013 so this should be doable. The only possible complication is that there is no VS2013 non-gpu build directory for msieve, so I am hoping that I can start with the VS2012 one.

Last fiddled with by amphoria on 2016-09-14 at 18:48 Reason: There is a VS2013 build dir.
amphoria is offline   Reply With Quote
Old 2016-09-14, 22:21   #7
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

1100111001102 Posts
Default

Good to know that -pbatch helps, but this doesn't really fix the problem. The problem is that msieve should be able to search leading coefficients up to the 10's of thousands in 150 seconds with 8 threads on a C99. From the sound of it you are searching a range 50x less than that. So we can make it stay around the deadline with this method but you may be finding subpar polys.

Questions:
Can you post the same output you did before with pbatch=5?
This is with the prebuild windows executables correct? Was it actually YAFU 1.34.5 or 1.34?
Can you post a test number? I'll see if I can reproduce this here.
bsquared is offline   Reply With Quote
Old 2016-09-15, 05:19   #8
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

22·7·317 Posts
Default

Same here.
We never found this issue because in all cases, our C99s are done by SIQS, as the crossover is over 100. But if forced to GNFS, it seems that the "long time for poly" behavior is the "normal" one.
LaurV is online now   Reply With Quote
Old 2016-09-15, 08:59   #9
amphoria
 
amphoria's Avatar
 
"Dave"
Sep 2005
UK

2×19×73 Posts
Default

Quote:
Originally Posted by bsquared View Post
Good to know that -pbatch helps, but this doesn't really fix the problem. The problem is that msieve should be able to search leading coefficients up to the 10's of thousands in 150 seconds with 8 threads on a C99. From the sound of it you are searching a range 50x less than that. So we can make it stay around the deadline with this method but you may be finding subpar polys.

Questions:
Can you post the same output you did before with pbatch=5?
This is with the prebuild windows executables correct? Was it actually YAFU 1.34.5 or 1.34?
Can you post a test number? I'll see if I can reproduce this here.
Code:
yafu "nfs(741244879109376246366513985428555418845913568310626508732412421094649581664407020182598936240636611)" -v -pbatch 5
Code:
nfs: commencing nfs on c99: 741244879109376246366513985428555418845913568310626508732412421094649581664407020182598936240636611
nfs: commencing poly selection with 8 threads
nfs: setting deadline of 148 seconds
nfs: completed 67 ranges of size 5 in 200.9028 seconds
nfs: best poly = # norm 1.646415e-013 alpha -4.744248 e 1.356e-008 rroots 4
I haven't managed to get Yafu to print a version number, but the name of the file is yafu-1.34.zip as posted at https://sourceforge.net/projects/yafu/. I am using the executable yafu-x64.exe.
amphoria is offline   Reply With Quote
Old 2016-09-15, 13:42   #10
EdH
 
EdH's Avatar
 
"Ed Hall"
Dec 2009
Adirondack Mtns

22×7×112 Posts
Default

Quote:
Originally Posted by amphoria View Post
[CODE]I haven't managed to get Yafu to print a version number, but the name of the file is yafu-1.34.zip as posted at https://sourceforge.net/projects/yafu/. I am using the executable yafu-x64.exe.
That's v1.34.5. It should open up in a console window by just double-clicking it:
Attached Thumbnails
Click image for larger version

Name:	YAFU1.34.5img.jpg
Views:	117
Size:	54.4 KB
ID:	14919  
EdH is offline   Reply With Quote
Old 2016-09-15, 14:13   #11
amphoria
 
amphoria's Avatar
 
"Dave"
Sep 2005
UK

277410 Posts
Default

Quote:
Originally Posted by EdH View Post
That's v1.34.5. It should open up in a console window by just double-clicking it:
You are correct as I have just realised that the version number is also printed on every line in factor.log.

For completeness I have also built yafu and msieve using VS2013. Yafu and msieve were built from the latest trunk code. This built Yafu 1.34.5 also. However the issue with poly select deadline still exists, so it might be something related to "small" composites.

Last fiddled with by amphoria on 2016-09-15 at 14:13
amphoria is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Running YAFU via Aliqueit doesn't find yafu.ini EdH YAFU 8 2018-03-14 17:22
A Desperate appeal! (by Richard K. Guy)... deadline is September 30, 2016 philmoore Factoring 102 2016-10-01 12:16
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
Time it takes to select polynomials for 154 digits John5788 Factoring 23 2008-08-27 07:54

All times are UTC. The time now is 13:48.

Sat Oct 31 13:48:35 UTC 2020 up 51 days, 10:59, 2 users, load averages: 2.42, 2.54, 2.46

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.