Yafu

[lorgix]

Originally Posted by axn

Well, it is evaluating 306!+1. 428498317330021 = 307 · 1395759991303, and 16347718253437 = 307 · 53249896591. All three are factors of 306!+1 (http://www.factordb.com/index.php?id...00000002850330). BTW, ecm is not deterministic, so you can and will see different outputs from running similar ecm curves on the same number.

Good point, I too noticed when I factored the composites.


I know ECM is probabilistic. But I don't expect consistency (which in this case would be pretty much inconsistency) from something that is erroneous.

[lorgix]

Originally Posted by bsquared

Yes... there is a bug in my factorial function which skips the last term if it is prime.

I will post fixed binaries tonight on sourceforge.

Sorry about that

It happens I guess. I wish I had the skills to create something similar to YAFU...

---

What's the rationale behind the new behavior of the factor()-command?
It appears to me that to few curves are run. Also, and I haven't done the math here, could it possible be better to run pm1 without stg2 the first time? Seeing as it may be run more than once again if no factor is found.

Is there a way for me to tailor the behavior of the command?

Why is there still a 4e9 limit in ECM?


And a more general question; Why do some implementations of ECM raise the bounds in so few and big steps? Is it somehow costly to raise the bounds more often, running fewer curves at each level? I don't get it.


Thanks a lot for your continuing work improving YAFU!

[bsquared]

Good questions.

Originally Posted by lorgix

What's the rationale behind the new behavior of the factor()-command?

The same as it was before... to optimize the balance of time spent pretesting prior to QS (or now GNFS). Pretesting is defined as anything which is not guaranteed to factor the number: like p+1, p-1, rho, or ecm. Hopefully it does a better job of it now... and soon I'm going to release an improvement which will make it better yet.

The optimal balance of time is in reality a complex question... but reasonable approximations of optimal are much simpler. Right now, factor() targets spending 1/4 of the time QS is estimated to take on pretesting. The improvement I hinted at is a new tuning function which will hopefully provide better estimates of how long QS (and NFS) is expected to take for a given input. The crossover between QS and NFS will also be computed.

Originally Posted by lorgix

It appears to me that to few curves are run. Also, and I haven't done the math here, could it possible be better to run pm1 without stg2 the first time?
Seeing as it may be run more than once again if no factor is found.

It may be that you're right. As of now, the estimate for how long QS will take is computed from example factorizations I've done using the few different machine types available to me. If you're running on a machine which is different from one of those which I've pre-computed regression curves for, YAFU tries to make the best choice that it can - but it likely won't be right. The tuning mechanism I'm building right now will help fix this - people can dial in the performance of factor() by running the tune function for their individual machines...

As for no stg2 in pm1... its hard to say. Yes, sometimes pm1 is run again with higher bounds, and either restarting from a saved B1 checkpoint or not doing stg2 the first time would be a savings. But on the other hand sometimes factors are found in stg2 the first time around, which would prevent all subsequent work from needing to be run, which would be a savings the other way. And on a third hand, either of these two mechanisms seem like too much work to implement for the potential savings. We're talking about saving 10% or so of a single pm1 curve at higher bounds... when potentially hundreds of much longer ecm curves would be run anyway. I'm not motivated enough to do anything about it :)

Originally Posted by lorgix

Is there a way for me to tailor the behavior of the command?

Right now it's not very flexible. Soon there will be a few ways to tailor it: you'll be able to set the target ECM/QS or ECM/NFS ratios in the yafu.ini file or from the command line. If you like to run more ecm curves, for example, you'd be able to set the target ratio from 0.25 (where it is fixed at now) to 0.3 or 0.35.

Originally Posted by lorgix

Why is there still a 4e9 limit in ECM?

Because when I first wrote the command line parser, I didn't have an easy way to parse integers greater than 32 bits. Is this really an issue for you in everyday use? (By the way, that limit should only apply to B1)

Originally Posted by lorgix

And a more general question; Why do some implementations of ECM raise the bounds in so few and big steps? Is it somehow costly to raise the bounds more often, running fewer curves at each level? I don't get it.

