Multi Prime - A multi-threaded prime number benchmark

[Alpha]

Here, over at EOCF is my thread about my multi threaded prime number program i wrote for windows and linux

The current windows version is 1.1, and it uses a GUI

the current linux version is 0.9 and is x64 only.

if you want, post results over at EOCF as that is my home forum

The default test is 32,000,000 - or test 12 if you want to run the console version (0.9)

my lappy with a t7500 @ 2.2 Ghz does it in a little over 28 seconds, while my wife's quad core at 3ghz did it a little over 10 seconds.

the more cores and speed you have, the faster this runs.

KillerBeagle over at EOCF ran the linux version on a dual quad core work server (8 @ 3ghz) and scored a bit over 2 seconds on 32,000,000.

[MuffinFlavored]

Would you mind releasing the source code for the actual benchmark itself?

[CyberDruid]

Interesting.

It would be nice to have some sort of way of monitoring the progress of the work. I ran it while folding two SMP clients and it works...lol but the times look slow.

[Alpha]

Would you mind releasing the source code for the actual benchmark itself?

source code... not quite yet....

looks slow? my Asus Eee PC Celeron M @ 900mhz ran the linux version (compiled myself) and did the 32,000,00 test in about 190 seconds. try it on a single core system and then run it again and a dual core or greater system.

[Metric]

Looks good so far.

A few threaded prime benchmarks have been in the works around here on XS, and it seems compared to some of those, this one does run a *little* slower than the other ones. If you don't mind, from a programming standing-point, what sort of method are you using to determine prime numbers (Sieve, etc)? I have one currently in the works, and I wouldn't mind seeing how it compares to others...

[Alpha]

just the standard brute force method

check each odd number against each odd number up to it's square root.

