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.

[science_man_88]

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

as for the other part I'm clueless.

[Christenson]

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.

[Mr. P-1]

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.

[Christenson]

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

[Mr. P-1]

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.

[Christenson]

Excellent explanation!

[KingKurly]

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.

[Christenson]

Hey King Kurly,
What about the P-1 on the 30-40M range? The bounds felt very uneven.....

[KingKurly]

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.

[Christenson]

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.