New Prime Sieve: An Alternative to the Sieve of Eratosthenes

[epsi00]

This sieve is similar to the Sieve of Eratosthenes but is very different in its implementation. Instead of considering all the numbers below N to find the primes, this sieve considers only N/3 since we know that 2/3 of the numbers up to N are multiples of 2 and 3.
No numerical experiment has been done to check the efficiency of this sieve because I cannot write code.

 

[epsi00]

How come no one has commented on this? Does it mean no one is interested in new ways to calculate the prime counting function Pi(N)?

 

[JeremyEbert]

This is very interesting to me. Unfortunately I’m a NuB when it comes to matrices. I do have a general understanding of your approach though. It reminds me of a mod 12 approach involving congruence of squares that I was working on. Do you have any suggestions for learning matrices?

 

[epsi00]

Well you can learn about matrices by taking a course in linear algebra I guess at the undergrad level. But for the purpose of the sieve, you can think of a matrix as a table of multiplication. More importantly, if you were to implement the sieve above, you really do not need to set up the matrices because setting matrices will make the sieve very inefficient and increase the storage requirements dramatically. To calculate the "matrix" elements, you need far fewer multiplications than in theory. Simply because once you have the first element of a matrix, you can deduce the second from it and the third from the second etc...That is for the diagonal element ( 1st, 2nd, 3rd...) but I also gave a method to fill a column, say the 2nd column, simply by addition of a constant quantity once you have deduced the 2nd diagonal element. This can also be applied, with a slight change, to the non-symmetric matrix.
And this is one of the point I made in the first post. That though we consider matrices to make the discussion simpler, we in fact do not need to really work with them.

This sieve can calculate Pi(N) with very few multiplications and a lot more additions ( about one addition per composite number).

if you want I can build one example and show how it is done.

 

[JeremyEbert]

To calculate the "matrix" elements, you need far fewer multiplications than in theory. Simply because once you have the first element of a matrix, you can deduce the second from it and the third from the second etc...That is for the diagonal element ( 1st, 2nd, 3rd...) but I also gave a method to fill a column, say the 2nd column, simply by addition of a constant quantity once you have deduced the 2nd diagonal element.

Picturing these symmetric matrices makes my think of some code I've played around with for non-standard bitmapping/masking techniques that I used to write an SNMP discovery tool using multi-dimensional arrays, I wonder if its applicable.

 

[JeremyEbert]

I would love an example!

 

[Hurkyl]

Splitting a sieve into regions based on their residue modulo 6 (and throwing out the classes over 0, 2, 3, and 4) is a good optimization. You can go further and consider residues modulo 30 or 210 or more. I believe this is called a "wheel sieve". I believe this idea is used in the fastest algorithms for listing all primes less than some bound.


If you take a step back and rethink your algorithm, I think you will greatly simplify your approach. Just think about the actual computational problem (e.g. find all points that are 1 modulo 6 and also divisible by some prime p) independently of the way you thought to consider the problem.


As for computing \pi(N), there are much better algorithms than sieves. At the very least, a sieve -- no matter how well optimized -- has to do one unit of work for every prime. Mathworld's page on the function indicates there are known algorithms that take much, much less time. (At least, once N is sufficiently large)


(30 = 2*3*5, 210 = 2*3*5*7)

 

[epsi00]

Splitting a sieve into regions based on their residue modulo 6 (and throwing out the classes over 0, 2, 3, and 4) is a good optimization. You can go further and consider residues modulo 30 or 210 or more. I believe this is called a "wheel sieve". I believe this idea is used in the fastest algorithms for listing all primes less than some bound.

I do everything by hand unfortunately so I won't be able to see if mod 30 or 210 or higher are more efficient.

If you take a step back and rethink your algorithm, I think you will greatly simplify your approach. Just think about the actual computational problem (e.g. find all points that are 1 modulo 6 and also divisible by some prime p) independently of the way you thought to consider the problem.

