mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Data > Marin's Mersenne-aries

Reply
 
Thread Tools
Old 2016-03-04, 04:09   #1
ixfd64
Bemusing Prompter
 
ixfd64's Avatar
 
"Danny"
Dec 2002
California

44078 Posts
Default 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 CPU credit calculator, 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)2 ≈ 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?

Last fiddled with by ixfd64 on 2016-03-04 at 04:16
ixfd64 is offline   Reply With Quote
Old 2016-03-04, 04:25   #2
airsquirrels
 
airsquirrels's Avatar
 
"David"
Jul 2015
Ohio

11·47 Posts
Default

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.

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

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

Last fiddled with by airsquirrels on 2016-03-04 at 04:29
airsquirrels is offline   Reply With Quote
Old 2016-03-04, 05:43   #3
axn
 
axn's Avatar
 
Jun 2003

4,723 Posts
Default

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.
axn is offline   Reply With Quote
Old 2019-08-13, 20:11   #4
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

4,643 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
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
LL Credit Calculator swl551 Software 0 2012-12-04 17:49
LL tests more credit-efficient than P-1? ixfd64 Software 3 2011-02-20 16:24
PrimeNet credit CPU efficiency calculator James Heinrich PrimeNet 22 2009-05-09 19:21
Discrepancy? DJones Data 7 2006-11-26 19:55
Large Digit Calculator Primeinator Lounge 7 2006-02-16 23:11

All times are UTC. The time now is 10:10.

Sat Oct 31 10:10:33 UTC 2020 up 51 days, 7:21, 2 users, load averages: 3.26, 2.47, 2.27

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.