Hi Jabari,
> If you can deterministically find P exponents faster and with
> certainty then you are more ahead of the game.
The exponent of the largest Mersenne prime is 32,582,657. Finding prime
exponents that are larger than that is quite trivial. The challenging
part for GIMPS is to verify which 2**p - 1 numbers (huge ones) are prime.
> Also, my primality tester can be applied to the Meresenne prime
> candidates. You just need to implement this very siimple, and
> deterministic, method to deal with the size of numbers you are dealing
> with, like you are trying to do with primes95.
You may have implemented a fast sieve. As a matter of fact, it's faster
than the prime generator offered by Ruby 1.9, but that's useless in the
context of huge numbers such as Mersenne primes. Let me demonstrate this
to you using your own Ruby code.
primz? is your method, while is_prime? is a simple Lucas–Lehmer test for
Mersenne numbers. Let's test the primality of 2**61 - 1, the 9th
Mersenne Prime discovered back in 1883.
require 'benchmark'
def primz?(n)
return true if [2, 3, 5].include? n
return false if n == 1 || n & 1 == 0
return false if n > 5 && ( ! [1, 5].include?(n % 6) || n % 5 == 0)
7.step(Math.sqrt(n).to_i,2) do |i|
p1 = 5*i; k = p1+i; p2 = k+i
return false if [(n-p1)%k , (n-p2)%k].include? 0
end
return true
end
# Lucas–Lehmer primality test for 2**p - 1
def is_prime?(p)
s = 4
m = 2**p - 1
(p-2).times do
s = (s**2 - 2) % m
end
s == 0 ? true : false
end
Benchmark.bm(10) do |bmr|
bmr.report("Lucas–Lehmer: ") { is_prime?(61) }
bmr.report("Zakiya:") { primz?(2**61 - 1) }
end
On my laptop, Lucas–Lehmer calculated the primality of 2**61-1 in
0.000126 seconds. Your primality test had to be interrupted after
running for an hour, as it had yet to yield any results.
And keep in mind that we are talking about a tiny number when compared
to the 9,808,358 digits of the 44th Mersenne prime. As pointed out by
Ken, your algorithm is not suitable to deal with any but the smallest
Mersenne primes.
As I said above, you may have implemented a relatively fast sieve, but
it isn't useful at all when it comes to trying to find new Mersenne primes.
Cheers,
Antonio
--
http://antoniocangiano.com | Zen and the Art of Programming
http://math-blog.com | Mathematics is wonderful!
http://stacktrace.it | Aperiodico di resistenza informatica
Currently writing "Ruby on Rails for Microsoft Developers" for Wrox.
_______________________________________________
Prime mailing list
[email protected]
http://hogranch.com/mailman/listinfo/prime
