Featured request

[lorgix]

Originally Posted by bsquared

It will work and you can use it, but it becomes increasingly less optimal¹ 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.

¹ 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?

[bsquared]

Originally Posted by lorgix

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.

Originally Posted by lorgix

(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).

Originally Posted by lorgix

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.

[lorgix]

Originally Posted by bsquared

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.

Originally Posted by bsquared

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.

Originally Posted by bsquared

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.

[bsquared]

Originally Posted by lorgix

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).

[Mr. Odd]

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?

[wwf]

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

[jasonp]

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.

[bsquared]

Originally Posted by wwf

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.

[henryzz]

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.

[Antonio]

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.

[jasonp]

Originally Posted by henryzz

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.