Hi Antonio, Thanks for your constructive criticism, and the example you gave with the comparison with Lucas-Lehmer primality tester.
I've been reviewing the responses off the GIMPS mailing list and it seems people are more focused on the implementation and language of primz? and not the conceptual methodology. Sooooooo... Since the primality tester was only a small part of my paper, that kind of fell out of the number theory of the prime generators, I will take your advice and write up a more mathematical explanation of how to do my primality testing method in an implemenation which can accomodate the size of GIMPS integers. But I'm a little surprised that people are missing the boat on my prime generators. The issue isn't Ruby, but the math I'm doing. Essentially, I've identified a class of functions which form sort of a vector space, which are sufficient to both identify candidate primes and then eliminate non-primes. One important aspect of these functions is that these vectors are inherently independent, which allows for then to be performed in parallel. In fact, as I stated multiple times in my paper, my methods SCREAMS out that these functions be performed in parallel. Ruby actually slows down as the residues get bigger because of its memory management deficiencies. The performance of my primz? tester is completely determined by how many of the odd numbers from 7-to-sqrt(N) you apply the test inside that loop to. I used the simplest generator to illustrate the method, but you can use any generator. To optimize the process, instead of checking all the odd numbers from 7-to-sqrt(N) you really only need to check the possible candidate primes. The bigger the generator, the fewer the candidates you will check up to the sqrt(N). To test a GIMPS prime candidate, I would take the largest generator, which is so far P13, which has a residue (vector) space of 5760. The possible prime candidates for these are: res(i)+30030, where 30030 is the modulus for P13. Each one of these numbers can be computed in parallel up to sqrt(N). However, the test for each of these candidates is still the simple test for P3, i.e. if (N-p1) mod 6 = OR (N-p2) mod 6 = 0, then the number is non-prime, and if you go through the candidates list and not violate these tests, N is prime. So it takes longest time to verify a prime -- IF DONE SEQUENTIALLY! There are so many ways to break this process down into parallel chunks. You can precompute the primes candidates list, and then extend it for larger and larger numbers as you go. Again, these are the only numbers you have to test against up to the sqrt(N). In fact, what you really want to calculate are p1 and p2 for each candidate prime, and extend that list, since that is the calculation first done with the candidates. Now you have a permanent set of p(1,2) values that you just extend for larger and larger numbers. These numbers then form a permanent vector space for all N. Again, I will write this up, and present some psuedo code, so people don't get hung up on Ruby, though it should be obvious that just about any compiled language would be faster than Ruby (or Python, etc). Finally, the only coded implementation of the Sieve of Atkin I have seen is the Python code I presented in my paper. If someone has a faster coded implementation the SoA I would appreciate seeing it, so I can benchmark it against ALL my versions of my SoZ. But the fact remains, my versions are faster than the given SoA, in both Ruby and Python. That doesn't seem to be acknowledged, or appreciated, from a mathematical, computational, or software coding point of view, as an advancement over the prior known state-of-the-art. Why? The numbers don't lie. Hotep (Peace) Jabari ----- Original Message ----- From: "Antonio Cangiano" To: [email protected] Subject: Re: [Prime] Ultimate Prime Sieve - Sieve of Zakiya (SoZ) Date: Sun, 08 Jun 2008 16:24:43 -0400 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 [IMAGE] -- See Exclusive Videos: 10th Annual Young Hollywood Awards http://www.hollywoodlife.net/younghollywoodawards2008/ _______________________________________________ Prime mailing list [email protected] http://hogranch.com/mailman/listinfo/prime
