mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > YAFU

Reply
 
Thread Tools
Old 2013-04-23, 16:45   #166
lorgix
 
lorgix's Avatar
 
Sep 2010
Scandinavia

3·5·41 Posts
Default

Quote:
Originally Posted by bsquared View Post
It will work and you can use it, but it becomes increasingly less optimal1 to do so as the numbers go north of 160 digits. This is because you need to put more and more thought into the process to get the best results. For example testing the polynomials via trial sieving, knowing when to stop searching vs. going for a better poly, knowing when to start test building matrices, and using the matrix building options within msieve to their potential, just off the top of my head. These are things I've taken steps toward automating, but I'm not there yet and in any case automation will probably never be as good as an experienced human.

1 As Xilman likes to point out, optimal with respect to what cost function? If you cost function is minimizing human interaction, then maybe YAFU is the right approach even for huge numbers. But it will be decidedly less optimal with respect to a power/calendar time cost function.
Thanks for responding.

I'm not expecting YAFU to replace an experienced human. But I am glad to see that the threshold for how large numbers can be factored automatically with reasonable efficiency may move upwards with some clever automation.

Trial sieving isn't done automatically is it?
Perhaps trial sieve the n best polys after x minutes of searching. Then trial sieve better polynomials as they are found. When the [estimated sieve time] to [poly search time] reaches a certain point, we are done. Or a hybrid between that and the current.