No, it costs nothing to change bounds, and the overhead per curve is very low. The answer is "Conventional Wisdom" I guess. People usually talk about something being "ecm pretested" to B1 bounds in increments of 5 digits. Those B1 values are helpfully specified in gmp-ecm's README. So I just picked those as my breakpoints.

Originally Posted by lorgix

Thanks a lot for your continuing work improving YAFU!

You're welcome!

[axn]

Originally Posted by bsquared

The same as it was before... to optimize the balance of time spent pretesting prior to QS (or now GNFS). Pretesting is defined as anything which is not guaranteed to factor the number: like p+1, p-1, rho, or ecm. Hopefully it does a better job of it now... and soon I'm going to release an improvement which will make it better yet.

The optimal balance of time is in reality a complex question... but reasonable approximations of optimal are much simpler. Right now, factor() targets spending 1/4 of the time QS is estimated to take on pretesting. The improvement I hinted at is a new tuning function which will hopefully provide better estimates of how long QS (and NFS) is expected to take for a given input. The crossover between QS and NFS will also be computed.

This is based on my experimentation with aliqueit. In my experience, p+1, p-1, and rho are not really needed. Instead jumping directly to ecm is more profitable (and simpler). Just start from a suitably small level (say 15 digits).
The other thing is, you can have a more aggressive ramp up of ecm levels without compromising the efficiency. I use 70% of the recommended # of curves(where probability is 50-50 that there are no factors of the target size) before switching to the next higher level. The final level can have the full set of recommended curves.

[bsquared]

I just updated the windows binaries on sourceforge. These contain a fix for the bug in the factorial routine (thanks lorgix!).

[Karl M Johnson]

Ok, seems I have trouble with nfs()
Used Mathematica to generate a composite number 65379518567343825609926638717478788763550229961891453899594186887691561214942200786222079232433049, which has 2 divisors.

Here's the batchfile calling Yafu:

yafu-32k-x64.exe -threads 4 -v -rhomax 800000 -fmtmax 299396627 -ggnfs_dir "C:\Program Files (x86)\msieve\ggnfs" <factorme.txt

Now, the thing is, that since yafu was executed, it was using 25% of CPU, and the private bytes usage has been rising by 120kb / sec, but nothing happens.It now uses 200MB of private bytes, and it's still rising, and still 25% cpu usage.
I'm using latest sourceforge binaries.
http://img6.imageshack.us/img6/2197/yafu.png

Any light ?

[lorgix]

Originally Posted by bsquared

The same as it was before... to optimize the balance of time spent pretesting prior to QS (or now GNFS). Pretesting is defined as anything which is not guaranteed to factor the number: like p+1, p-1, rho, or ecm. Hopefully it does a better job of it now... and soon I'm going to release an improvement which will make it better yet.

Originally Posted by bsquared

The optimal balance of time is in reality a complex question... but reasonable approximations of optimal are much simpler. Right now, factor() targets spending 1/4 of the time QS is estimated to take on pretesting. The improvement I hinted at is a new tuning function which will hopefully provide better estimates of how long QS (and NFS) is expected to take for a given input. The crossover between QS and NFS will also be computed.

Originally Posted by bsquared

Right now it's not very flexible. Soon there will be a few ways to tailor it: you'll be able to set the target ECM/QS or ECM/NFS ratios in the yafu.ini file or from the command line. If you like to run more ecm curves, for example, you'd be able to set the target ratio from 0.25 (where it is fixed at now) to 0.3 or 0.35.

I guess it depends very much on the circumstances... As an example, say you're taking numbers from factordb to factor. If the db has exhausted its arsenal then the first dozen or so steps the factor()-command takes will mostly be wasted. On the other hand, jumping straight to curves with B1=250k won't be very efficient if we randomly pick a number.

Allowing some manual, user tuning the way you're planning is probably the best. I think few people use YAFU to factor random integers...

Originally Posted by bsquared

