mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Marin's Mersenne-aries (https://www.mersenneforum.org/forumdisplay.php?f=30)
-   -   discrepancy in credit calculator for LL tests? (https://www.mersenneforum.org/showthread.php?t=21062)

 ixfd64 2016-03-04 04:09

discrepancy in credit calculator for LL tests?

It is my understanding that double an exponent results in an LL test taking approximately four times longer.

From the [url=http://mersenne.ca/credit.php]CPU credit calculator[/url], the 49th known Mersenne prime, M74,207,281, takes around 205 GHz-days. The first Mersenne number of prime index with 100 million digits, M332,192,831, needs around 4,941 GHz-days. This also seems reasonable. M601,248,421, the largest Mersenne number with an LL test to date, requires about 16,584 GHz-days, which closely matches the credit that Never Odd or Even received.

However, the numbers become weird after that: the calculator says the first Mersenne number with more than a billion digits, M3,321,928,097, requires just 91,630 GHz-days. The actual value should also be much higher; (3,321,928,097 / 601,248,421)[SUP]2[/SUP] ≈ 30.5, and multiplying that by 16,584 gives over 500,000 GHz-days.

So does the time complexity for LL tests stop exhibiting quadratic growth after a certain point? Or is there an error in the calculator?

 airsquirrels 2016-03-04 04:25

The calculation is based on a timing chart for a hard coded list of FFT sizes matched to exponent ranges. For numbers outside of the maximum measured FFT size the credit value is just an extrapolated point from the largest FFT size.

[url]http://www.mersenne.ca/credit.php?showsource=1[/url]

From a quick glance,the largest FFT size is 33.5M or so and credit is computed linearly for larger exponents than 596M

 axn 2016-03-04 05:43

James should modify the calculator to give an error message for out-of-range exponents rather than give out some made up crap. Or try to do a realistic projection.

 kriesel 2019-08-13 20:11

[QUOTE=ixfd64;428062]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?[/QUOTE]
The number theory folks tell us it's O(p[SUP]2[/SUP] 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[SUP]2.117[/SUP]. Double the exponent, about 4.34 times the effort.
Empirical run time scaling for LL, PRP, or P-1 are around p[SUP]2.1[/SUP]. 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 [URL]https://www.mersenneforum.org/showpost.php?p=502778&postcount=2[/URL]
prime95 P-1 [URL]https://www.mersenneforum.org/showpost.php?p=503892&postcount=3[/URL]
CUDALucas LL [URL]https://www.mersenneforum.org/showpost.php?p=488523&postcount=2[/URL]
CUDAPm1 P-1 [URL]https://www.mersenneforum.org/showpost.php?p=488527&postcount=2[/URL]

 All times are UTC. The time now is 16:32.