20060418, 01:22  #1 
"Jason Goatcher"
Mar 2005
3×7×167 Posts 
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. 
20060418, 13:34  #2 
Jul 2003
wear a mask
1,613 Posts 
(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. Last fiddled with by masser on 20060418 at 13:41 
20060418, 19:32  #3 
Jun 2003
2×13×191 Posts 
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). 
20060418, 19:56  #4 
"Jason Goatcher"
Mar 2005
3·7·167 Posts 
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. 
20060419, 17:54  #5 
Jul 2003
wear a mask
3115_{8} Posts 
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... 
20060419, 19:32  #6  
"Jason Goatcher"
Mar 2005
110110110011_{2} Posts 
Quote:
thanks 

20060420, 22:13  #7 
Jul 2003
wear a mask
3115_{8} Posts 
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. 
20060422, 03:45  #8 
"Jason Goatcher"
Mar 2005
3·7·167 Posts 
80 minutes it is.

20060423, 16:20  #9 
Jul 2003
wear a mask
1,613 Posts 
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 powerlaw 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_maxn_min) 4. After some algebra I came up with: T_average = [T_max/(e+1)]*[(1x^(e+1))/(1x)], 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. Last fiddled with by masser on 20060925 at 16:58 
20060525, 23:54  #10 
"Jason Goatcher"
Mar 2005
6663_{8} Posts 
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 dualcore 3GHz PentiumD.
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. 
20090125, 15:56  #11  
Jul 2003
wear a mask
1613_{10} Posts 
Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Sieving and LLRin in same time  pepi37  Software  1  20170515 17:17 
Sieving both sides vs one side at a time  paul0  Factoring  5  20151118 13:58 
Thanks PG for Sieving, now time to pick a new n?  cipher  Twin Prime Search  25  20090809 19:32 
Optimal sieving of large nranges  gd_barnes  Conjectures 'R Us  13  20090217 08:28 
prime density vs. sieving vs. prp time  jasong  Math  18  20060331 03:14 