How does Prime95 Scale with Exponents?

wblipp · 2003-10-13, 01:34

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.

philmoore · 2003-10-13, 21:34

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.

philmoore · 2003-10-15, 19:18

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.

wblipp · 2003-10-15, 20:18

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.

philmoore · 2003-10-15, 20:38

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!

wblipp · 2003-10-15, 21:21

Thanks, philmoore.

I've used your formula to calculate equivalent curves in the Planner.

2003-10-13, 01:34	#1
wblipp "William" May 2003 New Haven 2³×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-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

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Kinsey scale	Brian-E	Lounge	14	2015-08-27 01:43
Best way to scale polynomial selection	pastcow	Msieve	6	2013-05-08 09:01
force prime95 to get higher exponents?	joblack	PrimeNet	6	2009-04-25 15:16
How does one LL-test scale on 8- and 16-cores	joblack	Hardware	3	2009-01-18 18:09
How can i get Prime95 to not release exponents?	E_tron	Software	5	2003-12-19 02:59

2003-10-13, 21:34	#2
philmoore "Phil" Sep 2002 Tracktown, U.S.A. 10001011110₂ 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. 1118₁₀ 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, 21:21	#6
wblipp "William" May 2003 New Haven 2³×5×59 Posts	Thanks, philmoore. I've used your formula to calculate equivalent curves in the Planner.