Multi Prime - A multi-threaded prime number benchmark

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.

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

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.

Quote:

---

Originally Posted by MuffinFlavored

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.

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...

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.

They call me un-decisive Urnest.

Code:

---

        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?

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

try this instead:

Code:

---

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

Quote:

---

Originally Posted by Alpha

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

try this instead:

Code:

---

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?

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.

Quote:

---

Originally Posted by 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.

---

You are very right.

Here is muffinPrime. (:p:)

Code:

---

#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;
}

---

Quote:

---

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.

Code:

---

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.

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.

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

hmm nice :D

Quote:

---

Originally Posted by 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

---

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.