# Ultimate Prime Sieve -- Sieve of Zakiya (SoZ)

**URL:** <https://www.ruby-forum.com/t/ultimate-prime-sieve-sieve-of-zakiya-soz/139854>\
**Category:** Ruby\
**Created:** [June 8, 2008, 5:00am UTC](https://www.ruby-forum.com/t/ultimate-prime-sieve-sieve-of-zakiya-soz/139854 "2008-06-08T05:00:22Z")\
**Posts on this page:** 7\
**Page:** 1

<div class="post-metadata">

**Author:** ![jzakiya](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/3ec8ea/32.png) [@jzakiya](https://www.ruby-forum.com/u/jzakiya)\
**Post date:** [June 8, 2008, 5:00am UTC](https://www.ruby-forum.com/t/ultimate-prime-sieve-sieve-of-zakiya-soz/139854/1 "2008-06-08T05:00:22Z")

</div>

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:

> **[4shared - free file sharing and storage](https://www.4shared.com/dir/7467736/97bd7b71/sharing.html)**
>
> 4shared is a perfect place to store your pictures, documents, videos and files, so you can share them with friends, family, and the world. Claim your free 15GB now!

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

---

<div class="post-metadata">

**Author:** ![jzakiya](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/3ec8ea/32.png) [@jzakiya](https://www.ruby-forum.com/u/jzakiya)\
**Post date:** [June 8, 2008, 6:32am UTC](https://www.ruby-forum.com/t/ultimate-prime-sieve-sieve-of-zakiya-soz/139854/2 "2008-06-08T06:32:50Z")

</div>

On Jun 7, 10:58 pm, jzakiya [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote:

> ```
> n1, n2 = -1, 1; lndx= (self-1) >>1; sieve = []
> i6 = 6*i; p1 = (i6-i-3)>>1; p2 = (i6+i-3)>>1; k = i6>>1
> n = self.abs
> 
> ```
> 
> end  
> 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](http://snippets.dzone.com/posts/show/5610)

---

<div class="post-metadata">

**Author:** ![jzakiya](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/3ec8ea/32.png) [@jzakiya](https://www.ruby-forum.com/u/jzakiya)\
**Post date:** [June 9, 2008, 10:25am UTC](https://www.ruby-forum.com/t/ultimate-prime-sieve-sieve-of-zakiya-soz/139854/3 "2008-06-09T10:25:07Z")

</div>

jzakiya wrote:

> 

–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

---

<div class="post-metadata">

**Author:** ![jzakiya](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/3ec8ea/32.png) [@jzakiya](https://www.ruby-forum.com/u/jzakiya)\
**Post date:** [June 10, 2008, 12:46am UTC](https://www.ruby-forum.com/t/ultimate-prime-sieve-sieve-of-zakiya-soz/139854/4 "2008-06-10T00:46:03Z")

</div>

On Jun 9, 4:22 am, Michael U. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote:

> > [4shared - My 4shared - shared folder - free file sharing and storage](http://www.4shared.com/dir/7467736/97bd7b71/sharing.html)
> 
> 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

---

<div class="post-metadata">

**Author:** ![jzakiya](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/3ec8ea/32.png) [@jzakiya](https://www.ruby-forum.com/u/jzakiya)\
**Post date:** [June 10, 2008, 9:46am UTC](https://www.ruby-forum.com/t/ultimate-prime-sieve-sieve-of-zakiya-soz/139854/5 "2008-06-10T09:46:17Z")

</div>

jzakiya wrote:

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

---

<div class="post-metadata">

**Author:** ![jzakiya](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/3ec8ea/32.png) [@jzakiya](https://www.ruby-forum.com/u/jzakiya)\
**Post date:** [June 11, 2008, 9:15am UTC](https://www.ruby-forum.com/t/ultimate-prime-sieve-sieve-of-zakiya-soz/139854/6 "2008-06-11T09:15:55Z")

</div>

jzakiya wrote:  
–big snip–

> GB of memory should be able to test my routines up to those sizes of  
> be done in parallel, which I emphasized repeatedly in my paper.  
> 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

---

<div class="post-metadata">

**Author:** ![jzakiya](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/3ec8ea/32.png) [@jzakiya](https://www.ruby-forum.com/u/jzakiya)\
**Post date:** [June 10, 2008, 10:50pm UTC](https://www.ruby-forum.com/t/ultimate-prime-sieve-sieve-of-zakiya-soz/139854/7 "2008-06-10T22:50:51Z")

</div>

On Jun 10, 2:31 am, Michael U. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote:

> > > > [4shared - My 4shared - shared folder - free file sharing and storage](http://www.4shared.com/dir/7467736/97bd7b71/sharing.html)  
> > > > Keep your passion for Ruby and mathematics.  
> > > > it will be faster than Atkin. But understand, that eventually Atkins method  
> > > > I would have to dig up some of the algorithms I’ve lying around on my harddisk
> 
> 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