Optimizing Sieve of Eratosthenes

One of the most popular prime number algorithm is the Sieve which comes handy when you are required to generate prime numbers up to an upper bound.In this post we’ll be optimizing sieve to save both memory as well as time.

The optimization that we’ll be performing will be both memory as well as time efficient.

NOTE – I won’t be discussing how the basic sieve works.(Check out – Sieve(without optimisation)).

We will move step by step towards optimizing the algorithm to maximum extent.(If you know any further optimizations, please do share in the comment box).

So here’s what sieve looks like without any optimization.

//============================================================================
// Name        : sieve.cpp
// Author      : Prateek Agarwal
// Institution : NIT Jalandhar
//============================================================================

#include <bits/stdc++.h>
using namespace std;

#define MAX 1000000
#define SQ 1000

int prime[MAX+1];

int sieve(){
	for (int i=2;i<=SQ;i++){
		if (!prime[i]){
			for(int j=i*i;j<=MAX;j+=i){
				prime[j] = 1;
			}
		}
	}
	return 0;
}

int main(){
	sieve();
	return 0;
}

 

Lets begin our optimization!

Considering that you are processing the algorithm for 1000 elements, the size of the array is 4000 bytes (4 bytes or 32 bits per int value).

Instead of using an entire integer(32 bits) for marking as prime(or composite) , you could use just 1 bit.How?

use array index ‘0’ to store values for the first 32 (from 1 to 32) numbers, index ‘1’ for the next 32 (from 33 to 64) numbers and so on..

bitmask1.png

 

This will save us a lot of memory.But still there’s no improvement in time.

Just don’t consider the even values at all.This will make your algorithm faster by a factor of 2 or more.

Now all we have are odd values to deal with.Lets see what the arrangement will look like after neglecting the even values.

bitmask2.png

 

This not only speeds up your algorithm, but saves even more memory.(Now we are using 4000/64 = 62.5 bytes of memory).

So here’s the code for the complete optimization and later we’ll see how the bit wise magic is working.

//============================================================================
// Name        : optimised_bitwise_sieve.cpp
// Author      : Prateek Agarwal
// Institution : NIT Jalandhar
//============================================================================

#include <bits/stdc++.h>
using namespace std;

#define MAX 100000000
#define SQ 10000

//These macros are discussed below
#define check(n) (prime[n>>6]&(1<<((n&63)>>1)))
#define set(n) prime[n>>6]|=(1<<((n&63)>>1))

int prime[MAX>>6];

int sieve(){
	for(int i=3;i<=SQ;i+=2){
		if (!check(i)){
			int inc = 2*i;
			for(int j=i*i;j<=MAX;j+=inc){
				set(j);
			}
		}
	}
	return 0;
}

int main(){
	sieve();
	return 0;
}

 

Let us see how we can access and modify the bit value for a number ‘n’ (n is odd) .

  1. Get the array index where the bit value of ‘n’ is stored. Since we are storing the bit values of 32 consecutive odd numbers in one integer , the array index can be generalized as n/64 or n>>6 . So the array value if prime[n>>6].
  2. Now in order see which bit to visit,we have to modulo by 64 and then divide by 2.Example – numbers 1 and 65 in the picture above both have their result stored in first (least significant) bit but in different indexes. If we modulo both of them by 64,we will get 1 and then divide by , we will get which is the required bit position.
  3. the modulo operation n%64 can be seen as n&63 . This is similar to what happens when we divide a number(in base 10) by 10^k . We get the last k digits of that number.Except this time the modulo operation is taking place in base 2. So if we modulo n number by 2^6 , we will get the last 6 digits in the base 2 representation of n. (which is n&63).Try it out yourself for further clarification.

So to sum up, the first point gives us the logic for the array index in which the bit value for n is present – prime[n>>6]

And second and third points combined tells us about the bit position given by – ((n&63)>>1)

Now we can check as well as set the bit values.

Hope you understood the post 🙂

Here’s a question on optimized bit wise sieve (where normal sieve won’t work) on SPOJ-TDKPRIME.

Advertisements

4 thoughts on “Optimizing Sieve of Eratosthenes

    • Since an integer has 32 bits, each bit can be used as a hash for a number (instead of using an entire array index as hash)
      For eg- Normal hashing is done like this
      Hash[0] = 0 or 1 (indicates hash value for 0)
      Hash [1] = 0 or 1(indicates hash value for 1)….. And so on

      Here, since 0 and 1 are only possible values to store(which can be done by setting a bit on or off)
      An integer (Hash[i] having 32bits) can store the hash values for 32 different integers.
      Refer the image for clarity

      Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s