20031013, 01:34  #1 
"William"
May 2003
New Haven
2^{3}×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. 
20031013, 21:34  #2 
"Phil"
Sep 2002
Tracktown, U.S.A.
10001011110_{2} 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.

20031015, 19:18  #3 
"Phil"
Sep 2002
Tracktown, U.S.A.
1118_{10} 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. 
20031015, 20:18  #4  
"William"
May 2003
New Haven
2^{3}×5×59 Posts 
Quote:
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. 

20031015, 20:38  #5 
"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 20031015 at 20:39 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Kinsey scale  BrianE  Lounge  14  20150827 01:43 
Best way to scale polynomial selection  pastcow  Msieve  6  20130508 09:01 
force prime95 to get higher exponents?  joblack  PrimeNet  6  20090425 15:16 
How does one LLtest scale on 8 and 16cores  joblack  Hardware  3  20090118 18:09 
How can i get Prime95 to not release exponents?  E_tron  Software  5  20031219 02:59 