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