i found that wPrime was actually slow than mine across 8 cores at a faster speed (thanks to another thread here with the QX9770's) 32m in 3.3 seconds @ 3.2 or faster compared to 32m with 8 cores at 2.02 seconds at 3ghz

just ran wPrime against my multi prime - almost the same numbers, but not enough to justify another 11 seconds of running.

[MuffinFlavored]

They call me un-decisive Urnest.

        int n = 1;
	int i = 2;
	int a = 0;
	int begin = time(NULL);

	while (1) {
		for(i = 2; i <= sqrt(n); i++) {
			if(n &#37; i == 0) {
				a++;
			}
		}

		if (a >= 32000000) {
			break;
		}

		n++;
	}

	printf("32,000,000 primes - %d seconds\n", time(NULL)-begin);

Is that similar to your code?

[Alpha]

close enough, but try checking only odd number against odd numbers.

try this instead:

for( int x = 3; x < 32000000; x+= 2)
{
	for(int y = 3; y * y <= x;  y+= 2)
	{
		if( x &#37; y == 0)
		{
			//number x isnt prime
			break;
		}
	}
}

you'll find this to be MUCH faster - and i found a few glitches in your code...

and to thread that code, i just made a few tweaks and used a library called pthreads

[MuffinFlavored]

close enough, but try checking only odd number against odd numbers.

try this instead:

for( int x = 3; x < 32000000; x+= 2)
{
	for(int y = 3; y * y <= x;  y+= 2)
	{
		if( x % y == 0)
		{
			//number x isnt prime
			break;
		}
	}
}

you'll find this to be MUCH faster - and i found a few glitches in your code...

and to thread that code, i just made a few tweaks and used a library called pthreads

for( int x = 3; x < 32000000; x+= 2)

Are you only finding 16000000 primes then?

[Alpha]

well the question here is, do you want to find all the prime numbers up to a value or find value number of primes?

that method finds all the primes up to value.

why start at 2 to find every even number to not be prime? its a waste of resources every other itteration. really, you only need to check if a number is prime by checking its divisability by every prime number <= its sqrt.

[MuffinFlavored]

well the question here is, do you want to find all the prime numbers up to a value or find value number of primes?

that method finds all the primes up to value.

why start at 2 to find every even number to not be prime? its a waste of resources every other itteration. really, you only need to check if a number is prime by checking its divisability by every prime number <= its sqrt.

You are very right.

Here is muffinPrime. ()

#include <string.h>
#include <windows.h>
#include <math.h>
#include <time.h>

typedef struct range {
    int start;
    int stop;
} MYDATA, *PMYDATA;

int is_prime(int number) {
	int i = 2;

	for (i = 2; i <= sqrt(number); i++) {
		if (number &#37; i == 0) {
			return 0;
		}
	}

	return 1;
}

void WINAPI test(LPVOID lpParam) { //The benchmark itself
	PMYDATA pDataArray;
	int start, stop, primes;

	pDataArray = (PMYDATA)lpParam;
	start = pDataArray->start;
	stop = pDataArray->stop;
	primes = 0;

	while (primes <= stop) {
		if (is_prime(start) == 1) {
			primes++; //If the number is prime, add 1 to primes found
		}

		start += 2;
	}
}

int main() {
	HANDLE hThread[16]; //For a maximum of 16 processors
	PMYDATA pDataArray[16];
	SYSTEM_INFO system_info;

	int i, start, max, stop, start_time, end_time, threads, size;
	char* buffer;

	GetNativeSystemInfo(&system_info);
	threads = system_info.dwNumberOfProcessors; //Get number of processors
	i = 0;
	start = 1;
	max = 1000000;
	stop = max/threads;
	start_time = time(NULL);

	size = strlen("Calculating prime numbers on threads!\n") + 10;
	buffer = malloc(size);
	sprintf(buffer, "Calculating %d prime numbers on %d threads!\n", max, system_info.dwNumberOfProcessors);
	MessageBox(NULL, buffer, "Starting benchmark!", MB_OK);

	for (i = 0; i < threads; i++) {
		pDataArray[i] = (PMYDATA)HeapAlloc(GetProcessHeap(), HEAP_ZERO_MEMORY, sizeof(MYDATA));

		pDataArray[i]->start = start;
		pDataArray[i]->stop = stop;

		hThread[i] = CreateThread(NULL, 0, (LPTHREAD_START_ROUTINE)test, pDataArray[i], 0, NULL);
		start += max/threads;
		stop += max/threads;
	}

	WaitForMultipleObjects(threads, hThread, TRUE, INFINITE);

	for (i = 0; i < threads; i++) {
		CloseHandle(hThread[i]);
		HeapFree(GetProcessHeap(), 0, pDataArray[i]);
        pDataArray[i] = NULL;
	}

	end_time = time(NULL);

	size = strlen("It took seconds to calculate prime numbers on threads.\n") + 16;
	buffer = malloc(size);
	sprintf(buffer, "It took %d seconds to calculate %d prime numbers on %d threads.\n", end_time-start_time, max, threads);
	MessageBox(NULL, buffer, "Finished benchmark!", MB_OK);

	return 1;
}

[Alpha]

int is_prime(int number) {
int i = 2;

for (i = 2; i <= sqrt(number); i++) {
if (number % i == 0) {
return 0;
}
}

return 1;
}

try this instead.

int is_prime(int number) {
	int i = 3;

	for (i = 3; i <= sqrt(number); i+=2) {
		if (number % i == 0) {
			return 0;
		}
	}

	return 1;
}

then, only send it in odd numbers, as all numbers are prime, and no even numbers are ever prime. cuts your time in half.

[Metric]

What about using a sieve (Eratosthenes or Atkin)? This cuts down on time tremendously if the algorithm is multi-threaded correctly and it stresses ram somewhat as well. If your interested, I can post a pseudo-code layout of how it works. The threaded Eratosthenes algorithm I've been working on has a time of 0.9 seconds for 32M on my Q6600 @ 3.6GHz.

[Alpha]

oh, i already got my seive code working....

but im not letting him have at that. a 2^31 -1 run uses about 256mb of ram and i can find all the primes upto that point in about 30 seconds on my T7500 with 2 threads.

its soooo much faster than the brute force method

oh, i just checked my 32m time - .329 seconds

[begrip]

hmm nice

[MuffinFlavored]

oh, i already got my seive code working....

but im not letting him have at that. a 2^31 -1 run uses about 256mb of ram and i can find all the primes upto that point in about 30 seconds on my T7500 with 2 threads.

its soooo much faster than the brute force method

oh, i just checked my 32m time - .329 seconds

Nice, my code is quite slow.

I need to find a way that once the first thread is done (which is sooner than all the other threads), to create another thread and do more work.