Optimal Sieving Time
 

Has anyone managed to:

(1) Calculate the approximate time an n will take(the general formula), and...

(2)Come up with a formula to optimize sieving, which I guess would require a "yes" answer to number 1.

(1)

I did an Excel power fit on some PRP timings and came up with:

PRP Test Time = C * n ^ e

where C depends on your machine and e is about 2.15 +/- 0.05

(2)

Not optimal, but pretty good: Determine range of n you will test: n_min < n < n_max. Determine T1 = TestTime(n_min) and T2 = TestTime(n_max). Sieve until NewPGen is removing candidates at rate of 1 n every (T1+2*T2)/3.

You'll get a better approximation with c*n^2*log(n). Here n*log(n) factor comes from the performance of FFT multiply and the other n comes from the number of multiplications required for a PRP exponentiation sequence.

However there is an added complexity -- FFT performance doesn't scale very smoothly with n -- it changes abruptly as n increase (as and when the FFT length used changes).

My original formula(I'll use this new one in the future) was to take the n 4/5s of the way from the minimum n to the maximum n and sieve until I was removing candidates at about that rate. I tried this new formula, and it only shortened my time by about 4 minutes.

Btw, I'm sieving from 70,000 to 500,000(yes, I know it's high) and the optimal number seems to be about 3 hours 45 min. Or, since I tend to get impatient, it means I'll quit when the last 10 n's removed take 37.5 hours.

I did some rough calculations for the range you are considering, Jasong. With such a large range, you should stop sieving around (0.36) T_max. That will certainly shorten the time you spend sieving.

I'll write more later that explains how I came up with this...

[QUOTE=jasong]My original formula(I'll use this new one in the future) was to take the n 4/5s of the way from the minimum n to the maximum n and sieve until I was removing candidates at about that rate. I tried this new formula, and it only shortened my time by about 4 minutes.

Btw, I'm sieving from 70,000 to 500,000(yes, I know it's high) and the optimal number seems to be about 3 hours 45 min. Or, since I tend to get impatient, it means I'll quit when the last 10 n's removed take 37.5 hours.[/QUOTE]
Okay, I've been thinking about it, and since my Sempron probably won't be PRPing the entire range, I'd like to know the C value of the above listed equation for a 3GHz Pentium, so I can sieve relative to that.

thanks

I don't have access to a 3 Ghz P4 right now, but I did some tests on a 3.2 Ghz machine. I arrived at

Time = (3*10^(-8))* n ^ 2.02.

An n=500000 test will take about 10500 seconds or 2.9 hours.

I would sieve until NewPGen is removing candidates at a third of that... or about 80 minutes per n.

Hope this helps.

80 minutes it is.

Here's the formula I came up with:

1. Assume Time = C * n ^ e. (I agree with axn1 that n^2 * log (n) might be a better formula, but at our low n values, the formula here works very well) Both C and e will depend on your machine and the version of PRP (or pfgw) you are using. These are easily found by doing a power-law fit in Excel.

2. Assume you will test over range n_min < n < n_max with T(n_min) = T_min and T(n_max) = T_max.

3. Calculate the average value of T(n) over the range [n_min,n_max]; this is approximately the integral of T(n) over the range of n values divided by (n_max-n_min)

4. After some algebra I came up with:

T_average = [T_max/(e+1)]*[(1-x^(e+1))/(1-x)], where x = n_min/n_max.

Note the limiting values x = 0 (T_ave = T_max/(e+1) and x =1 (T_ave = T_max) .

5. Sieve with Newpgen until the removal rate is 1 n every T_average.

Hope this helps. Any comments welcome.

Guys, quick question: My computer went kaput a few days ago(this is a loaner), but I'm going to get a computer for my birthday. It will probably be a dual-core 3GHz Pentium-D.

As per the equation in another thread(the one that included log(n) ), what is the value of C for one of my cores?

Educated guesses are welcome.

[QUOTE=masser;78201]Here's the formula I came up with:

1. Assume Time = C * n ^ e. (I agree with axn1 that n^2 * log (n) might be a better formula, but at our low n values, the formula here works very well) Both C and e will depend on your machine and the version of PRP (or pfgw) you are using. These are easily found by doing a power-law fit in Excel.

2. Assume you will test over range n_min < n < n_max with T(n_min) = T_min and T(n_max) = T_max.

3. Calculate the average value of T(n) over the range [n_min,n_max]; this is approximately the integral of T(n) over the range of n values divided by (n_max-n_min)

4. After some algebra I came up with:

T_average = [T_max/(e+1)]*[(1-x^(e+1))/(1-x)], where x = n_min/n_max.

Note the limiting values x = 0 (T_ave = T_max/(e+1) and x =1 (T_ave = T_max) .

5. Sieve with Newpgen until the removal rate is 1 n every T_average.

Hope this helps. Any comments welcome.[/QUOTE]

Because of a conversation in another subforum, I wanted to add a note to this old thread. All of the empirical evidence I have accumulated suggests e=2 is a very good approximation above. So for large n ranges where x = n_min/n_max is nearly zero, a reasonable suggestion would be to sieve until the rate is T_max/(2+1) = T_max/3.