It may be that you're right. As of now, the estimate for how long QS will take is computed from example factorizations I've done using the few different machine types available to me. If you're running on a machine which is different from one of those which I've pre-computed regression curves for, YAFU tries to make the best choice that it can - but it likely won't be right. The tuning mechanism I'm building right now will help fix this - people can dial in the performance of factor() by running the tune function for their individual machines...

So it may be that it runs particularly far from optimal on my system.

This tuning thing sounds very interesting!

Originally Posted by bsquared

As for no stg2 in pm1... its hard to say. Yes, sometimes pm1 is run again with higher bounds, and either restarting from a saved B1 checkpoint or not doing stg2 the first time would be a savings. But on the other hand sometimes factors are found in stg2 the first time around, which would prevent all subsequent work from needing to be run, which would be a savings the other way. And on a third hand, either of these two mechanisms seem like too much work to implement for the potential savings. We're talking about saving 10% or so of a single pm1 curve at higher bounds... when potentially hundreds of much longer ecm curves would be run anyway. I'm not motivated enough to do anything about it :)

The way I see it the effort could be split up, to be more efficient. And going over the same space more than once is hardly efficient.

Everything you say makes sense. But I think it would be interesting to try
... > pm1 stg1 > pp1, some ECM & other stuff > pm1 stg1 extended (from save file pref. obv.) +stg2 > ...

But, even if my intuition is right the gains would be small so... Well you said it.

Originally Posted by bsquared

Because when I first wrote the command line parser, I didn't have an easy way to parse integers greater than 32 bits. Is this really an issue for you in everyday use? (By the way, that limit should only apply to B1)

I don't actually know that/if it applies to B1, but it does apply to B2!

If I enter a big enough number into factor() it will eventually run ECM with B1=10M, B2=1B and then B1=100M, B2=4B after stating that primes above 4e9 aren't supported in ECM.

Hardly a big problem. I occasionally use ecm() to run curves with B1=20M, B2=4B.

Originally Posted by bsquared

No, it costs nothing to change bounds, and the overhead per curve is very low. The answer is "Conventional Wisdom" I guess. People usually talk about something being "ecm pretested" to B1 bounds in increments of 5 digits. Those B1 values are helpfully specified in gmp-ecm's README. So I just picked those as my breakpoints.

"Conventional Wisdom" is the only answer I've been able to find.

I understand that people stick to GMP-ECM-standard for reasons of simplicity.

But unless I'm missing something here (and that may very well be the case), there are gains to be made.

This really confuses me, cause this is all about efficiency.

