Featured request

[bsquared]

Originally Posted by LaurV

After I clicked on your "here" and read a couple of posts about the balance between ecm and siqs (mixed in that discussion) some stupid idea came into my mind: would it be possible to start ecm and siqs in the same time on a multithreaded machine?

<snip>

Does it make sense? O is all gibberish?

I think I understand, but I'm having trouble seeing how it makes things faster *on average*. I guess you might save by hitting some time-optimal balance point more accurately, but it's still a guess as to what that time-optimal point might be, and in any case I changed from a time-balanced ecm/qs strategy to a pretest-level-based ecm/qs strategy in version 1.30. I won't even get into the scale of code change that would be required to do something like that

Originally Posted by LaurV

In the past I did many tests with plan=light against plan=normal. Occasionally I used plan=deep but for siqs-factorable cofactors it was never necessarily to go deep with the ecm, only for nfs-factorable composite it made sense to do it. Usually a "light" ecm and siqs was faster per total numbers factored, and only rarely would the "normal" ecm find factors missed by "light" ecm.

Have you done the same with the new plan defaults? Or have you settled on a custom plan ratio that you like?

[Random Poster]

Originally Posted by bsquared

I think I understand, but I'm having trouble seeing how it makes things faster *on average*.

It depends on what you mean by "faster". Usually you do ECM for time x which succeeds with probability p, and if it fails you do QS for time y, so the expected total time is x+(1-p)y; this is less than y iff x/p<y. With the suggested change you would do ECM for x and QS for x at the same time and then possibly QS for y-x, so expected wall-clock time is x+(1-p)(y-x) but expected processor time is 2x+(1-p)(y-x); the expected wall-clock time is less than y iff x<y, but the expected processor time is less than y iff x(1+1/p)<y. So if you only have a single number to factor and don't mind wasting processor time, by all means do ECM on one thread and QS on another at the same time (which should be simple enough to do manually), but YAFU should be optimized to minimize processor time.

[LaurV]

Originally Posted by bsquared

Have you done the same with the new plan defaults? Or have you settled on a custom plan ratio that you like?

No, and no. For a simple and objective reason: I am out of "siqs range". There was a time when I was doing mostly siqs, but now I involved better computers and all my aliquots advanced in the 120-150 digits range and I very seldom try to factor lower stuff. You remember there was a time when I continuously bothered you about siqs (which I still understand, contrary to nfs which I only partially understand), but that time is now "past" as long as I don't need too often to factor under-100-digits composites. Maybe someday I would move my ass and put the hand on the book and try to workout the nfs. But for now I am just using it blind.

[LaurV]

Originally Posted by Random Poster

so the expected total time is x+(1-p)y

Shouldn't be px+(1-p)y? And in fact you get always a better number, no matter if you minimize the wall clock time or the processor time (assuming they are directly proportional), and then no matter if you do one or more factorizations. More factorizations are just one factorization at the power of n, hehe, or say, one-by-one factorization. As said in the former post, this only affects the siqs, where consumed time is comparable with the ecm consumed time (for a siqs-range composite) and you know exactly how many relations you will need, and you can maximize the efficiency (minimize the time spent in ecm+siqs). For nfs - where such optimization would be more wanted - it can not be done (or not so easy, or I don't have enough knowledge about nfs to see how it could be done).

[EdH]

Originally Posted by bsquared

I can't judge interest, maybe others will respond, but as long as you are willing to work fairly independently of me, I'm all for it. Not that I'm trying to distance myself from it, just trying not to create extra work for myself .

BTW, I've thought about this before, but never took it on for one reason or another. One reason is that every time I thought about it I immediately saw opportunity for a multitude of neat bells/whistles that would have been far too time consuming to implement.

Not trying to discourage you... Go for it if it is interesting to you!

As a matter of curiosity, what would you use to create the GUI? Something cross-platform like Qt or tcl/tk, or would it be a windows only thing?

My expectations would be a totally separate front end that would simply offer a lot of the switches and functions as buttons with edit boxes to enter data. Like I did with AliWin, I'd have everything build a "command line" that would be displayed in a central box and by clicking on a "Run YAFU" button, a separate console window would open with that command issued.

Once the new console window is running, the GUI would basically sit, or possibly watch any generated "log" files. It would not interface with the running instance of YAFU, other than terminating it, if that is desired.

At this point I'm looking at only a Windows interface, written in C++, compiled via Dev-C++ with source code and binary available. I'd like to expand it to linux in the future, but I've never been happy with any of the GUI packages I've studied for linux, yet.

It would probably look quite different, but here's an image of AliWin2 running Aliqueit:

