By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
440,781 Members | 1,134 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 440,781 IT Pros & Developers. It's quick & easy.

Ultimate Prime Sieve -- Sieve Of Zakiya (SoZ)

P: n/a
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 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 and Ruby and Python source from here:

http://www.4shared.com/dir/7467736/9...1/sharing.html

Below is a sample of one of the simple prime generators. I did a
Python version of this in my paper (see Python source too). The Ruby
version below is the minimum array size version, while the Python has
array of size N (I made no attempt to optimize its implementation,
it's to show the method). See my paper for what/why is going on here.

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
end

def primesP3(val):
# all prime candidates 3 are of form 6*k+(1,5)
# initialize sieve array with only these candidate values
n1, n2 = 1, 5
sieve = [False]*(val+6)
while n2 < val:
n1 += 6; n2 += 6; sieve[n1] = n1; sieve[n2] = n2
# now load sieve with seed primes 3 < pi < 6, in this case just 5
sieve[5] = 5

for i in range( 5, int(ceil(sqrt(val))), 2) :
if not sieve[i]: continue
# p1= 5*i, k = 6*i, p2 = 7*i,
p1 = 5*i; k = p1+i; p2 = k+i
while p2 <= val:
sieve[p1] = False; sieve[p2] = False; p1 += k; p2 += k
if p1 <= val: sieve[p1] = False

primes = [2,3]
if val < 3 : return [2]
primes.extend( i for i in range(5, val+(val&1), 2) if sieve[i] )

return primes

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

Ruby: 10000001.primesP3a
Python: primesP3a(10000001)

The paper presents benchmarks with Ruby 1.9.0-1 (YARV). I would love
to see my various prime generators benchmarked with optimized
implementations in other languages. I'm hoping C/C++ gurus will do
good implementations. The methodology is very simple, since all I do
is additions, multiplications, and array reads/writes.

I would also like to the C implementations benchmarked against the
versions create by Daniel J Bernstein of the Sieve of Atkin (SoA). The
C code is here:

http://cr.yp.to/primesgen.html

Have fun with the code. ;-)

Jabari Zakiya
Jun 27 '08 #1
Share this Question
Share on Google+
5 Replies


P: n/a
On Jun 13, 1:27*pm, jzakiya <jzak...@gmail.comwrote:
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 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 and Ruby and Python source from here:

http://www.4shared.com/dir/7467736/9...1/sharing.html

Below is a sample of one of the simple prime generators. I did a
Python version of this in my paper (see Python source too). *The Ruby
version below is the minimum array size version, while the Python has
array of size N (I made no attempt to optimize its implementation,
it's to show the method). *See my paper for what/why is going on here.

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
end

def primesP3(val):
* * # all prime candidates 3 are of form *6*k+(1,5)
* * # initialize sieve array with only these candidate values
* * n1, n2 = 1, 5
* * sieve = [False]*(val+6)
* * while *n2 < val:
* * * * n1 += 6; * n2 += 6; *sieve[n1] = n1; * sieve[n2] = n2
* * # now load sieve with seed primes 3 < pi < 6, in this case just 5
* * sieve[5] = 5

* * for i in range( 5, int(ceil(sqrt(val))), 2) :
* * * *if not sieve[i]: *continue
* * * *# *p1= 5*i, *k = 6*i, *p2 = 7*i,
* * * *p1 = 5*i; *k = p1+i; *p2 = k+i
* * * *while p2 <= val:
* * * * * sieve[p1] = False; *sieve[p2] = False; *p1 += k; *p2 += k
* * * *if p1 <= val: *sieve[p1] = False

* * primes = [2,3]
* * if val < 3 : return [2]
* * primes.extend( i for i in range(5, val+(val&1), 2) *if sieve[i] )

* * return primes

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

Ruby: * * *10000001.primesP3a
Python: * primesP3a(10000001)

The paper presents benchmarks with Ruby 1.9.0-1 (YARV). *I would love
to see my various prime generators benchmarked with optimized
implementations in other languages. *I'm hoping C/C++ gurus will do
good implementations. *The methodology is very simple, since all I do
is additions, multiplications, and array reads/writes.

I would also like to the C implementations benchmarked against the
versions create by Daniel J Bernstein of the Sieve of Atkin (SoA). The
C code is here:

http://cr.yp.to/primesgen.html

Have fun with the code. *;-)

Jabari Zakiya
CORRECTION:

