Sieve of Eratosthenes : Bitwise version

After searching the net i came to know that the bit-wise version is pretty efficient.
The problem is i am unable to understand the math/method it is using.

The version that i have been busy with looks likes :

#define MAX 100000000
#define LIM 10000

unsigned flag[MAX>>6]={0};

#define ifc(n) (flag[n>>6]&(1<<((n>>1)&31)))         //LINE 1
#define isc(n) (flag[n>>6]|=(1<<((n>>1)&31)))        //LINE 2

void sieve() {
    unsigned i, j, k;
    for(i=3; i<LIM; i+=2)
        if(!ifc(i))
            for(j=i*i, k=i<<1; j<LIM*LIM; j+=k)
                isc(j);
}

Points that I understood (Please correct me if I am wrong):
1)Statement in line 1 checks if the number is composite.
2)Statement in line 2 marks the number 'n' as composite.
3)The program is storing the value 0 or 1 at a bit of an int. This tends to reduce the memory usage to x/32. (x is the size that would have been used had an int been used to store the 0 or 1 instead of a bit like in my solution above)

Points that are going above my head as of now :
1)How is the finction in LINE 1 functioning.How is the function making sure that the number is composite or not.
2)How is function in LINE 2 setting the bit.
3)I also came to know that the bitwise sieve is timewise efficient as well. Is it because of the use of bitwise operators only or something else is contributing to it as well.

Please give any additional info if you have.
Any sort of help is highly appreciated.
Thanks a lot.

Last edited on

The Protostar (26)

Please anyone??

Smac89 (1727)

You declared an array of unsigned values on line 4, but you never initialised the values to anything. Then you are using some of the elements of the array in your macro function. How do you know what value is in the array or are the values initialised to zero for unsigned array, because it will make more sense that way?

The Protostar (26)

Yes, even i was wondering about that. I thought of editing it... but later decided to put it in the same form as i found on the website. had the flag elements been initialised. theey would have been set to zero only.

@Smac89 code edited.

Last edited on

The Protostar (26)

For printing the primes you need to do this

for i =3 to n
if(!ifc(i))
print i

The Protostar (26)

Here is the link to the approach in wikibook : http://en.wikibooks.org/wiki/Algorithm_Implementation/Mathematics/Prime_number_generation#C_.28bitwise.29

Here is their implementation :

#include <math.h>
#define MAX 1000000
const int S=(int)sqrt((double)MAX);
 
#define rP(n) (sieve[n>>6]|=(1<<((n>>1)&31)))
#define gP(n) sieve[n>>6]&(1<<((n>>1)&31))
 
unsigned sieve[(MAX>>6)+1]={0};
int i, j,k,l=0 , prime[MAX];
prime[0]=2;
for(i=3;i<=S;i+=2) if(!(gP(i))) {
        k=(i<<1);
        prime[l++]=i;
        for(j=i*i;j<=MAX;j+=k) rP(j);
}
 
for(;i<=MAX;i++) if(!(gP(i))) prime[l++]=i;

Last edited on

The Protostar (26)

Problem is solved just examined a few cases deeply.
@smac89 thanks. :)

Topic archived. No new replies allowed.

Sieve of Eratosthenes : Bitwise version

C++

Forum