I thought about it but I could not figure out what you mean by " greatly simplifying " my approach. Can you please post the way this sieve can be simplified.

As for computing \pi(N), there are much better algorithms than sieves. At the very least, a sieve -- no matter how well optimized -- has to do one unit of work for every prime. Mathworld's page on the function indicates there are known algorithms that take much, much less time. (At least, once N is sufficiently large)

(30 = 2*3*5, 210 = 2*3*5*7)

This may be the case of course but the way I do things is new and I wanted to post it. I will be providing an example in another post just for completeness.

 

[epsi00]

Let's take N=900 and see how to calculate the matrix elements for the matrix M=6ij + (i+j). Since M is symmetric, we only need to calculate about half the total number of elements ( the side below the diagonal but including the diagonal elements ). The first element is for (i=1, j=1) so M=6*1*1 + (1+1)=8. We know this element corresponds to 7*7=(6*1+1)(6*1+1)=49 since (49-1)/6=8. The maximum element is given by ME=900/6=150. We are now able to calculate the first column of the matrix simply by adding 7 to the previous element.

8
8+7=15
15+7=22
22+7=29
...
141+7=148

Note that 7 is the first element of the arithmetic progression (6k+1).
We see that element 148 is the last one needed since adding 7 to it will be greater than ME=150, the max element.

To calculate the elements of the second column, we note that:
13*13=(7+6)*(7+6)=7*7 + 2*6*7 +6*6 and the in terms of indices (13*13-1)/6=(7*7-1)/6 +2*7 +6= 8+14+6=28. Please refer to the formula in the first post.
Now we can calculate the 2nd column

28
28+13=41
41+13=54
54+13=67
...
132+13=145

145 is the value of the last element of the second column.

The third column can be calculated in the same way. The diagonal element is:
28+2*13+6=60. The third column looks like:

60
60+19=79
79+19=98
98+19=117
117+19=136

136 is the last element since adding 19 to it makes the result larger than ME=150.

To calculate the fourth column, we first need to calculate the diagonal element.
60+2*19+6=104. The fourth column looks like:

104
104+25=129

we stop since 129+25 > ME.

So we now have all the elements of the symmetric matrix M=6*ij+(i+j). These elements are simply the indices of the numbers ( composite ) in the arithmetic progression ap=(6k+1)=7,13,19,... They simply tell us that the 8th, 15th, 22nd ...elements of ap are composite numbers. Of course we still need to consider the other symmetric matrix M=6*ij -(i+j) to get all the indices needed for ap=(6k+1).
And finally, we also need to consider the non symmetric matrix M=6ij+(i-j) to find the indices of the composite numbers in the arithmetic progression ap=(6k-1). The procedure is the same ( with a slight change for the non symmetric matrix ).

 

[epsi00]

Let's take N=900 again and see how to calculate the matrix elements for the matrix M=6ij - (i+j). Since M is symmetric, we only need to calculate about half the total number of elements ( the side below the diagonal but including the diagonal elements ). The first element is for (i=1, j=1) so M=6*1*1 - (1+1)=4. We know this element corresponds to 5*5=(6*1-1)(6*1-1)=25 since (25-1)/6=4. The maximum element is given by ME=900/6=150. We are now able to calculate the first column of the matrix simply by adding 5 to the previous element.

4
4+5=9
9+5=14
14+5=19
….
144+5=149

Note that 5 is the first element of the arithmetic progression (6k-1).
We see that element 149 is the last one needed since adding 5 to it will be greater than ME=150, the max element.

To calculate the elements of the second column, we note that:
11*11=(5+6)*(5+6)=5*5 + 2*6*5 +6*6 and in terms of indices (11*11-1)/6=(5*5-1)/6 +2*5 +6= 4+10+6=20. Please refer to the formula in the first post.
Now we can calculate the elements of the 2nd column, starting with its diagonal element.

20
20+11=31
31+11=42
42+11=53
….
130+11=141141 is the value of the last element of the second column.