(What values of -pbatch make sense? I'm thinking that for large inputs the optimal value may be substantially larger than 250.)

Is it likely that YAFU will have GPU support in the future?
lorgix is offline   Reply With Quote
Old 2013-04-23, 17:30   #167
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

D0D16 Posts
Default

Quote:
Originally Posted by lorgix View Post

Trial sieving isn't done automatically is it?
At the moment, for GNFS, no. It will do trial sieving of SNFS polys, and the framework is such that it will be straightforward to make the same happen for GNFS, but right now that automation is not implemented.

Quote:
Originally Posted by lorgix View Post
(What values of -pbatch make sense? I'm thinking that for large inputs the optimal value may be substantially larger than 250.)
I don't recommend changing that parameter. You want it big enough so that each thread is doing appreciable work, else the threading overhead will start to dominate, and you want it small enough so that batches finish in a reasonable timeframe, so that we don't overshoot the targeted time to spend in poly select. 250 is a good choice for most inputs (extremely large or small are possible exceptions).

Quote:
Originally Posted by lorgix View Post
Is it likely that YAFU will have GPU support in the future?
It could have GPU support now, for anyone that compiles their own libraries and wants to turn on msieve gpu capability. If you mean gpu support for other stuff like siqs, then in the medium time frame (year-ish) the answer is no.
bsquared is offline   Reply With Quote
Old 2013-04-23, 17:39   #168
lorgix
 
lorgix's Avatar
 
Sep 2010
Scandinavia

10011001112 Posts
Default

Quote:
Originally Posted by bsquared View Post
At the moment, for GNFS, no. It will do trial sieving of SNFS polys, and the framework is such that it will be straightforward to make the same happen for GNFS, but right now that automation is not implemented.
That sounds promising.
Quote:
Originally Posted by bsquared View Post
I don't recommend changing that parameter. You want it big enough so that each thread is doing appreciable work, else the threading overhead will start to dominate, and you want it small enough so that batches finish in a reasonable timeframe, so that we don't overshoot the targeted time to spend in poly select. 250 is a good choice for most inputs (extremely large or small are possible exceptions).
OK, I was under the impression that the optimal value would vary more. Thanks for the info.
Quote:
Originally Posted by bsquared View Post
It could have GPU support now, for anyone that compiles their own libraries and wants to turn on msieve gpu capability. If you mean gpu support for other stuff like siqs, then in the medium time frame (year-ish) the answer is no.
I was mostly thinking about poly search and ECM stage 1.
lorgix is offline   Reply With Quote
Old 2013-04-23, 17:46   #169
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

13×257 Posts
Default

Quote:
Originally Posted by lorgix View Post
I was mostly thinking about poly search and ECM stage 1.
Building GPU Msieve will give you poly search capability today (note: I don't plan on releasing an "official" yafu+gpu-msieve). When/if the production GMP-ECM codebase builds with a gpu option, then we'll have that too (but I also don't plan on an officially supported release with it enabled).
bsquared is offline   Reply With Quote
Old 2013-05-21, 12:58   #170
Mr. Odd
 
Mar 2010

5·11 Posts
Default

I don't know how you'd implement it, but it seems that YAFU could help us all be smarter about using SNFS. A quick calculation up front regarding the equivalent gnfs difficulty would help choose between snfs and gnfs, as well as figuring out how much ECM to do.

For example, the C139 from 10^217+2 will take much less time using GNFS because the SNFS equivalent difficulty is much more. Similarly, 10^131+4 will take no time using SNFS and needs maybe 5 minutes of ECM. Both of these decisions could either be automated or at least presented to the user to choose which course of action is best.

Thoughts?
Mr. Odd is offline   Reply With Quote
Old 2013-08-07, 04:37   #171
wwf
 
May 2013

2×3 Posts
Default Yafu on arm cpu

Has anyone managed to get Yafu working on an arm cpu?
The code seems heavily optimized and I don't see a "generic" path for some functions.

Walter
wwf is offline   Reply With Quote
Old 2013-08-08, 00:47   #172
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

3×1,163 Posts
Default

That's by design, you must have an SSE2 system to compile the code. This was done because it's too much work to maintain a generic branch of code that almost nobody else needs.
jasonp is offline   Reply With Quote
Old 2013-08-08, 02:47   #173
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

13×257 Posts
Default

Quote:
Originally Posted by wwf View Post
Has anyone managed to get Yafu working on an arm cpu?
The code seems heavily optimized and I don't see a "generic" path for some functions.

Walter
It is heavily optimized for Intel/AMD and Jason's right, some time ago we made the decision to stop maintaining generic branches since nobody needed it.

@jason:
Will msieve compile on an ARM? I know it used to, but with all of your recent development I guess I'm not sure anymore. I haven't looked through the source in a while.
bsquared is offline   Reply With Quote
Old 2013-08-08, 14:50   #174
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

7×821 Posts
Default

I am pretty certain fivemack managed to compile it on arm.
I can understand stopping generic x86 but it would be nice if c code existed for things like arm. I would guess in the next few years they will become a viable computing platform here as they use so little power.
fivemack is the one to talk about concerning arm I think.

Last fiddled with by henryzz on 2013-08-08 at 14:51
henryzz is online now   Reply With Quote
Old 2013-10-04, 20:44   #175
Antonio
 
Antonio's Avatar
 
"Antonio Key"
Sep 2011
UK

10238 Posts
Default

Would it be possible to replace the "plan=(light/normal/deep/custom)" in the .ini with:-
qs_plan=(light/normal/deep/custom)
gnfs_plan=(light/normal/deep/custom)
(Bold are just my preferred defaults)
and then automatically select the test plan for a composite according to the qs/gnfs crossover point?

Of course you could go the whole way and also replace "pretest_ratio=" with:-
"qs_ratio=" and "gnfs_ratio="
for those people who want to customize both situations, but I would be very happy if just the first part could be implemented.
Antonio is offline   Reply With Quote
Old 2013-10-06, 01:25   #176
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

DA116 Posts
Default

Quote:
Originally Posted by henryzz View Post
I am pretty certain fivemack managed to compile it on arm.
I can understand stopping generic x86 but it would be nice if c code existed for things like arm. I would guess in the next few years they will become a viable computing platform here as they use so little power.
fivemack is the one to talk about concerning arm I think.
Sorry, I didn't see this when it was asked. Msieve still has a generic code path for everything, mainly because I don't have to maintain a state of the art sieving implementation anymore. You do need a pthreads library after the last linear algebra overhaul.

Fivemack got the code to compile on an ARM eval board, and ran NFS linear algebra on a commendably large matrix given how tiny that system is.
jasonp is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
ARM ASM request ET_ Programming 0 2018-11-01 14:57
Bug/request Dubslow YAFU 4 2012-03-31 03:07
Odd request? Xyzzy Lounge 23 2011-03-08 17:50
Prime95 featured in Maximum PC! ixfd64 Software 10 2010-05-31 15:21
GMP-ECM Request rogue GMP-ECM 4 2009-11-23 15:07

All times are UTC. The time now is 12:58.

Thu Nov 26 12:58:09 UTC 2020 up 77 days, 10:09, 4 users, load averages: 2.09, 1.70, 1.48

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.