mersenneforum.org  

Go Back   mersenneforum.org > Other Stuff > Archived Projects > ElevenSmooth

 
 
Thread Tools
Old 2003-10-13, 01:34   #1
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

45018 Posts
Default 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.
wblipp is offline  
Old 2003-10-13, 21:34   #2
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

100010111112 Posts
Default

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 is offline  
Old 2003-10-15, 19:18   #3
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

45F16 Posts
Default

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.
philmoore is offline  
Old 2003-10-15, 20:18   #4
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

23·103 Posts
Default

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.
wblipp is offline  
Old 2003-10-15, 20:38   #5
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

111910 Posts
Default

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
philmoore is offline  
Old 2003-10-15, 21:21   #6
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

236910 Posts
Default

Thanks, philmoore.

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

Thread Tools


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

All times are UTC. The time now is 07:50.


Thu Dec 2 07:50:00 UTC 2021 up 132 days, 2:18, 0 users, load averages: 0.83, 1.06, 1.14

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.