 mersenneforum.org Optimal Sieving Time
 Register FAQ Search Today's Posts Mark Forums Read 2006-04-18, 01:22 #1 jasong   "Jason Goatcher" Mar 2005 66638 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.   2006-04-18, 13:34 #2 masser   Jul 2003 Behind BB 36648 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 2006-04-18 at 13:41   2006-04-18, 19:32 #3 axn   Jun 2003 543810 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).   2006-04-18, 19:56 #4 jasong   "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.   2006-04-19, 17:54 #5 masser   Jul 2003 Behind BB 197210 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...   2006-04-19, 19:32   #6
jasong

"Jason Goatcher"
Mar 2005

3×7×167 Posts Quote:
 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   2006-04-20, 22:13 #7 masser   Jul 2003 Behind BB 22·17·29 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.   2006-04-22, 03:45 #8 jasong   "Jason Goatcher" Mar 2005 3·7·167 Posts 80 minutes it is.   2006-04-23, 16:20 #9 masser   Jul 2003 Behind BB 22·17·29 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 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. Last fiddled with by masser on 2006-09-25 at 16:58   2006-05-25, 23:54 #10 jasong   "Jason Goatcher" Mar 2005 3×7×167 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 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.   2009-01-25, 15:56   #11
masser

Jul 2003
Behind BB

22·17·29 Posts Quote:
 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.  Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post pepi37 Software 1 2017-05-15 17:17 paul0 Factoring 5 2015-11-18 13:58 cipher Twin Prime Search 25 2009-08-09 19:32 gd_barnes Conjectures 'R Us 13 2009-02-17 08:28 jasong Math 18 2006-03-31 03:14

All times are UTC. The time now is 08:48.

Tue Feb 7 08:48:49 UTC 2023 up 173 days, 6:17, 1 user, load averages: 0.92, 0.99, 1.01