Ultimate Prime Sieve -- Sieve of Zakiya (SoZ)

Discussion in 'Ruby' started by jzakiya, Jun 8, 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 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, Jun 8, 2008
    #1
    1. Advertising

  2. jzakiya

    jzakiya Guest

    On Jun 7, 10:58 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 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
     
    jzakiya, Jun 8, 2008
    #2
    1. Advertising

  3. jzakiya

    Michael Ulm Guest

    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 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
     
    Michael Ulm, Jun 9, 2008
    #3
  4. jzakiya

    jzakiya Guest

    On Jun 9, 4:22 am, Michael Ulm <> 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 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


    Have you run all my coded examples?

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

    Jabari
     
    jzakiya, Jun 9, 2008
    #4
  5. jzakiya

    Michael Ulm Guest

    jzakiya wrote:
    > On Jun 9, 4:22 am, Michael Ulm <> 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 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

    >
    > 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
     
    Michael Ulm, Jun 10, 2008
    #5
  6. jzakiya

    jzakiya Guest

    On Jun 10, 2:31 am, Michael Ulm <> wrote:
    > jzakiya wrote:
    > > On Jun 9, 4:22 am, Michael Ulm <> 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 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

    >
    > > 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


    ------------------

    >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.


    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
     
    jzakiya, Jun 10, 2008
    #6
  7. jzakiya

    Michael Ulm Guest

    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
     
    Michael Ulm, Jun 11, 2008
    #7
    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:
    553
    jzakiya
    Jul 19, 2008
  2. jzakiya
    Replies:
    4
    Views:
    485
    user923005
    Jun 13, 2008
  3. jzakiya

    Sieve of Zakiya

    jzakiya, Nov 4, 2008, in forum: Python
    Replies:
    7
    Views:
    313
    Mark Dickinson
    Nov 19, 2008
  4. jzakiya

    Sieve of Zakiya

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

Share This Page