Talk:Lucas-Lehmer test: Difference between revisions
→Speeding things up
| (8 intermediate revisions by 5 users not shown) | |||
Line 1:
==
Welcome to 1979!
:Yeah. I know. :-) --[[User:Short Circuit|Short Circuit]] 07:55, 21 February 2008 (MST)
The table below lists all known Mersenne primes:
{| class="wikitable"
Line 321 ⟶ 322:
| Great Internet Mersenne Prime Search|GIMPS / Curtis Cooper (mathematician)|Curtis Cooper & Steven Boone [http://www.mersenne.org/32582657.htm]
|}
:The 45th and 46th Mersenne primes have been discovered, is the intention to keep this table up to date? --[[User:Lupus|Lupus]] 17:24, 2 December 2008 (UTC)
:: The above list seems to be copied ''in toto'' from the updated Wikipedia site:
<big> https://en.wikipedia.org/wiki/Mersenne_prime#List_of_known_Mersenne_primes </big>
:: The above Wikipedia site now has a list of '''51''' Mersenne primes. -- [[User:Gerard Schildberger|Gerard Schildberger]] ([[User talk:Gerard Schildberger|talk]]) 19:57, 7 May 2019 (UTC)
== Java precision ==
The Java version is still limited by types. Integer.parseInt(args[0]) limits p to 2147483647. Also the fact that isMersennePrime takes an int limits it there too. For full arbitrary precision every int needs to be a BigInteger or BigDecimal and a square root method will need to be created for them. The limitation is OK I think (I don't think we'll be getting up to 2<sup>2147483647</sup> - 1 anytime soon), but the claim "any arbitrary prime" is false because of the use of ints. --[[User:Mwn3d|Mwn3d]] 07:45, 21 February 2008 (MST)
== Speeding things up ==▼
▲== Speeding things up ==
The main loop in Lucas-Lehmer is doing (n*n) mod M where M=2^p-1, and p > 1. '''But we can do it without division'''.
Line 393 ⟶ 398:
</lang>
[[User:Arbautjc|Arbautjc]] ([[User talk:Arbautjc|talk]]) 22:04, 15 November 2013 (UTC)
May 2015 - fixed small bugs in both Python implementations. In the first, execution failed (Python 3) without a cast to int in the test. In the second, there was a typo - an 'r' should have been 's'.
: Timing for some solutions for 2..11213:
{| class="wikitable"
|-
! Time (s)
! Solution
|-
| 871.2
| Python without optimizations
|-
| 314.7
| Python with optimizations
|-
| 124.7
| Perl Math::GMP without optimizations
|-
| 106.9
| Pari/GP 2.8.0
|-
| 61.8
| Perl Math::GMP with optimization
|-
| 33.0
| Python using gmpy2 (skipping non-primes)
|-
| 14.2
| C/GMP with even more optimizations
|-
| 13.3
| Perl Math::Prime::Util::GMP (source of C/GMP code)
|}
[[User:Danaj|Danaj]] ([[User talk:Danaj|talk]]) 19:49, 9 May 2015 (UTC)
Rust solution for 2..11213 -> 8.6 s
Pari/GP solution for 2..11213 -> 2.835 s --[[User:Nebulus|Nebulus]] ([[User talk:Nebulus|talk]]) 05:21, 22 February 2023 (UTC)
| |||