Jump to content
  • Advertisement
Sign in to follow this  
Grain

How can I make this use less memory? [Sieve of Eratosthenes]

This topic is 4698 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

#include <iostream>
#include <iomanip>
#include <set>
void Sieve(std::set<unsigned int>& s ,unsigned int n)
{
	unsigned int m,i;
	s.erase(s.begin(),s.end());
    
	std::cout << "Filling set: " << 1 << " to " << n << std::endl << std::endl;
	s.insert(1);
	s.insert(2);
	for(m=3; m<=n; m+=2)
		s.insert(m);
	
	std::cout << "Set Filled, " /*<< s.size() << " Items."<< std::endl*/ ;
	std::cout << "Removing non-primes:" << std::endl << std::endl;
	
	for(m=3; m*m <= n; m++)
	{
		if(s.find(m) != s.end())
		{
			i = 2 * m;
			while (i <= n)
			{
				s.erase(i);
				i += m;
			}
		}
	}
	std::cout << "Non-primes removed: " << s.size() << " items remaining" << std::endl;

}

int main()
{
	unsigned int count = 0;
	std::set<unsigned int> primes; 
	std::set<unsigned int>::iterator itr;
	Sieve(primes,35000000);

	std::cin >> count;
	itr = primes.begin();
	if(!count)
	{
		while(itr != primes.end())
		{
			count++;
			std::cout << " " << *itr << " ";
			if(count % 10 == 0)
				std::cout << std::endl;
			itr++;
		}
		std::cout << std::endl;

		std::cin >> count;
	}
	return 0;
}


The Sieve of Eratosthenes is used to calculate prime numbers in a given set of integers. The above program works great except for one thing. The problem with this is that I can only calculate about 35 million before it uses up my entire memory, about 1GB, at which point it starts using the swap file and the program slows to a snails pace while my hard drive thrashes around. With 35 million it takes about a minute to complete but with 40 million I let it run several hours before I killed it. I wanted to calculate all primes in the unsigned int range 0 to 0xFFFFFFFF which is 4 billion ints. So I need to make this use a lot less memory.

Share this post


Link to post
Share on other sites
Advertisement
Guest Anonymous Poster
how about just using one bit per number in a static array, i'm not sure if that is actually smaller as you have to store 1 bit per non-prime as well. You can for sure save some memory by using a mark and sweep approach on a static array of unsigned ints.

Share this post


Link to post
Share on other sites
Instead of std::set, I'd use array of bits. One for each odd number bigger than 1. First set all the bits, then go through the array, and for each bit set, you clear all the bits further in the array kind of like this:

for(int i=0;i<N;i++)
if (bitset)
for(int k=i+i;k<N;k+=i)
bitset=0;


If you use one bit per odd integer, you'd need 2^28 bytes = 256 Megs to find all primes less than 2^32.

AP: It would take less memory, as he's initializing his std::set with all the odd integers, taking 2^31*4 bytes = 16 Gigs for all up to 2^32, plus the overhead from std::set, which is in some proportion to the amount of elements in it.

Share this post


Link to post
Share on other sites
Quote:
Original post by Anonymous Poster
how about just using one bit per number in a static array, i'm not sure if that is actually smaller as you have to store 1 bit per non-prime as well. You can for sure save some memory by using a mark and sweep approach on a static array of unsigned ints.


That should use ~512MiB (e.g. 1/8th of 4GiB) to cover 0..0xFFFFFFFF, so that would indeed come out to a smaller amount.

Share this post


Link to post
Share on other sites
Firstly, do not populate the set first. If a number isn't prime, the sieve doesn't need to remember it. Instead, generate your set at runtime using a for loop and test each number as it comes but do not store non-primes in the memory for more than one iteration.

Also, on a mathematical point, the higher up in the set of integers you go, it becomes exponentially less likely that each number is prime. If I understand your code correctly, you're using less memory as time goes on, since you populate the set at the start and then remove the non-prime elements. The problem is that primes become incredibly sparse when you enter the millions, so getting from 35 million primes to 40 million is going to take a very long time.

Share this post


Link to post
Share on other sites
Quote:
Original post by Grain
How to I make an array of bits? There is no bit type as far as I know.


There's bound to be a bitvector class somewhere (probably in boost), but if you can't find one, here's the basics:


class mybits
{
std::vector<unsigned char> vec;

public:
mybits(int bits) { vec.resize(bits/8); };

set(int bit,bool on=true) {
int b=bit%8;
int p=bit/8;
int mask=1<<b;
vec

=(vec

&(~mask))|(on?mask:0);
}
clear(int bit) { set(bit,false); };
}



I won't guarantee that that'll work (since I just typed it from the top of my head), but the idea should be clear enough.

Share this post


Link to post
Share on other sites
You'll have to do it manually, probably create a custom container class. Check out the bitwise logic and shift operators. You basically want to have a bunch of 32bit integers, shift the required bit into place and "and" it with 1.

Here is an interesting concept which you could use: Ranges (from here).


One bit for each possible odd number of a 32 bit integer is 256 megabytes of data. It should fit nicely [smile].

Share this post


Link to post
Share on other sites
Just for fun, here's a class. This "should" work [wink]. It will automatically return "not-set" for even numbers. Uses a puny 256 megabytes [smile]. You should probably test it before use, though.

class oddbits
{
private:
// enough space for every odd unsigned int in 32 bits
static const size_t SIZE = 0x4000000;
uint32 d[SIZE];

public:
oddbits() { for(size_t i=0; i<SIZE; i++) d=0; }

bool get(unsigned int i)
{
return (i&1==1) && ((d[i>>6]>>(i>>1))&1==1);
}

void set(unsigned int i, bool v)
{
if(i&1==0) return;

uint32 x = (1<<((i>>1)&1F));
d[i>>6] = (d[i>>6]&~x)|(v?x:0);
}
};

Share this post


Link to post
Share on other sites
Quote:
Original post by Motz
Firstly, do not populate the set first. If a number isn't prime, the sieve doesn't need to remember it. Instead, generate your set at runtime using a for loop and test each number as it comes but do not store non-primes in the memory for more than one iteration.

Also, on a mathematical point, the higher up in the set of integers you go, it becomes exponentially less likely that each number is prime. If I understand your code correctly, you're using less memory as time goes on, since you populate the set at the start and then remove the non-prime elements. The problem is that primes become incredibly sparse when you enter the millions, so getting from 35 million primes to 40 million is going to take a very long time.


Quoted for value. Instead of storing all the numbers and then removing the composite values, you can consider each number for prime-ness as you get to it, and insert it. Since you will then not have to remove values from the middle, you can use a more space-efficient container as well: std::vector.


#include <iostream>
#include <iomanip>
#include <vector>

void Sieve(std::vector<unsigned int>& s ,unsigned int n) {
unsigned int m,i;
s.erase(s.begin(),s.end());
s.push_back(1);
s.push_back(2);
for(m=3; m<=n; m+=2) {
int count = s.size();
bool prime = true;
for (int i = 0; i < count; ++i) {
if (!(m % s)) { // current value is divisible by a former prime;
// discard it
prime = false; break;
// In case you're wondering, solving this with a goto is just as tricky;
// you'd need to put it at the *end* of the outer loop, with no
// action following it, which is rather bizarre.
}
}
if (prime) s.push_back(m);
}
}



Of course, this isn't the Sieve of Eratosthenes any more (pedantically speaking anyway), but it's how it's normally done :s

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!