mersenneforum.org  

Go Back   mersenneforum.org > New To GIMPS? Start Here! > Information & Answers

Reply
 
Thread Tools
Old 2011-07-20, 08:33   #1
Unregistered
 

2×5×7×139 Posts
Default 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.
  Reply With Quote
Old 2011-07-20, 11:51   #2
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts
Default

http://en.wikipedia.org/wiki/Thread_(computer_science) might help I think.

as for the other part I'm clueless.
science_man_88 is offline   Reply With Quote
Old 2011-07-20, 12:25   #3
Christenson
 
Christenson's Avatar
 
Dec 2010
Monticello

24×107 Posts
Default

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.
Christenson is offline   Reply With Quote
Old 2011-07-26, 20:39   #4
Mr. P-1
 
Mr. P-1's Avatar
 
Jun 2003

7×167 Posts
Default

Quote:
Originally Posted by Christenson View Post
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.
Mr. P-1 is offline   Reply With Quote
Old 2011-07-26, 20:46   #5
Christenson
 
Christenson's Avatar
 
Dec 2010
Monticello

24·107 Posts
Default

Quote:
Originally Posted by Mr. P-1 View Post
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....
Christenson is offline   Reply With Quote
Old 2011-07-27, 01:37   #6
Mr. P-1
 
Mr. P-1's Avatar
 
Jun 2003

7·167 Posts
Default

Quote:
Originally Posted by Christenson View Post
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
Mr. P-1 is offline   Reply With Quote
Old 2011-07-27, 01:39   #7
Christenson
 
Christenson's Avatar
 
Dec 2010
Monticello

24×107 Posts
Default

Excellent explanation!
Christenson is offline   Reply With Quote
Old 2011-07-27, 02:18   #8
KingKurly
 
KingKurly's Avatar
 
Sep 2010
Annapolis, MD, USA

101111012 Posts
Default

Quote:
Originally Posted by Mr. P-1 View Post
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.
KingKurly is offline   Reply With Quote
Old 2011-07-27, 02:51   #9
Christenson
 
Christenson's Avatar
 
Dec 2010
Monticello

6B016 Posts
Default

Hey King Kurly,
What about the P-1 on the 30-40M range? The bounds felt very uneven.....
Christenson is offline   Reply With Quote
Old 2011-07-27, 03:10   #10
KingKurly
 
KingKurly's Avatar
 
Sep 2010
Annapolis, MD, USA

33·7 Posts
Default

Quote:
Originally Posted by Christenson View Post
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.
KingKurly is offline   Reply With Quote
Old 2011-07-27, 12:34   #11
Christenson
 
Christenson's Avatar
 
Dec 2010
Monticello

171210 Posts
Default

Quote:
Originally Posted by KingKurly View Post
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.
Christenson is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
GM200 will not speed up LL Karl M Johnson GPU Computing 2 2015-10-10 05:43
Different Speed in different OS's Dubslow Software 11 2011-08-02 00:04
LL test speed up? jebeagles Miscellaneous Math 16 2006-01-04 02:43
Question on speed lpmurray Software 1 2005-06-24 02:54
Speed issues... Xyzzy Lounge 42 2003-10-08 01:27

All times are UTC. The time now is 14:57.

Tue Oct 20 14:57:48 UTC 2020 up 40 days, 12:08, 1 user, load averages: 2.91, 3.02, 2.79

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.