mersenneforum.org How does Prime95 Scale with Exponents?
 Register FAQ Search Today's Posts Mark Forums Read

 2003-10-13, 01:34 #1 wblipp     "William" May 2003 New Haven 23×5×59 Posts How does Prime95 Scale with Exponents? For the next stage of the Special Project, there is interest in working smaller exponents. I think the most effective way will be to work a combination of curves on several different exponents. To evaluate these alternatives, I need to know how much easier the smaller exponents are with Prime95. For example, we might work 3326400/3 and 3326400/7. Will these be three times faster and seven times faster than working on 3326400? I can run some experiments, but I thought somebody might already know.
 2003-10-13, 21:34 #2 philmoore     "Phil" Sep 2002 Tracktown, U.S.A. 100010111102 Posts This is a good approximation for fairly large exponents, say 1M or larger. In actual fact, I have found that doubling the size of an exponent in the range from 10K to 1M increases the run time by closer to a factor of 3 than a factor of 2. Actual running time depends of course on machine and memory allocation, but there is definitely a range where the running time seems to grow faster than the O(n*ln n) estimate for DWT multiplication would lead one to expect. I'll take a look at my Athlon timing data and see if I can fit a reasonable straight line to it and get back with the results.
 2003-10-15, 19:18 #3 philmoore     "Phil" Sep 2002 Tracktown, U.S.A. 111810 Posts I looked at my timings on curves run on Fermat numbers F12 through F24 (P4096 through P16777216) on an Athlon XP computer, and I came up with a rough power law fit for the time for a curve to fixed bounds: T = constant x (log exponent)^1.302 (The base of the logarithm changes the constant, so it works for any base.) What this means is that on average, doubling the size of the exponent increases the time T by a factor of 2^1.302, about a factor of 2.47. However, a straight line is just the overall average fit, it looks like this 2.47 factor should actually be a little smaller for the low exponents, maybe around 2.23, increasing to around 2.7 in the range from F16 to F20, i.e., exponents in the range 65536 to 1048575, then decreasing again above that to around 2.1. Hope this gives you a good overall picture. Perhaps some timings on Mersenne numbers on a Pentium 4 might change a few of the details, but I am guessing that the overall shape of the curve will be similar.
2003-10-15, 20:18   #4
wblipp

"William"
May 2003
New Haven

23×5×59 Posts

Quote:
 Originally posted by philmoore T = constant x (log exponent)^1.302 What this means is that on average, doubling the size of the exponent increases the time T by a factor of 2^1.302, about a factor of 2.47.
I'm not clear about this. It looks to me like the time for exponents of "k" and "2k" will be
c * ln(k)^1.302
c * ln(2k)^1.302 = c * [ln(2) + ln(k)] ^ 1.302

The ratio of these numbers is an awkward expression, not your elegant 2^1.302. I must be misunderstanding something.

 2003-10-15, 20:38 #5 philmoore     "Phil" Sep 2002 Tracktown, U.S.A. 2·13·43 Posts Sorry, my mistake - the equation should read: T = constant x (exponent)^1.302 (I was working with Fermat numbers where the index of a Fermat number is the log(log(Fermat #)), where log means log base 2, and I confused the log of the number itself with the log of the exponent.) Leave it to a math teacher to make things confusing! Last fiddled with by philmoore on 2003-10-15 at 20:39
 2003-10-15, 21:21 #6 wblipp     "William" May 2003 New Haven 23×5×59 Posts Thanks, philmoore. I've used your formula to calculate equivalent curves in the Planner.

 Similar Threads Thread Thread Starter Forum Replies Last Post Brian-E Lounge 14 2015-08-27 01:43 pastcow Msieve 6 2013-05-08 09:01 joblack PrimeNet 6 2009-04-25 15:16 joblack Hardware 3 2009-01-18 18:09 E_tron Software 5 2003-12-19 02:59

All times are UTC. The time now is 14:45.

Fri Jan 15 14:45:46 UTC 2021 up 43 days, 10:57, 0 users, load averages: 1.81, 1.72, 1.71