Ultimate Prime Sieve -- Sieve of Zakiya (SoZ)

[jzakiya]

This is to announce the release of my paper "Ultimate Prime Sieve --
Sieve of Zakiiya (SoZ)" in which I show and explain the development of
a class of Number Theory Sieves to generate prime numbers. I also use
the number theory to then create the fastest, and deterministic,
primality tester. I used Ruby 1.9.0-1 as my development environment
on a P4 2.8 Ghz laptop.

You can get the pdf of my paper from here:

http://www.4shared.com/dir/7467736/97bd7b71/sharing.html


Below is a sample of one of the prime generators, and the primality
tester.

class Integer
def primesP3a
# all prime candidates > 3 are of form 6*k+1 and 6*k+5
# initialize sieve array with only these candidate values
# where sieve contains the odd integers representatives
# convert integers to array indices/vals by i = (n-3)>>1 =
(n>>1)-1
n1, n2 = -1, 1; lndx= (self-1) >>1; sieve = []
while n2 < lndx
n1 +=3; n2 += 3; sieve[n1] = n1; sieve[n2] = n2
end
#now initialize sieve array with (odd) primes < 6, resize array
sieve[0] =0; sieve[1]=1; sieve=sieve[0..lndx-1]

5.step(Math.sqrt(self).to_i, 2) do |i|
next unless sieve[(i>>1) - 1]
# p5= 5*i, k = 6*i, p7 = 7*i
# p1 = (5*i-3)>>1; p2 = (7*i-3)>>1; k = (6*i)>>1
i6 = 6*i; p1 = (i6-i-3)>>1; p2 = (i6+i-3)>>1; k = i6>>1
while p1 < lndx
sieve[p1] = nil; sieve[p2] = nil; p1 += k; p2 += k
end
end
return [2] if self < 3
[2]+([nil]+sieve).compact!.map {|i| (i<<1) +3 }
end

def primz?
# number theory based deterministic primality tester
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)

7.step(Math.sqrt(n).to_i,2) do |i|
# p5= 5*i, k = 6*i, p7 = 7*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
end

Now to generate an array of the primes up to some N just do:
1000001.primesP3a

To check the primality of any integer just do: 13328237.primz?

The paper presents benchmarks with Ruby 1.9.0-1 (YARV). I would love
to see the various prime generators benchmarked with other
interpretors. I would also like to see at least the primality tester
make it into the standard library, since its so short, elegant, and
good.

Have fun with the code.

Jabari Zakiya

 

[jzakiya]

This is to announce the release of my paper "Ultimate Prime Sieve --
Sieve of Zakiiya (SoZ)" in which I show and explain the development of
a class of Number Theory Sieves to generate prime numbers. I also use
the number theory to then create the fastest, and deterministic,
primality tester. I used Ruby 1.9.0-1 as my development environment
on a P4 2.8 Ghz laptop.

You can get the pdf of my paper from here:

http://www.4shared.com/dir/7467736/97bd7b71/sharing.html

Below is a sample of one of the prime generators, and the primality
tester.

class Integer
def primesP3a
# all prime candidates > 3 are of form 6*k+1 and 6*k+5
# initialize sieve array with only these candidate values
# where sieve contains the odd integers representatives
# convert integers to array indices/vals by i = (n-3)>>1 =
(n>>1)-1
n1, n2 = -1, 1; lndx= (self-1) >>1; sieve = []
while n2 < lndx
n1 +=3; n2 += 3; sieve[n1] = n1; sieve[n2] = n2
end
#now initialize sieve array with (odd) primes < 6, resize array
sieve[0] =0; sieve[1]=1; sieve=sieve[0..lndx-1]

5.step(Math.sqrt(self).to_i, 2) do |i|
next unless sieve[(i>>1) - 1]
# p5= 5*i, k = 6*i, p7 = 7*i
# p1 = (5*i-3)>>1; p2 = (7*i-3)>>1; k = (6*i)>>1
i6 = 6*i; p1 = (i6-i-3)>>1; p2 = (i6+i-3)>>1; k = i6>>1
while p1 < lndx
sieve[p1] = nil; sieve[p2] = nil; p1 += k; p2 += k
end
end
return [2] if self < 3
[2]+([nil]+sieve).compact!.map {|i| (i<<1) +3 }
end

def primz?
# number theory based deterministic primality tester
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)

7.step(Math.sqrt(n).to_i,2) do |i|
# p5= 5*i, k = 6*i, p7 = 7*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
end

Now to generate an array of the primes up to some N just do:
1000001.primesP3a