The third column can be calculated in the same way. The diagonal element is:
20+2*11+6=48. The third column looks like:

48
48+17=65
65+17=82
82+17=99
…
133+17=150150 is the last element since adding 17 to it makes the result larger than ME=150.

To calculate the fourth column, we first need to calculate the diagonal element.
48+2*17+6=88. The fourth column looks like:

88
88+23=111
111+23=134we stop since 134+23 > ME=150

The fifth column has only one element, the diagonal one and its value is 140.

So we now have all the elements of the symmetric matrix M=6*ij-(i+j). These elements are simply the indices of the numbers ( composite ) in the arithmetic progression ap=(6k+1)=7,13,19,... simply because the product (6i-1)*(6j-1) is an element of the ap=(6k+1) and not an element of ap=(6k-1). They simply tell us that the 4th, 9th, 14th ...elements of ap=(6k+1) are composite numbers.
The indices of the composite numbers in the arithmetic progression ap=(6k-1) will be given by the non symmetric matrix M=6*ij + (i-j) and will be given in another post.

 

[dalcde]

Removing the multiples of 2 and 3 is the first to steps of the normal sieve.

 

[epsi00]

Removing the multiples of 2 and 3 is the first to steps of the normal sieve.

right. and that's not even needed in this sieve because we do not even consider them so there is no need to remove them. We only consider N/3 instead of N then sieve since the multiples of 2 and 3 make up 2/3 of the numbers up to N.

 

[baric]

right. and that's not even needed in this sieve because we do not even consider them so there is no need to remove them. We only consider N/3 instead of N then sieve since the multiples of 2 and 3 make up 2/3 of the numbers up to N.

Your {6k-1, 6k+1} sieve reduces the quantity of numbers to check by 1/3 over the simpler (2n+1} sieve. This is simply because you've added the next prime into your algorithm.

Similarly, you can reduce the quantity of numbers to check by another 20% by incorporating 5 into your algorithm thusly: { 30k+1, 30k+3, 30k+7, 30k+11, 30k+13, 30k+17, 30k+19, 30k+23, 30k+29 }

You are basically pre-loading some filtering into the design of your algorithm and this can continue to any arbitrary level. Obviously, you will get into diminishing returns if you are doing these computations manually, so {6k-1, 6k+1} seems like a good stopping point.

But if you are doing these computationally, there's no reason to not expand your algorithm to whatever size is optimal for your computer configuration.

 

[epsi00]

Thanks for the suggestion Baric

Hopefully one of the bright kids on this forum will write the code and experiment with it to see how far it can be pushed and which representation provides the most efficient sieve.
2*3 or (6k+/- 1) ======>done
2*3*5 or ( 30k+1,3,...)====> to be done
2*3*5*7 or ( 210k+1,...) ====> to be done
...

 

[baric]

Thanks for the suggestion Baric

Hopefully one of the bright kids on this forum will write the code and experiment with it to see how far it can be pushed and which representation provides the most efficient sieve.
2*3 or (6k+/- 1) ======>done
2*3*5 or ( 30k+1,3,...)====> to be done
2*3*5*7 or ( 210k+1,...) ====> to be done
...

Well, there's definitely a trade-off. You reduce the numbers to be sieved at the cost of increasing the size of the sieve.

A sieve stopping at 2 gives you a 50% reduction and a sieve size of 1 (the minimum anyway).
At 3, you get a 67% reduction and a sieve size of 2. (1*2)
At 5, you get a 73% reduction and a sieve size of 8. (1*2*4)
At 7, you get a 77% reduction and a sieve size of 48. (1*2*4*6)
At 11,you get a 79% reduction and a sieve size of 480. (1*2*4*6*10)
At 13, you get an 81% reduction and a sieve size of 5760. (1*2*4*6*10*12)

While that may seem like a huge sieve, an additional 8% reduction (going from 79% to 81%) can be quite significant over a large range of numbers and justify the initial sieve setup.

