exscape

Oct 10, 2009, 11:41 AM

I want to apologize in advance for the extremely ugly typecasting in the isPrime for loop... ;) I don't feel like fixing it right now. You'll see...

Anyway. I'm trying to learn GCD, but I'm stuck. I figured I'd try to parallelize a simple program that checks whether a number is prime or not.

It calls isPrime() in a loop a certain number of times and reports the number of primes found.

Using a for loop, the number returned is always the same (6542 for the first 2^16 numbers) - as expected. Using dispatch_apply(), the number changes between approx. 2700-4700 (a few runs showed 3442, 3593, 4033, 4336, 2701, 3571). I have no clue as to why! Here's the code:

#include <stdio.h>

#include <math.h>

#include <dispatch/dispatch.h>

#define NONPRIME 0

#define PRIME 1

short isPrime(unsigned long long);

int main()

{

__block unsigned long primes = 0;

unsigned long long max = (1ULL << 16ULL);

/* to switch from GCD, uncomment these two lines, comment the dispatch_apply()

* and }); lines, and the } ending the for loop. */

//unsigned long long num = 0;

//for (num=0; num < max; num++) {

dispatch_apply(max, dispatch_get_global_queue(0, 0), ^(size_t num) {

primes += isPrime(num);

});

//}

printf("%lu primes found among the first %llu numbers\n", primes, max);

return 0;

}

short isPrime(unsigned long long n)

{

unsigned long long j;

if (n < 2)

return NONPRIME;

if (n == 2)

return PRIME;

if (n % 2 == 0)

return NONPRIME;

for (j=3; j<=((unsigned long long)((double)(sqrt((double)n)))+1); j+=2) {

if (n % j == 0)

return NONPRIME;

}

return PRIME;

}

What am I doing wrong?

Thanks in advance.

Anyway. I'm trying to learn GCD, but I'm stuck. I figured I'd try to parallelize a simple program that checks whether a number is prime or not.

It calls isPrime() in a loop a certain number of times and reports the number of primes found.

Using a for loop, the number returned is always the same (6542 for the first 2^16 numbers) - as expected. Using dispatch_apply(), the number changes between approx. 2700-4700 (a few runs showed 3442, 3593, 4033, 4336, 2701, 3571). I have no clue as to why! Here's the code:

#include <stdio.h>

#include <math.h>

#include <dispatch/dispatch.h>

#define NONPRIME 0

#define PRIME 1

short isPrime(unsigned long long);

int main()

{

__block unsigned long primes = 0;

unsigned long long max = (1ULL << 16ULL);

/* to switch from GCD, uncomment these two lines, comment the dispatch_apply()

* and }); lines, and the } ending the for loop. */

//unsigned long long num = 0;

//for (num=0; num < max; num++) {

dispatch_apply(max, dispatch_get_global_queue(0, 0), ^(size_t num) {

primes += isPrime(num);

});

//}

printf("%lu primes found among the first %llu numbers\n", primes, max);

return 0;

}

short isPrime(unsigned long long n)

{

unsigned long long j;

if (n < 2)

return NONPRIME;

if (n == 2)

return PRIME;

if (n % 2 == 0)

return NONPRIME;

for (j=3; j<=((unsigned long long)((double)(sqrt((double)n)))+1); j+=2) {

if (n % j == 0)

return NONPRIME;

}

return PRIME;

}

What am I doing wrong?

Thanks in advance.