Optimal Sieving Time

[jasong]

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.

[masser]

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

[axn]

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

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

[masser]

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

[jasong]

Originally Posted by 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.

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

[masser]

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.

[jasong]

80 minutes it is.

[masser]

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.

[jasong]

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.

[masser]

Originally Posted by masser

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.

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.