I have no idea what computational algorithms are used to apply the sieve to large numbers, but I'm guess that they would gladly make a 5K for 8% tradeoff :)

 

[baric]

While that may seem like a huge sieve, an additional 8% reduction (going from 79% to 81%) can be quite significant over a large range of numbers and justify the initial sieve setup.

One more point. Keep in mind that the sieve can be built dynamically as the prime number search continues. So you could start with a small sieve {30k+n...} and factor the primes to 210. From that point, you already have the sieve for {210k+n... } where 'n' is the series of primes up to 210, excluding the primes used to create the sieve (2,3,5,7).

Then when you've factored the primes up to 2310, you can easily switch to the sieve {2,3,5,7,11}.

This way, your sieve will automatically become more efficient as you progress through the primes, up to your computer's memory capacity to maintain the sieve.

 

[epsi00]

I agree with you but since I can't write code, I won't be able to test all the issues you raised.

 

[baric]

I agree with you but since I can't write code, I won't be able to test all the issues you raised.

Can't write code?!?

aww, man.. that's the easy part! :)

 

[epsi00]

Can't write code?!?

aww, man.. that's the easy part! :)

well, if that's the easy part, you are welcome to experiment numerically with this sieve and take full credit for it. I am really curious to see how far we can go before we hit the rule of diminishing return. Obviously we can't keep improving the efficiency at little or no cost.

 

[baric]

well, if that's the easy part, you are welcome to experiment numerically with this sieve and take full credit for it. I am really curious to see how far we can go before we hit the rule of diminishing return. Obviously we can't keep improving the efficiency at little or no cost.

Like I said, it's totally dependent upon the computer's memory capacity although the size of the sieve does go up factorially with {p-1.. } where p is the series of primes, so you can't really get too far...

If you set the sieve limit to 1 billion, for example, your prime sieve stops at p(10)=29... i.e E!{p(1)-1*p(2)-1... *p(10)-1} = 1,021,870,080. At that point, you are filtering 84.2% of the integers. Adding 31 to the sieve increases the sieve size to 30 billion and raises the filtering to 84.7%, or an improvement of 3.33% (31/30). In addition, each entry in the sieve would occupy multiple bytes since we would be dealing with very large integers. (8 bytes each would allow representation of integers up to 1.8E19). So a sieve of 30 billion in size would require 240 gigabytes to maintain.

The realistic memory limit has to be around there because I doubt that anyone would want to designate several terabytes of memory to maintain a sieve of {2...37}

I guess you could write the program to query the heap space and automatically limit the sieve size to the computer's memory capacity. It would not be a bad way to do it since a 3% improvement over the factorization of 1.8E19 numbers is going to save a lot more time than it takes to set up the sieve.

Then you could simply throw more hardware (memory) at the problem to speed things up.

I'll see if I can write up some code for this tonight.

 

[epsi00]

Sometimes one may be interested in sieving between two numbers (N1,N2) instead of from (1,N). This sieve can probably be adapted to do that ( I haven't thought seriously about this case ). It's just a matter of figuring out how to calculate the max element of each column for the sieve of (1,N) then start from those max element and calculate the elements of columns up to N.

 

[bsquared]

This is an interesting variation of the wheel sieve, but I don't have any idea how efficiently it could be implemented versus a classic wheel. Especially if extended to larger residue class systems (i.e., mod 30 or mod 210).

My http://sourceforge.net/projects/yafu/" sieve currently uses wheel sieves up to mod 2310 (2*3*5*7*11) for sieving large ranges of the number line, and is one of the fastest sieve of eratosthenes implementations I'm aware of. I've spent enough time optimizing it that I don't have any interest in coding this variation, but I encourage you to learn how to do it yourself. I'll note that returns diminish sufficiently that mod 2310 is as high as I could go before the sieve speed actually started to decrease (mod 30030 involves sieving over too many residue classes).

 

[Ulam]

If you want be happy, you can arrest the algorithm at \sqrt{n}.

 

[idiom]

Hey this is correct but you can actually reduce to 1/5