20110720, 08:33  #1 
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.

20110720, 11:51  #2 
"Forget I exist"
Jul 2009
Dumbassville
10000010110001_{2} Posts 
http://en.wikipedia.org/wiki/Thread_(computer_science) might help I think.
as for the other part I'm clueless. 
20110720, 12:25  #3 
Dec 2010
Monticello
2^{4}×107 Posts 
The first thing you should know about TF is that CUDAenabled GPUs from NVIDIA are cleaning the clocks of CPUs on TF problems, with speedups from 10100 times. They use a program called mfaktc, look for the "putting it all together" thread under Hardware/GPU computing.
TF per se is a bruteforce approach: Sieve for probable candidates, and then calculate 2^exponent1 mod candidate, lots and lots of times. P1 (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^10M1, actual factoring efforts are working on 2^10611 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. 
20110726, 20:39  #4 
Jun 2003
491_{16} Posts 
You mean "exponents up to 10M" i.e., Mersenne numbers up to 2^10M1.
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. 
20110726, 20:46  #5  
Dec 2010
Monticello
3260_{8} Posts 
Quote:
I thought that ceiling was at a crossover point where P1 became a more effective way to find factors.... 

20110727, 01:37  #6  
Jun 2003
1169_{10} Posts 
Quote:
In more detail: P1 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 P1 than with ecm to the same bounds. So why do ecm at all? Because p1 is a singleshot 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: P1 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 p1. If you check, you'll find that all or nearly all of the exponents in the ecm range have already had a good p1 done on them. Last fiddled with by Mr. P1 on 20110727 at 01:39 

20110727, 01:39  #7 
Dec 2010
Monticello
2^{4}×107 Posts 
Excellent explanation!

20110727, 02:18  #8  
Sep 2010
Annapolis, MD, USA
3^{3}×7 Posts 
Quote:
To those who would ask why I would do that, I ask why GIMPS does ECM at all above 100k. 

20110727, 02:51  #9 
Dec 2010
Monticello
2^{4}×107 Posts 
Hey King Kurly,
What about the P1 on the 3040M range? The bounds felt very uneven..... 
20110727, 03:10  #10 
Sep 2010
Annapolis, MD, USA
3^{3}×7 Posts 

20110727, 12:34  #11 
Dec 2010
Monticello
2^{4}·107 Posts 
You are saying the original P1 bounds in the 1.9M range were quite low...I was wondering if you had the same feeling about the p1 bounds in the (admittedly much larger) 3040M range, which feel to me quite uneven, but I don't have much of a feel for what constitutes good bounds.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
GM200 will not speed up LL  Karl M Johnson  GPU Computing  2  20151010 05:43 
Different Speed in different OS's  Dubslow  Software  11  20110802 00:04 
LL test speed up?  jebeagles  Miscellaneous Math  16  20060104 02:43 
Question on speed  lpmurray  Software  1  20050624 02:54 
Speed issues...  Xyzzy  Lounge  42  20031008 01:27 