Created
March 17, 2021 16:32
-
-
Save TheVoxcraft/2fd8bb40d8dd2bf4d21f3793704dfd3e to your computer and use it in GitHub Desktop.
My multithreaded implementation in C of finding primes, 10x faster than PyPy implementation .
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
#include <stdbool.h> | |
#include <stdlib.h> | |
#include <time.h> | |
#include <pthread.h> | |
#include <math.h> | |
struct thread_args{ | |
int start_number; | |
int end_number; | |
}; | |
void* calculate_thread(void *p) | |
{ | |
struct thread_args *args = (struct thread_args *) p; | |
int start_number = args->start_number; | |
int end_number = args->end_number; | |
int noPrimes = 0; | |
for (unsigned int i = start_number; i <= end_number; i++){ | |
bool found = true; | |
for (unsigned int div = 2; div < i; div++){ | |
if((i % div) == 0){ | |
found = false; | |
break; | |
} | |
} | |
if(found == true){ | |
noPrimes++; | |
} | |
} | |
free (args); | |
pthread_exit((void*)(intptr_t) noPrimes); | |
} | |
int main() { | |
int END_NUMBER = 200000; | |
int THREAD_COUNT = 6; | |
int noPrimes = 0; | |
time_t start, end; | |
double diff; | |
time (&start); | |
printf("Finding all primes up to: %d\n", END_NUMBER); | |
int total = 0; | |
pthread_t tid[THREAD_COUNT]; | |
int chunk_size = floor(END_NUMBER/THREAD_COUNT); | |
for (int thread_id = 0; thread_id < THREAD_COUNT; thread_id++){ | |
struct thread_args *args = malloc (sizeof (struct thread_args)); | |
args->start_number = chunk_size*thread_id; | |
args->end_number = chunk_size*(thread_id+1); | |
pthread_create (&tid[thread_id], NULL, calculate_thread, (void*) args); | |
printf("Created thread %i \n", thread_id); | |
//printf("%d to %d\n", args->start_number, args->end_number); | |
} | |
for (int thread_id = 0; thread_id < THREAD_COUNT; thread_id++){ | |
void *sum = NULL; | |
pthread_join (tid[thread_id], &sum); | |
total += (int)(intptr_t) sum; | |
} | |
time (&end); | |
diff = difftime (end,start); | |
printf("Took: %.2lfs, found: %i", diff, total); | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment