Register to reply

A new prime sieve

by epsi00
Tags: primes sieve
Share this thread:
epsi00
#1
Mar31-11, 12:57 PM
P: 84
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.
Attached Files
File Type: pdf new prime sieve1.pdf (11.7 KB, 70 views)
Phys.Org News Partner Science news on Phys.org
Hoverbike drone project for air transport takes off
Earlier Stone Age artifacts found in Northern Cape of South Africa
Study reveals new characteristics of complex oxide surfaces
epsi00
#2
Apr15-11, 09:13 AM
P: 84
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
#3
Apr15-11, 01:19 PM
P: 205
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
#4
Apr15-11, 02:13 PM
P: 84
A new prime sieve

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
#5
Apr15-11, 02:28 PM
P: 205
Quote Quote by epsi00 View Post
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-dimentional arrays, I wonder if its applicable.
JeremyEbert
#6
Apr15-11, 02:56 PM
P: 205
I would love an example!
Hurkyl
#7
Apr15-11, 03:00 PM
Emeritus
Sci Advisor
PF Gold
Hurkyl's Avatar
P: 16,099
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 [itex]\pi(N)[/itex], 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
#8
Apr18-11, 09:29 AM
P: 84
Quote Quote by Hurkyl View Post
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 [itex]\pi(N)[/itex], 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
#9
Apr18-11, 10:07 AM
P: 84
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
#10
Apr19-11, 09:18 AM
P: 84
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=141


141 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=150


150 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=134


we 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
#11
Apr27-11, 11:59 PM
P: 166
Removing the multiples of 2 and 3 is the first to steps of the normal sieve.
epsi00
#12
Apr28-11, 07:02 AM
P: 84
Quote Quote by dalcde View Post
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
#13
Apr30-11, 10:06 PM
P: 12
Quote Quote by epsi00 View Post
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
#14
May1-11, 07:47 AM
P: 84
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
#15
May1-11, 09:59 AM
P: 12
Quote Quote by epsi00 View Post
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
#16
May1-11, 10:07 AM
P: 12
Quote Quote by baric View Post
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
#17
May1-11, 11:42 AM
P: 84
I agree with you but since I can't write code, I won't be able to test all the issues you raised.
baric
#18
May2-11, 09:04 AM
P: 12
Quote Quote by epsi00 View Post
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! :)


Register to reply

Related Discussions
Twin Prime Sieve Linear & Abstract Algebra 2
Goldbach’s Conjecture and the 2-Way Sieve General Math 6
An algorithm based on Eratosthenes Sieve Programming & Computer Science 6
Sieve of Eratosthenes - Programming in VB Computing & Technology 14