Taylor Liesnham Taylor Liesnham - 7 months ago 61
C Question

How do I chunk prime numbers for multithreading?

I'm relatively new to C, and up until now had barely any experience in multithreading. I've written a small program that calculates whether an array of numbers are primes or composites. This works fine, but when working with larger numbers I'd like to split the workload between threads.

I sort of have an idea of how this would work, I just can't see how to implement this within C. As a simple example if we take the prime 199, I would divide this number by the number of cores (e.g. 4) to get 49.75. We would then round this number to 50. Each thread would then be given a range to calculate.

The first thread would calculate from i 2 to 50, the second from i 51 to 102, and so on.

I hope that makes some sense, I'm sure the solution is easier than I think it is, it's just I can't for the life of me work it out.

My Code:

#include <pthread.h>
#include <inttypes.h>
#include <stdio.h>
#include <unistd.h>

#ifdef _SC_NPROCESSORS_ONLN
#define NUM_THREADS sysconf(_SC_NPROCESSORS_ONLN)
#else
#define NUM_THREADS 1
#endif

uint64_t numbers[] = {7,3,19,17,199,333}; // Numbers to check

void *work(void *n_void_ptr);
int isPrime(uint64_t n);

int main()
{
int rc;
pthread_t thread[NUM_THREADS];

for (int i = 0; i < sizeof(numbers) / sizeof(uint64_t); i++) {
rc = pthread_create(&thread[i], NULL, work, &numbers[i]);
}

pthread_exit(NULL);

return 0;
}

void *work(void *n_void_ptr)
{
uint64_t *n_ptr = (uint64_t *)n_void_ptr;

if (!isPrime(*n_ptr)) {
printf("%llu is a prime!\n", *n_ptr);
}

pthread_exit(NULL);
}

int isPrime(uint64_t n)
{
int count = 0;
uint64_t i; // Any number > n/2 cannot be a factor

for (i = 2; i < n / 2 - 0.5; i++) {
if (n % i == 0) {
count++;
}

if (count == 1) {
printf("%llu is composite!\n", n);

return -1; // n is not prime
}
}

return 0; // n is prime
}

Answer Source

So what you want to do is have different threads to check for different non overlapping ranges.

We need a struct first to pass the ranges to the workers. So we start with -

typedef struct {
    int lower;
    int upper;
    int number;
    int result;
} worker_range;

Now in the main I am assuming you need to check 199 and each thread needs to check 50 values.

We start like this

worker_threads **ranges = malloc(sizeof(worker_threads*) * (199 / 50 + 1));

Now we need to spawn the threads

int i;
for ( i = 0; i < 199 / 50 + 1; i++){ //Fix this so that extra threads are not spawned.
    ranges[i] = malloc(sizeof(worker_range));
    ranges[i]->number = 199;
    ranges[i]->lower = 2 + i * 50;
    ranges[i]->upper = range->lower + 50; //We are probably okay with a bit of overflow
    range[i]->result = 0;
    pthread_create(&thread[i], NULL, work, ranges[i]);
}

Now that all threads have started, we wait for them to finish.

int flag = 0;
for ( i = 0 ;i < 199 / 50 + 1; i++) {
    pthread_join(thread[i]);
    if(ranges[i]->result == 1)
        flag = 1;
    free(ranges[i]);
}
if (flag==1){
    printf("%d is composite\n",199);
}else{
    printf("%d is prime\n",199);
}
free(ranges);

Finally the worker function -

void* work(void * param) {
    work_range *range = param;
    int i;
    for(i = range->lower, i < range->upper; i++){
        if (range->number % i == 0){
            (range->result) = 1;
            break;
        }
    }
}

I hope this helps.