To check the primality of any integer just do: 13328237.primz?

The paper presents benchmarks with Ruby 1.9.0-1 (YARV). I would love
to see the various prime generators benchmarked with other
interpretors. I would also like to see at least the primality tester
make it into the standard library, since its so short, elegant, and
good.

Have fun with the code.

Jabari Zakiya

The Ruby code from the paper can be seen here;

http://snippets.dzone.com/posts/show/5610

 

[Michael Ulm]

This is to announce the release of my paper "Ultimate Prime Sieve --
Sieve of Zakiiya (SoZ)" in which I show and explain the development of
a class of Number Theory Sieves to generate prime numbers. I also use
the number theory to then create the fastest, and deterministic,
primality tester. I used Ruby 1.9.0-1 as my development environment
on a P4 2.8 Ghz laptop.

You can get the pdf of my paper from here:

http://www.4shared.com/dir/7467736/97bd7b71/sharing.html

--snip--

Hi, just skimmed over your paper. Nice work, but you seem
somewhat overenthusiastic about it. Your sieve looks very
much like Wheel factorization to me.

Also, your primality test is a lot slower than known methods
(like the AKS primality test which has been mentioned on this
list a few weeks ago).

Keep your passion for Ruby and mathematics.

Regards,

Michael

 

[jzakiya]

--snip--

Hi, just skimmed over your paper. Nice work, but you seem
somewhat overenthusiastic about it. Your sieve looks very
much like Wheel factorization to me.

Also, your primality test is a lot slower than known methods
(like the AKS primality test which has been mentioned on this
list a few weeks ago).

Keep your passion for Ruby and mathematics.

Regards,

Michael

Have you run all my coded examples?

Can you provide empirical results for other methods and their code?

Jabari

 

[Michael Ulm]

Have you run all my coded examples?

Can you provide empirical results for other methods and their code?

Your implementation of the sieve is quite fast and for any ordinary range
it will be faster than Atkin. But understand, that eventually Atkins method
must be quicker due to its better asymptotic bound.

As an made up example, if your method takes n units of time to complete the
task and Atkins takes 3 * n / (log log n) units of time for the same task,
then yours would be faster until n ~ 5300000000. So, for all practical n
yours would be faster but Atkin would still be considered the 'faster'
algorithm asymptotically.

As for primality testing, understand, that people test primality of numbers
with 100+ digits. You don't get very far with such numbers using trial division.
I would have to dig up some of the algorithms I've lying around on my harddisk
for benchmarks, but until I find the time just look at what the simple
factor command does to the example you give in your paper (primality of the
product of the first 11 primes + 1)

time factor 200560490131
200560490131: 200560490131

real 0m0.006s
user 0m0.005s
sys 0m0.001s

i.e. the number is prime and it took this fairly old (~1 GHz Pentium) machine
5 milliseconds to figure out.

HTH,

Michael

 

[jzakiya]

Your implementation of the sieve is quite fast and for any ordinary range
it will be faster than Atkin. But understand, that eventually Atkins method
must be quicker due to its better asymptotic bound.

As an made up example, if your method takes n units of time to complete the
task and Atkins takes 3 * n / (log log n) units of time for the same task,
then yours would be faster until n ~ 5300000000. So, for all practical n
yours would be faster but Atkin would still be considered the 'faster'
algorithm asymptotically.

As for primality testing, understand, that people test primality of numbers
with 100+ digits. You don't get very far with such numbers using trial division.
I would have to dig up some of the algorithms I've lying around on my harddisk
for benchmarks, but until I find the time just look at what the simple
factor command does to the example you give in your paper (primality of the
product of the first 11 primes + 1)

time factor 200560490131
200560490131: 200560490131

real 0m0.006s
user 0m0.005s
sys 0m0.001s

i.e. the number is prime and it took this fairly old (~1 GHz Pentium) machine
5 milliseconds to figure out.

HTH,

Michael

Hi Michael,

Help me out here.

By what basis do say "that eventually Atkins method must be quicker"?

The test I've run in Ruby and Python with my different versions show
they pull away from the SoA as N gets bigger. Why to you think the
math I do is asymptotically bounded? Did you read that I took the SoA
generator functions and implemented them with my methodology and beat
the SoA by over a factor of 2. I'm limited to 1GB on my laptop, so I
haven't been able to do Ns into the billions (yet) but people with 2-4
GB of memory should be able to test my routines up to those sizes of
N.

I'm really hoping that some people will ACTUALLY rigorously test my
versions against the SoA, which is why I released my findings. But all
my tests show my methodology, in its various specific implementations,
is 'better' in many aspects, and not just speed.

