mersenneforum.org TF speed
 Register FAQ Search Today's Posts Mark Forums Read

 2011-07-20, 08:33 #1 Unregistered   8,581 Posts TF speed I've recently used the option multithreading (from 1 to 4 CPU) of Prime 95 to finish quickly my LL test. Now I'm doing simple TF, but I saw that TF spend the same time when multithreading is set to 1 and when it is set to 4. Can someone explain me what the multithreading does and if is there a way to make TF run faster. Can also someone wrote the name of a book that explain how factoring program work?(I've already read math section but I'd like to learn more) thanks.
 2011-07-20, 11:51 #2 science_man_88     "Forget I exist" Jul 2009 Dumbassville 100000101100012 Posts http://en.wikipedia.org/wiki/Thread_(computer_science) might help I think. as for the other part I'm clueless.
 2011-07-20, 12:25 #3 Christenson     Dec 2010 Monticello 24×107 Posts The first thing you should know about TF is that CUDA-enabled GPUs from NVIDIA are cleaning the clocks of CPUs on TF problems, with speedups from 10-100 times. They use a program called mfaktc, look for the "putting it all together" thread under Hardware/GPU computing. TF per se is a brute-force approach: Sieve for probable candidates, and then calculate 2^exponent-1 mod candidate, lots and lots of times. P-1 (with a Gig or so of RAM) seems to be the most effective way to find factors at the moment when hunting for M48; to give you an idea, ECM works on exponents up to about 2^10M-1, actual factoring efforts are working on 2^1061-1 using GNFS or SNFS, and QS (and its extension, MPQS) is easiest to understand of the actual factoring methods. Read up under the factoring forums, you'll find the beginnings of my own researches in that direction. Be warned: The number theory is hard work.
2011-07-26, 20:39   #4
Mr. P-1

Jun 2003

49116 Posts

Quote:
 Originally Posted by Christenson ECM works on exponents up to about 2^10M-1
You mean "exponents up to 10M" i.e., Mersenne numbers up to 2^10M-1.

This is in any case misleading, in so far as it implies that 10M is the limit of the algorithm. In fact, ECM works just fine on larger exponents too. It's true that GIMPS is coordinating the ECM efforts on exponents up to 10M, but that's an arbitrary ceiling.

2011-07-26, 20:46   #5
Christenson

Dec 2010
Monticello

32608 Posts

Quote:
 Originally Posted by Mr. P-1 You mean "exponents up to 10M" i.e., Mersenne numbers up to 2^10M-1. This is in any case misleading, in so far as it implies that 10M is the limit of the algorithm. In fact, ECM works just fine on larger exponents too. It's true that GIMPS is coordinating the ECM efforts on exponents up to 10M, but that's an arbitrary ceiling.
Yup! an exponent of 2^10M would be a little hard to store on my PC....

I thought that ceiling was at a crossover point where P-1 became a more effective way to find factors....

2011-07-27, 01:37   #6
Mr. P-1

Jun 2003

116910 Posts

Quote:
 Originally Posted by Christenson I thought that ceiling was at a crossover point where P-1 became a more effective way to find factors....
P-1 is always a more effective way to find factors to start with. P-1 to a given set of bounds is equivalent to a single curve of ecm to the same bounds, except the algorithm is cheaper computationally, and you get the 2p in the 2kp+1 form of the factor for free.

In more detail: P-1 only needs k to be smooth to the given bounds. For ecm to find a factor q, you need q+b to be smooth for some small (unknown) b which depends upon both the factor and the curve. Because b is small, q+b is about the same size as q, while k is a factor of 2p smaller than q. Consequently it is more likely to be smooth, so you are more likely to find a factor with P-1 than with ecm to the same bounds.

So why do ecm at all? Because p-1 is a single-shot affair. If you run it again, to the same bounds, you get the same result. The only thing you can do is run it to higher bounds, but the returns from doing this diminish rapidly. With ecm instead of, or as well as increasing the bounds, you can switch to another curve.

To summarise: P-1 is initially cheaper and more effective than ecm, but the ability to switch curves with ecm means that the returns from doing more ecm diminish less rapidly than with p-1.

If you check, you'll find that all or nearly all of the exponents in the ecm range have already had a good p-1 done on them.

Last fiddled with by Mr. P-1 on 2011-07-27 at 01:39

 2011-07-27, 01:39 #7 Christenson     Dec 2010 Monticello 24×107 Posts Excellent explanation!
2011-07-27, 02:18   #8
KingKurly

Sep 2010
Annapolis, MD, USA

33×7 Posts

Quote:
 Originally Posted by Mr. P-1 If you check, you'll find that all or nearly all of the exponents in the ecm range have already had a good p-1 done on them.
Another reason I've done a bunch of P-1 in the 1.9M range is that the bulk of them had been P-1'd to B1=B2=40k. I raised that limit quite a bit and found quite a lot of factors in the process.

To those who would ask why I would do that, I ask why GIMPS does ECM at all above 100k.

 2011-07-27, 02:51 #9 Christenson     Dec 2010 Monticello 24×107 Posts Hey King Kurly, What about the P-1 on the 30-40M range? The bounds felt very uneven.....
2011-07-27, 03:10   #10
KingKurly

Sep 2010
Annapolis, MD, USA

33×7 Posts

Quote:
 Originally Posted by Christenson Hey King Kurly, What about the P-1 on the 30-40M range? The bounds felt very uneven.....
I haven't done much in that range. Which bounds are you referring to? I'm confused here.

2011-07-27, 12:34   #11
Christenson

Dec 2010
Monticello

24·107 Posts

Quote:
 Originally Posted by KingKurly Another reason I've done a bunch of P-1 in the 1.9M range is that the bulk of them had been P-1'd to B1=B2=40k. I raised that limit quite a bit and found quite a lot of factors in the process.
You are saying the original P-1 bounds in the 1.9M range were quite low...I was wondering if you had the same feeling about the p-1 bounds in the (admittedly much larger) 30-40M range, which feel to me quite uneven, but I don't have much of a feel for what constitutes good bounds.

 Similar Threads Thread Thread Starter Forum Replies Last Post Karl M Johnson GPU Computing 2 2015-10-10 05:43 Dubslow Software 11 2011-08-02 00:04 jebeagles Miscellaneous Math 16 2006-01-04 02:43 lpmurray Software 1 2005-06-24 02:54 Xyzzy Lounge 42 2003-10-08 01:27

All times are UTC. The time now is 03:41.

Sun Nov 29 03:41:44 UTC 2020 up 80 days, 52 mins, 3 users, load averages: 1.09, 1.15, 1.27