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
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
Hey Antonio,
I couldn't sleep without coding up the simplest example of my
improved primz? tester based on the methodology I described in my
previous post. This only uses the simplest 2 residue/vectors of P3.
This version is about 5 times faster for 32582657.primz? done in a
loop 1000 times, compared to my original primz?
But you see, I am only using the candidate primes up to sqrt(N),
and I check both candidates in pararllel, instead of just one odd number
at a time, in my original code.
Please check/benchmark this for yourself.
It's about 4:40 am now, so when I get up, I'll write a general
method so I can do the 5760 residues of P13, just to prove the
efficacy of THE METHOD!
def primz?
n = self.abs
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)
srt= Math.sqrt(n).to_i
n1, n2 = 1, 5
while n2 <= srt
n1 += 6; n2 += 6
# p1= 5*i, k = 6*i, p2 = 7*i
p1 = 5*n1; k1 = p1+n1; p2 = k1+n1
q1 = 5*n2; k2 = q1+n2; q2 = k2+n2
return false if [(n-p1)%k1, (n-p2)%k1, (n-q1)%k2, (n-q2)%k2].include? 0
end
if n1 <= srt then return false if [(n-p1)%k1 , (n-p2)%k1].include? 0 end
return true
end
Jabari
--
See Exclusive Videos: 10th Annual Young Hollywood Awards
http://www.hollywoodlife.net/younghollywoodawards2008/
_______________________________________________
Prime mailing list
[email protected]
http://hogranch.com/mailman/listinfo/prime
