View Single Post
Old 2019-08-13, 20:11   #4
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

29·167 Posts
Default

Quote:
Originally Posted by ixfd64 View Post
It is my understanding that double an exponent results in an LL test taking approximately four times longer.
...
So does the time complexity for LL tests stop exhibiting quadratic growth after a certain point? Or is there an error in the calculator?
The number theory folks tell us it's O(p2 log p log log p) per primality test using the best available technology for this size multiplication or squarings mod Mp, the irrational base discrete weighted transform. Over the mersenne.org range, that works out to around p2.117. Double the exponent, about 4.34 times the effort.
Empirical run time scaling for LL, PRP, or P-1 are around p2.1. Any fixed overhead appears to lower the power on the scaling and have greater effect in lowering the scaling power at small p.
prime95 PRP https://www.mersenneforum.org/showpo...78&postcount=2
prime95 P-1 https://www.mersenneforum.org/showpo...92&postcount=3
CUDALucas LL https://www.mersenneforum.org/showpo...23&postcount=2
CUDAPm1 P-1 https://www.mersenneforum.org/showpo...27&postcount=2

Last fiddled with by kriesel on 2019-08-13 at 20:12
kriesel is offline   Reply With Quote