[bsquared]

Originally Posted by LaurV

No, and no. For a simple and objective reason: I am out of "siqs range". There was a time when I was doing mostly siqs, but now I involved better computers and all my aliquots advanced in the 120-150 digits range and I very seldom try to factor lower stuff. You remember there was a time when I continuously bothered you about siqs (which I still understand, contrary to nfs which I only partially understand), but that time is now "past" as long as I don't need too often to factor under-100-digits composites. Maybe someday I would move my ass and put the hand on the book and try to workout the nfs. But for now I am just using it blind.

ECM pretesting and -plan apply to nfs too. I guess you are using aliqueit for the ecm and factMsieve for the nfs, which is fine.

[Dubslow]

I typed in a random number:

>> factor(134085979082345987629876542398717)

factoring 134085979082345987629876542398717
using pretesting plan: normal
no tune info: using qs/gnfs crossover of 95 digits

div: primes less than 10000
fmt: 1000000 iterations
rho: x^2 + 3, starting 1000 iterations on C29 
rho: x^2 + 2, starting 1000 iterations on C29 
rho: x^2 + 2, starting 1000 iterations on C24 
Total factoring time = 0.0006 seconds


***factors found***

P4 = 4057
P5 = 75883
P5 = 33289
PRP20 = 13083776549900283863

When I C/V the number into WolframAlpha, it is able to tell me (in the few seconds it takes for the page to load) that this PRP is in fact P. A few 30 digit PRPs were also listed as prime by WolframAlpha. I'm not exactly sure which tests might be best used, but it is apparent that there are tests that prove primality in a (very) short period of time, since WolframAlpha can do it. (They're not using a database, are they? It's certainly not factordb, since I just added that P20 into it, and it said PRP as well. In fact, it seems that FDB needs a better small-P algorithm as well as YAFU. Edit: I just went back to that page on FDB and now it says P, and this was only a minute later.) I'm not sure what WA's (or FDB's) limits are, but I'll test that now.
Edit: What yafu reported as PRP45 and PRP46, factordb report now as P.

[bsquared]

There are certainly algorithms that can prove primalty of such small numbers very quickly, I just haven't implemented any of them (I'm thinking in particular of APRCL). Pretty much all of the time I'm ok with the 1 chance in 4^20 that the PRP's have of actually being composite. If there ever comes a day when I just have to know for sure, I'll go to somewhere like WolframAlpha or Alpertron's webpage :)

Anyone have an APRCL implemention they would want to contribute to YAFU?

[Dubslow]

How about

>> q

quits?

[CRGreathouse]

Originally Posted by Dubslow

When I C/V the number into WolframAlpha, it is able to tell me (in the few seconds it takes for the page to load) that this PRP is in fact P. A few 30 digit PRPs were also listed as prime by WolframAlpha. I'm not exactly sure which tests might be best used, but it is apparent that there are tests that prove primality in a (very) short period of time, since WolframAlpha can do it. (They're not using a database, are they? It's certainly not factordb, since I just added that P20 into it, and it said PRP as well. In fact, it seems that FDB needs a better small-P algorithm as well as YAFU. Edit: I just went back to that page on FDB and now it says P, and this was only a minute later.) I'm not sure what WA's (or FDB's) limits are, but I'll test that now.
Edit: What yafu reported as PRP45 and PRP46, factordb report now as P.

I'm not sure it actually proved primality! Mathematica's PrimeQ only tests probable-primality. Mathematica does have some tests for proving primality but they're fairly weak. It would surprise me if W|A was more able.

Originally Posted by bsquared

There are certainly algorithms that can prove primalty of such small numbers very quickly, I just haven't implemented any of them (I'm thinking in particular of APRCL). Pretty much all of the time I'm ok with the 1 chance in 4^20 that the PRP's have of actually being composite. If there ever comes a day when I just have to know for sure, I'll go to somewhere like WolframAlpha or Alpertron's webpage :)

Anyone have an APRCL implemention they would want to contribute to YAFU?

PARI has an excellent APR-CL implementation, probably the best out there (by my testing, anyway). You can take it under GPLv2+ AFAIK, if your license is compatible.

[Dubslow]

Well, it says "xxx is a prime number.", but I suppose you're right, it could just be a PRP that's "catered to the masses". OTOH, it's clear that FactorDB does use an actual primality test, and it's able to run those on 80+ digit numbers in less than a second, so it is perfectly reasonable. And thanks for the pointer, while I can't do much with it, eventually I will be slightly happier when I use YAFU. As a newcomer only just stretching his sights beyond GIMPS, I had lots of fun using it.