Hello.

I am quite new to c++ but am working on translating a prime generator I have made over from c#.

I have everything working well but have found that c# can output to file faster than c++ (by around 10%). This is once the 'working out' is done.

Here is the c++ code that I am currently using:

FILE * handle = fopen("primes.dat", "w");

ostringstream buffer; buffer << 2 << ' ';

for (int x = 3; x < upper_primes; x += 2)
{
    if (!test_primes[x])
    {			
		if (buffer.tellp() > 4194304)
		{
			fputs(buffer.str().c_str(), handle);
			
			buffer.str("");
		}
		
		buffer << x << ' ';
    }
}

fputs(buffer.str().c_str(), handle);

fclose(handle);

As you can see it outputs to file every 4MB. I have tried a few variations from 1KB up to 4MB all with similar results.

I have also tried using ofstream directly rather than ostringstream and fputs. They offer very little performance difference.

So my question is simply.. for a loop that outputs millions of numbers (originally as type int) each followed by a space can you suggest a faster way to output the list?

FULL SOURCE CODE

Once I can fine tune this I will have to work on the multi-threading for the processing. My first attempt at that made it slower (I need to keep the threads for re-using rather than creating new ones every loop) .. but thats another matter.

Thanks in advance :)

Jonathan .

How about beginning with the fact that your approach to testing primes is horribly inefficient?

If you care to suggest a faster method then please do. On my machine this is generating all primes from 1 to 100,000,000 in around 4 seconds. My method isn't what you usually find on the web but I find that it does the job a lot faster than anything else i've found online. The result is a ~50MB file.

Already gave you a couple suggestions here

Thanks I will look into fprintf method. The ofstream I already have tried it wasn't any faster. I never even asked my question at that other website but regardless thanks for your reply.

Thanks I will look into fprintf method.

Unfortunately this only increased the output time. Any more suggestions ?

Observe how this does NOT check 9
http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

That's the most famous algorithm out there, and it should be quicker than yours.
Odd that you missed it in your "research"

Marking all multiples of 3, 5, 7 etc. and the rest are then primes. I get the idea. My method was based on that and is infact faster.

If you check the full source code you will see:

static bool test_primes[upper_primes];

const int square_root = (int) sqrt((double) num_primes) + 1;

for (int x = 3; x < square_root; x += 2)
{
	if (!test_primes[x])
	{
		const int up_limit = (num_primes / x) + 1;
	
		for (int mx = x; mx < up_limit; mx += 2)
		{
			test_primes[(mx * x)] = true;
		}	
	}
}

1. An array to mark of the multiples
2. Work out the square root
3. Loop through from 3 to square root marking multiples (missing out those that aren't primes themselves)

4. Output as shown in the already presented code.

Test it for yourself.

This article has been dead for over six months. Start a new discussion instead.