mersenneforum.org  

Go Back   mersenneforum.org > Prime Search Projects > Sierpinski/Riesel Base 5

Reply
 
Thread Tools
Old 2006-04-18, 01:22   #1
jasong
 
jasong's Avatar
 
"Jason Goatcher"
Mar 2005

3·7·167 Posts
Default 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.
jasong is offline   Reply With Quote
Old 2006-04-18, 13:34   #2
masser
 
masser's Avatar
 
Jul 2003
wear a mask

22×3×131 Posts
Default

(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
masser is offline   Reply With Quote
Old 2006-04-18, 19:32   #3
axn
 
axn's Avatar
 
Jun 2003

114678 Posts
Default

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).
axn is offline   Reply With Quote
Old 2006-04-18, 19:56   #4
jasong
 
jasong's Avatar
 
"Jason Goatcher"
Mar 2005

350710 Posts
Default

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.
jasong is offline   Reply With Quote
Old 2006-04-19, 17:54   #5
masser
 
masser's Avatar
 
Jul 2003
wear a mask

22·3·131 Posts
Default

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...
masser is offline   Reply With Quote
Old 2006-04-19, 19:32   #6
jasong
 
jasong's Avatar
 
"Jason Goatcher"
Mar 2005

3·7·167 Posts
Default

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
jasong is offline   Reply With Quote
Old 2006-04-20, 22:13   #7
masser
 
masser's Avatar
 
Jul 2003
wear a mask

22×3×131 Posts
Default

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.
masser is offline   Reply With Quote
Old 2006-04-22, 03:45   #8
jasong
 
jasong's Avatar
 
"Jason Goatcher"
Mar 2005

66638 Posts
Default

80 minutes it is.
jasong is offline   Reply With Quote
Old 2006-04-23, 16:20   #9
masser
 
masser's Avatar
 
Jul 2003
wear a mask

22×3×131 Posts
Default

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
masser is offline   Reply With Quote
Old 2006-05-25, 23:54   #10
jasong
 
jasong's Avatar
 
"Jason Goatcher"
Mar 2005

3×7×167 Posts
Default

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.
jasong is offline   Reply With Quote
Old 2009-01-25, 15:56   #11
masser
 
masser's Avatar
 
Jul 2003
wear a mask

22·3·131 Posts
Default

Quote:
Originally Posted by masser View Post
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.
masser is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Sieving and LLR-in in same time pepi37 Software 1 2017-05-15 17:17
Sieving both sides vs one side at a time paul0 Factoring 5 2015-11-18 13:58
Thanks PG for Sieving, now time to pick a new n? cipher Twin Prime Search 25 2009-08-09 19:32
Optimal sieving of large n-ranges gd_barnes Conjectures 'R Us 13 2009-02-17 08:28
prime density vs. sieving vs. prp time jasong Math 18 2006-03-31 03:14

All times are UTC. The time now is 22:19.

Mon Apr 19 22:20:00 UTC 2021 up 11 days, 17 hrs, 0 users, load averages: 3.38, 3.28, 3.44

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.