Why doesn't this work with N>8000

[yelnatz]

It returns correctly for anything less than 8000 as max. Any clues?

void sieve::sequential(){
	std::list<double> seqPrimes;
	double root = sqrt(max);

	if ( max < 1 ) return;
	
	// start with 2
	seqPrimes.push_back(2);
	
	// get everyone else
	for(double i = 3; i < max; i += 2 ){
		double s = 6;
		if( ( std::fmod((i-1),s) == 0 ) || (std::fmod((i+1),s) == 0 ) )
			seqPrimes.push_back(i);
	}

	// initialize iterators
	std::list<double>::iterator outside = seqPrimes.begin();
	std::list<double>::iterator inside = seqPrimes.begin();
	++inside; // start inside as the one after 

	// start 
	while( outside != seqPrimes.end() ){
	
		// if outside iterator is > root, done
		if( *outside >= root ) break;
		
		// inside iterator is the one were checking against
		while( inside != seqPrimes.end()){

			// if inside is divisible by outside, its not prime
			if ( fmod( *inside, *outside ) == 0 ){
				inside = seqPrimes.erase( inside ) ;
			}
			// check next number
			++inside;
		}
		// we've elimated all numbers that are divisble by outside
		// now go to the next one
		++outside;

		// set the inside counter to the next element of outside
		inside = outside;
		++inside;
	}
	std::cout << "# of primes < " << max << " : " << seqPrimes.size() << std::endl;
}

[tfityo]

Maybe rounding errors?
Why do use double, not integers?

[yelnatz]

I'm only using doubles so I get more numbers later on, no other reason.

[tfityo]

Then you should use unsigned long long, it also occupies 8 bytes and provides accurate representation of integer numbers.
Ordinary int can represent numbers up to 2,000,000,000. Do you need more?

[yelnatz]

Hey, I fixed it. It was something to do with my inside iterator being on at the end and me increasing it still.

I put in long long int from what you've said, I need the big numbers since I'm doing the parallel version after this.

Thanks.

void sieve::sequential(){
	std::list<unsigned long long> seqPrimes;
	unsigned long long root = sqrt(max);

	if ( max < 1 ) return;

	// start with 2
	seqPrimes.push_back(2);	
	seqPrimes.push_back(3);

	// get everyone else
	for(unsigned long long i = 3; i < max; i += 2 ){
		unsigned long long s = 6;
		if( ( std::fmod((i-1),s) == 0 ) || (std::fmod((i+1),s) == 0 ) )
			seqPrimes.push_back(i);
	}

	// initialize iterators
	std::list<unsigned long long>::iterator outside = seqPrimes.begin();
	std::list<unsigned long long>::iterator inside = seqPrimes.begin();
	unsigned long long outside_prime, inside_num;

	// start 
	while( outside != seqPrimes.end() ){

		outside_prime = *outside;// set the inside counter to the next element of outside
		if( outside_prime >= root ) break;
		inside = outside;

		if( inside != seqPrimes.end())
			++inside;

		// inside iterator is the one were checking against
		while( inside != seqPrimes.end()){
			inside_num = *inside;
			// if inside is divisible by outside, its not prime
			if ( inside_num % outside_prime == 0 ){
				inside = seqPrimes.erase( inside ) ;
			}
			// check next number
			if( inside != seqPrimes.end())
				++inside;			
		}
		// we've elimated all numbers that are divisble by outside
		// now go to the next one		
		++outside;
	}
	std::cout << "# of primes < " << max << " : " << seqPrimes.size() << std::endl;
}

[tfityo]

Just one more little comment. This part of code

	for(unsigned long long i = 3; i < max; i += 2 ){
		unsigned long long s = 6;
		if( ( std::fmod((i-1),s) == 0 ) || (std::fmod((i+1),s) == 0 ) )
			seqPrimes.push_back(i);
	}

is expensive (because of division) and error prone (because of possible rounding errors). You can do something like it:

for (int i = 6; i < max; i += 6){
 seqPrimes.push_back(i - 1);
 seqPrimes.push_back(i + 1);
} 

[yelnatz]

You were right.

void sieve::sequential(){
	std::list<int> seqPrimes;
	int root = sqrt(max);
	int s = 6;

	if ( max < 1 ) return;

	// start with 2 and 3
	seqPrimes.push_back(2);	
	seqPrimes.push_back(3);

	// get everyone else
	for (int i = 6; i < max; i += 6){
		seqPrimes.push_back(i - 1);
		seqPrimes.push_back(i + 1);
	}

	// initialize iterators
	std::list<int>::iterator outside = seqPrimes.begin();
	std::list<int>::iterator inside = seqPrimes.begin();
	int outside_prime, inside_num;

	// start 
	while( outside != seqPrimes.end() ){

		outside_prime = *outside;

		// only check until root+1 ( compensate rounding errors )
		if( outside_prime >= root+1 ) break;

		// set the inside counter to the next element of outside
		inside = outside;
		if( inside != seqPrimes.end())
			++inside;

		// inside iterator is the one were checking against
		while( inside != seqPrimes.end()){
			inside_num = *inside;
			// if inside is divisible by outside, its not prime
			if ( inside_num % outside_prime == 0 ){
				inside = seqPrimes.erase( inside ) ;
				continue;
			}
			// check next number
			if( inside != seqPrimes.end())
				++inside;
		}
		// we've elimated all numbers that are divisble by outside
		// now go to the next one		
		++outside;
	}
	std::cout << "# of primes < " << max << " : " << seqPrimes.size() << std::endl;
}