mersenneforum.org > YAFU Featured request
 Register FAQ Search Today's Posts Mark Forums Read

2012-02-29, 05:51   #12
bsquared

"Ben"
Feb 2007

23×163 Posts

Quote:
 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? 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

Quote:
 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?

2012-02-29, 08:06   #13
Random Poster

Dec 2008

179 Posts

Quote:
 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.

2012-02-29, 08:49   #14
LaurV
Romulan Interpreter

"name field"
Jun 2011
Thailand

101000001011012 Posts

Quote:
 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.

2012-02-29, 08:59   #15
LaurV
Romulan Interpreter

"name field"
Jun 2011
Thailand

5×112×17 Posts

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

2012-02-29, 13:56   #16
EdH

"Ed Hall"
Dec 2009

5,419 Posts

Quote:
 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:
Attached Thumbnails

Last fiddled with by EdH on 2012-02-29 at 13:57

2012-02-29, 15:45   #17
bsquared

"Ben"
Feb 2007

374910 Posts

Quote:
 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.

 2012-03-28, 01:04 #18 Dubslow Basketry That Evening!     "Bunslow the Bold" Jun 2011 40 P I typed in a random number: Code: >> 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. Last fiddled with by Dubslow on 2012-03-28 at 02:02
 2012-03-28, 03:52 #19 bsquared     "Ben" Feb 2007 23×163 Posts 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?
 2012-03-28, 05:16 #20 Dubslow Basketry That Evening!     "Bunslow the Bold" Jun 2011 40> q` quits?
2012-03-28, 05:34   #21
CRGreathouse

Aug 2006

22·3·499 Posts

Quote:
 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.

Quote:
 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.

Last fiddled with by CRGreathouse on 2012-03-28 at 05:35

 2012-03-28, 07:25 #22 Dubslow Basketry That Evening!     "Bunslow the Bold" Jun 2011 40

 Similar Threads Thread Thread Starter Forum Replies Last Post ET_ Programming 0 2018-11-01 14:57 Dubslow YAFU 4 2012-03-31 03:07 Xyzzy Lounge 23 2011-03-08 17:50 ixfd64 Software 10 2010-05-31 15:21 rogue GMP-ECM 4 2009-11-23 15:07

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

Fri Mar 31 13:28:01 UTC 2023 up 225 days, 10:56, 0 users, load averages: 0.76, 0.90, 0.92