Factoring Speeds

[Khemikal796]

Was just checking up on the status and I remembered something that I thought might be a good bit of info for people looking at starting, or just wanting to know. I remember from back ago that certain exponents required different size FFTs, could be wrong on this, even when factoring. Or is it ram size or something? Anywho I know that one of the breakpoints in this is in the range that Im currently doing, if I remember correctly. I was wondering if someone knew where the breakpoints were exactly so that we can gauge what ranges would be best for our certain speed computers. Thanks in advanced, and hope my vagueness isnt

P.S. Im doing the 35-35.2 range currently

[dsouza123]

One of the help files that comes with Prime95 has the breakdown
of bit depths to factor to (ie 2^67 etc) by exponent range.

There was a thread a while ago that delt with various bit depths
ie 2^64 versus 2^65 where the time increases by some factor, and
which type of CPUs are most efficient, 2^65+ for P4 because of SSE2.

[Khemikal796]

Ive checked the readmes that come with P95 for the breakpoints in the size of the FFT that each range of exponents use. Am I just missing it?

As for bit depths I understand that perfectly. Im just curious as to at what points does the computer see an increase in the time it takes to factor a certain number.

For example:
2^3,000,000-1 factoring to 60 bits is a lot faster than 2^35,000,000-1 because 35,000,00 > 3,000,000. The computer needs more resources or something to work with the bigger number, thus making it slower.

Im wandering where the breakpoints are for things like this. Does this 2nd post help any more???

[hbock]

Originally Posted by Khemikal796

For example:
2^3,000,000-1 factoring to 60 bits is a lot faster than 2^35,000,000-1 because 35,000,00 > 3,000,000. The computer needs more resources or something to work with the bigger number, thus making it slower.

No, it's vice versa. Due to the fact that a factor has the form q=2*k*P+1, where P is the prime exponent itself and k is an integer >=1, the range for k to investigate for a given factor size increases in the same way as the size of the exponent decreases.
Furthermore, TF is not using FFT but LL does. And the optimal factoring depth depends on the time used for LL as described in the math section. The time for LL depends of course on the FFT size used which you can find for example in the benchmark section.
So, the factoring depth for TF changes from 68 to 69 bits starting at 35.1M (your range) but from 34.56M a new FFT size of 2048K is used (depends slightly on whether SSE2 is used or not). These are two different crossovers.

[dsouza123]

For trial factoring as the exponent increases and passes a range boundary
it is both faster and slower.

Faster at the same bit depth but slower overall (takes longer) because of an extra bit depth is tested.

As the exponent increases there are fewer potential factors at a given
bit depth (ie 2^64) as hbock detailed, 30M will have more pf than 35.2M but
35.2M will have to do an extra bit depth 2^69 because it is past the 35.1M boundary
that only tests to 2^68, which will add about twice the time that the 2^68 bit depth took.
If the 2^68 step took 72 hours (3 days) it will take 144 hours (6 days) to do 2^69.

FFT isn't used in trial factoring.

Exponents    Trial
up to        factored to
---------    -----------
3960000         2^60
5160000         2^61
6515000         2^62
8250000         2^63
13380000       2^64
17850000       2^65
21590000       2^66
28130000       2^67
35100000       2^68
44150000       2^69
57020000       2^70
71000000       2^71
79300000       2^72

[Khemikal796]

Thanks guys. Couldnt remember exactly what kinda of breakpoint there was in my range, and was shooting blindly at a corresponence between the factoring and the time taken to LL, thus the FFT talk. Wasnt too far off on my guess, just missing lots of details