My method is shorter and easier to code (in any language), easier to
understand, extensible to accommodate better generator functions, and
inherently able to be done in parallel. In fact, my method SCREAMS to
be done in parallel, which I emphasized repeatedly in my paper.

If you have the capacity, please SHOW ME some benchmarks that prove
the SoA is better than the various SoA versions beyond some point.

Yeh, the primality tester I showed in my paper just fell out of the
number theory I used to do the prime generators. I realized then it
wasn't the best numerical method to test REALLY BIG numbers, but it
was just so cool to demonstrate the conceptual brevity of reversing
the process to generate primes to test numbers for being prime. I
realized early that it was only practical for "normal" numbers, but
for most people that's sufficient, and it's practical to do because
it's short and easy to code and understand. I'm still thinking about
ways to make numerically useful tests for large numbers using this
number theory, so stay tuned.

Jabari

 

[Michael Ulm]

jzakiya wrote:
--big snip--

Help me out here.

By what basis do say "that eventually Atkins method must be quicker"?

The test I've run in Ruby and Python with my different versions show
they pull away from the SoA as N gets bigger. Why to you think the
math I do is asymptotically bounded? Did you read that I took the SoA
generator functions and implemented them with my methodology and beat
the SoA by over a factor of 2. I'm limited to 1GB on my laptop, so I
haven't been able to do Ns into the billions (yet) but people with 2-4
GB of memory should be able to test my routines up to those sizes of
N.

I'm really hoping that some people will ACTUALLY rigorously test my
versions against the SoA, which is why I released my findings. But all
my tests show my methodology, in its various specific implementations,
is 'better' in many aspects, and not just speed.

My method is shorter and easier to code (in any language), easier to
understand, extensible to accommodate better generator functions, and
inherently able to be done in parallel. In fact, my method SCREAMS to
be done in parallel, which I emphasized repeatedly in my paper.

If you have the capacity, please SHOW ME some benchmarks that prove
the SoA is better than the various SoA versions beyond some point.

Yeh, the primality tester I showed in my paper just fell out of the
number theory I used to do the prime generators. I realized then it
wasn't the best numerical method to test REALLY BIG numbers, but it
was just so cool to demonstrate the conceptual brevity of reversing
the process to generate primes to test numbers for being prime. I
realized early that it was only practical for "normal" numbers, but
for most people that's sufficient, and it's practical to do because
it's short and easy to code and understand. I'm still thinking about
ways to make numerically useful tests for large numbers using this
number theory, so stay tuned.

Let me start off by saying, that I really like your implementation of
your sieve and I consider it quite useful for practical purposes. I'm
not quite sure if it really differs from the trick used in wheel
factorization, but even then it is a very clear implementation and very
quick.

Now for the SoA, there are several methods to measure performance. One
way is to implement each algorithm and measure the time of execution.
This is often quite practical, but has some problems. This approach
clearly depends a lot on the programming language used, the particular
implementation of an algorithm and maybe some externalities (like IO speed).
This makes it somewhat controversial to compare algorithms in this way,
although in practice that is often all one needs.

A way to overcome the shortcomings of benchmarking is to analyze the code
and examine just how much work is needed to perform it. This can be done
in a very fine-grained way up to counting how many additions and multiplications
are needed in an algorithm (look in D. E. Knuth's book "The Art of Programming"
for examples of this). For most purposes, such detailed analysis is
overkill, and a more simplified approach is taken. There, one estimates the
number of steps one has to perform in the algorithm for very large inputs.
This estimation is usually given in big O notation. E.g. an algorithm of
order O(n) would need about n steps for an input of size n. To be more precise,
there exist constants a and b such that the algorithm will take between
a*n and b*n steps.

The crown of 'fastest' algorithm usually goes to the one with the smallest
asymptotic behaviour, i.e. the one for which the function insidethe O is
smaller. This does not necessarily reflect benchmarking behaviour in the
real world for inputs of realistic sizes. Analysis gives that your sieve is
of order O(n), and the SoA is of order O(n / log log n) (However, since the
SoA is the more complex algorithm one would expect that the associated
constants are greater than the constants needed in your case). So, the SoA
is the fastest known algorithm for this measure. This has nothing to do
with benchmarking.

So, in practical applications, one would just about always use a simpler sieve
instead of the SoA. You have demonstrated in your benchmarks that for normal
input sizes your sieve is better than SoA, but the SoA has the better
asymptotic behaviour.

HTH,

Michael