But I don't hear people questioning this convention. Alpern's app even skips bounds (don't get me wrong; I love that nifty app).

(Btw, YAFU abandons the standard after B1=1M, and doesn't comply at all when B2 is considered. Again, not a problem.)


Another thing; I often run more than one instance of YAFU from one directory. Could it be arranged so that (automatically) the second instance of QS doesn't fail because of the data file from the first?

Also, would it be troublesome to make a command that runs like factor() but uses only ECM? It could use the standard values and/or allow the user to set bounds and number of curves. I really like the factor()-command, but I think a command like that would be appreciated by many as well. For situations where you know that the number you are entering lack small and/or smooth factors.

axn almost asked for it a few posts up. Even though I don't quite agree with axn about factor(). But I don't think he would kick out rho, pp1 & pm1 from a 'general purpose'-factoring-command. I think what axn is talking about is what I described above; when you know there are no small factors. Correct me if I'm wrong.

[jasonp]

Rho is there because it's very fast when you want 6-8 digit factors, faster than any of the other methods. One P+-1 curve is also much faster than one ECM curve, so if you're budgeting time in units of ECM curves, then P+-1 can be run with much larger B1 in the same time one ECM curve needs (the conventional wisdom uses a P-1 B1 of 10x the ECM B1 and a P+1 B1 of 5x the ECM B1). So for the same cost as an ECM curve you have a much better chance of finding factors that are susceptible to P+-1; it's extra 'resolving power' for free.

ECM will always be able to find factors that the other methods miss; the point is that you don't have to go to the trouble of using ECM when it is overkill. There's a minor additional point that when an input has factors of different sizes, using ECM with too large a B1 will find multiple factors at once.

For example, if an input has a 6, 10 and 20 digit factor and you run ECM intended to find the 20-digit factor, you'll spend a lot of time on one curve and then probably find the product of all three of those factors. Which is fine, but if you want each factor individually you aren't don't yet. You could have found the 6-digit factor in 1% of the ECM time and the 10-digit factor in maybe 5% of the ECM time, leaving the 20-digit factor for ECM to find; knowing the other factors also makes the ECM arithmetic faster.

[bsquared]

Originally Posted by Karl M Johnson

Ok, seems I have trouble with nfs()
Used Mathematica to generate a composite number 65379518567343825609926638717478788763550229961891453899594186887691561214942200786222079232433049, which has 2 divisors.

Here's the batchfile calling Yafu:

yafu-32k-x64.exe -threads 4 -v -rhomax 800000 -fmtmax 299396627 -ggnfs_dir "C:\Program Files (x86)\msieve\ggnfs" <factorme.txt

Now, the thing is, that since yafu was executed, it was using 25% of CPU, and the private bytes usage has been rising by 120kb / sec, but nothing happens.It now uses 200MB of private bytes, and it's still rising, and still 25% cpu usage.
I'm using latest sourceforge binaries.
http://img6.imageshack.us/img6/2197/yafu.png

Any light ?

I'm seeing the same thing. The first thing is that the command line parser doesn't know to remove the quotes around the ggnfs_dir string. So for now, try adding this line to the yafu.ini file instead:

ggnfs_dir=C:\Program Files (x86)\msieve\ggnfs\

Even doing that, it still just sits there for me. But if I move the command from the factorme.txt file and put it on the command line, it works fine. Or, try it in a batchfile:

yafu-32k-x64.exe -threads 4 -v -rhomax 800000 -fmtmax 299396627 -batchfile factorme.txt

[Karl M Johnson]

Originally Posted by bsquared

yafu-32k-x64.exe -threads 4 -v -rhomax 800000 -fmtmax 299396627 -batchfile factorme.txt

Worked, but not.
Even in ini files, the path to sievers require quotes.
Relative pathing, maybe, like ggnfs_dir=/sievers/ ( folder sievers, which exists in dir, where yafu was called from).

P.S. Small feature suggestion - if, while doing polyselect, YAFU is killed, then, when restarted, proceed with sieving and other steps.
It can be done manually though :-)

Since I've already spoken, another feature suggestion: "parallelize polyselection".
From my point of view, it can be done like this.
When msieve's polyselection starts, it says "searching leading coefficients from 1 to 14167290".
Why not launch N msieve instances, each doing it's own work in that range ?
For instance, if it's [1;14167290], and CPU has 2 cores, it can be split to [1;7083645] and (7083645;14167290].
The only thing that bothers me that, even the figures look evenly split, they may take different time to finish. K.

[bsquared]

Originally Posted by Karl M Johnson

Worked, but not.
Even in ini files, the path to sievers require quotes.
Relative pathing, maybe, like ggnfs_dir=/sievers/ ( folder sievers, which exists in dir, where yafu was called from).

It works without quotes for me in the .ini file. In the code, I copy whatever string follows the equals sign and directly paste it in front of the lasieve binary name. So the quotes gets in the way. No doubt I should do some smarter processing here. Relative path names also work in the .ini file, for me.

Originally Posted by Karl M Johnson

P.S. Small feature suggestion - if, while doing polyselect, YAFU is killed, then, when restarted, proceed with sieving and other steps.
It can be done manually though :-)

Since I've already spoken, another feature suggestion: "parallelize polyselection".
From my point of view, it can be done like this.
When msieve's polyselection starts, it says "searching leading coefficients from 1 to 14167290".
Why not launch N msieve instances, each doing it's own work in that range ?
For instance, if it's [1;14167290], and CPU has 2 cores, it can be split to [1;7083645] and (7083645;14167290].
The only thing that bothers me that, even the figures look evenly split, they may take different time to finish. K.

Good suggestions... I'll see what I can do to incorporate them.