Ultimate Prime Sieve -- Sieve Of Zakiya (SoZ)

Discussion in 'C Programming' started by jzakiya, Jun 13, 2008.

  1. jzakiya

    jzakiya Guest

    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/97bd7b71/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: 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 )

    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, Jun 13, 2008
    #1
    1. Advertising

  2. jzakiya

    jzakiya Guest

    On Jun 13, 1:27 pm, 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/97bd7b71/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:  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 )
    >
    >     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"
    jzakiya, Jun 13, 2008
    #2
    1. Advertising

  3. jzakiya

    Guest

    On Jun 13, 8:27 pm, 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.

    <snip>
    Not related to ISO C. Try another newsgroup.
    , Jun 13, 2008
    #3
  4. jzakiya

    user923005 Guest

    On Jun 13, 10:27 am, 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/97bd7b71/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:  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 )
    >
    >     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, Jun 13, 2008
    #4
  5. jzakiya

    user923005 Guest

    On Jun 13, 2:01 pm, CBFalconer <> 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/97bd7b71/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.
    user923005, Jun 13, 2008
    #5
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. jzakiya
    Replies:
    3
    Views:
    549
    jzakiya
    Jul 19, 2008
  2. jzakiya

    Sieve of Zakiya

    jzakiya, Nov 4, 2008, in forum: Python
    Replies:
    7
    Views:
    310
    Mark Dickinson
    Nov 19, 2008
  3. jzakiya
    Replies:
    6
    Views:
    188
    Michael Ulm
    Jun 11, 2008
  4. jzakiya

    Sieve of Zakiya

    jzakiya, Nov 20, 2008, in forum: Ruby
    Replies:
    11
    Views:
    236
  5. Replies:
    0
    Views:
    104
Loading...

Share This Page