Velocity Reviews > Ultimate Prime Sieve -- Sieve Of Zakiya (SoZ)

Ultimate Prime Sieve -- Sieve Of Zakiya (SoZ)

jzakiya
Guest
Posts: n/a

 06-13-2008
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

jzakiya
Guest
Posts: n/a

 06-13-2008
On Jun 13, 1:27*pm, jzakiya <(E-Mail Removed)> 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
>
> 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"

vippstar@gmail.com
Guest
Posts: n/a

 06-13-2008
On Jun 13, 8:27 pm, jzakiya <(E-Mail Removed)> 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.

<snip>
Not related to ISO C. Try another newsgroup.

user923005
Guest
Posts: n/a

 06-13-2008
On Jun 13, 10:27*am, jzakiya <(E-Mail Removed)> 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
>
> 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

user923005
Guest
Posts: n/a

 06-13-2008
On Jun 13, 2:01*pm, CBFalconer <(E-Mail Removed)> wrote:
> 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.

 Thread Tools

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is OffTrackbacks are On Pingbacks are On Refbacks are Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post jzakiya Ruby 11 11-25-2008 01:14 AM jzakiya Python 7 11-19-2008 09:47 AM jzakiya Python 3 07-19-2008 07:39 PM jzakiya Ruby 6 06-11-2008 07:15 AM C Erler Ruby 1 09-28-2006 03:46 AM

Advertisments