Quote:
Originally Posted by ixfd64
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(p
2 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 p
2.117. Double the exponent, about 4.34 times the effort.
Empirical run time scaling for LL, PRP, or P-1 are around p
2.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