Primes.jl icon indicating copy to clipboard operation
Primes.jl copied to clipboard

Faster `imsersenne`

Open oscardssmith opened this issue 3 years ago • 2 comments

Use trial division and pohlard's P-1 algorithm to speed up ismersenne when false. Based roughly on https://www.mersenne.org/various/math.php. The basic idea is that since almost no mersenne numbers are prime, it's worth doing some quick tests before going to LL. For example, on ismersenne(big(2)^132049-1) this adds about 2.5 seconds of extra checks (compared to 80 seconds original runtime). However, these checks make the algorithm run in only the 2.5 seconds for the vast majority of outputs.

oscardssmith avatar Feb 28 '21 09:02 oscardssmith

I've also realized that using mod_mersenne in ll_primecheck gives a 3.5x speedup for the function in the true case.

oscardssmith avatar Feb 28 '21 19:02 oscardssmith

Any ideas why the 32 bit tests are timing out?

oscardssmith avatar Mar 04 '21 18:03 oscardssmith