http://cr.yp.to/primegen.html NOT "primesgen"
Jun 27 '08 #2

P: n/a
On Jun 13, 8:27 pm, jzakiya <jzak...@gmail.comwrote:
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 used
Ruby 1.9.0-1 as my development environment on a P4 2.8 Ghz laptop.
<snip>
Not related to ISO C. Try another newsgroup.
Jun 27 '08 #3

P: n/a
On Jun 13, 10:27*am, jzakiya <jzak...@gmail.comwrote:
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 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 and Ruby and Python source from here:

http://www.4shared.com/dir/7467736/9...1/sharing.html

Below is a sample of one of the simple prime generators. I did a
Python version of this in my paper (see Python source too). *The Ruby
version below is the minimum array size version, while the Python has
array of size N (I made no attempt to optimize its implementation,
it's to show the method). *See my paper for what/why is going on here.

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
end

def primesP3(val):
* * # all prime candidates 3 are of form *6*k+(1,5)
* * # initialize sieve array with only these candidate values
* * n1, n2 = 1, 5
* * sieve = [False]*(val+6)
* * while *n2 < val:
* * * * n1 += 6; * n2 += 6; *sieve[n1] = n1; * sieve[n2] = n2
* * # now load sieve with seed primes 3 < pi < 6, in this case just 5
* * sieve[5] = 5

* * for i in range( 5, int(ceil(sqrt(val))), 2) :
* * * *if not sieve[i]: *continue
* * * *# *p1= 5*i, *k = 6*i, *p2 = 7*i,
* * * *p1 = 5*i; *k = p1+i; *p2 = k+i
* * * *while p2 <= val:
* * * * * sieve[p1] = False; *sieve[p2] = False; *p1 += k; *p2 += k
* * * *if p1 <= val: *sieve[p1] = False

* * primes = [2,3]
* * if val < 3 : return [2]
* * primes.extend( i for i in range(5, val+(val&1), 2) *if sieve[i] )

* * return primes

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

Ruby: * * *10000001.primesP3a
Python: * primesP3a(10000001)

The paper presents benchmarks with Ruby 1.9.0-1 (YARV). *I would love
to see my various prime generators benchmarked with optimized
implementations in other languages. *I'm hoping C/C++ gurus will do
good implementations. *The methodology is very simple, since all I do
is additions, multiplications, and array reads/writes.

I would also like to the C implementations benchmarked against the
versions create by Daniel J Bernstein of the Sieve of Atkin (SoA). The
C code is here:

http://cr.yp.to/primesgen.html
I might give it a go. Bernstein's primegen is not your best
competition. This is:
http://www.primzahlen.de/files/referent/kw/sieb.htm

Here is output using a single 3 GHz CPU:

Microsoft Windows [Version 6.0.6001]
Copyright (c) 2006 Microsoft Corporation. All rights reserved.

C:\math\sieve\ecprime\x64\Release 64>ecprime 100000000000

100%
primes: 4118054813
time: 60.153 sec
C:\math\sieve\ecprime\x64\Release 64>

So your mark is to beat sieving through 100 billion in a minute.

I might give your algorithm a crack (no promises though). I set
follow-ups to news:comp.programming
Jun 27 '08 #4

P: n/a
jzakiya wrote:
>
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 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 and Ruby and Python source from here:

http://www.4shared.com/dir/7467736/9...1/sharing.html
.... snip ...

Ruby and Python are not C. This is comp.lang.c, and other
languages are off-topic.

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home.att.net>
Try the download section.
** Posted from http://www.teranews.com **
Jun 27 '08 #5

P: n/a
On Jun 13, 2:01*pm, CBFalconer <cbfalco...@yahoo.comwrote:
jzakiya wrote:
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 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 and Ruby and Python source from here:
http://www.4shared.com/dir/7467736/9...1/sharing.html

... snip ...

Ruby and Python are not C. *This is comp.lang.c, and other
languages are off-topic.
That's true, and his request (to build a version in C to see how it
compares to other sieves) is also off topic.
However, Ruby and Python were not the gist of his post {more like an
aside}, so he may deserve censure, but certainly not for that.

In my previous post I made a forward to news:comp.programming which is
more appropriate. There is a contests newsgroup also, but it does not
seem very active and this is not really a contest either.
Jun 27 '08 #6

This discussion thread is closed

Replies have been disabled for this discussion.