DAPPLE Example: prime
Source code:
// prime -- a parallel prime-number program
// written using the Data-Parallel Programming Library for Education (DAPPLE)
//
// This program uses the Sieve of Erasthenes to produce prime numbers.
// It produces one prime number in each iteration, and then divides
// all candidate numbers by that prime in parallel, to reduce the set of
// candidates.
// This algorithm is not very efficient, because even after a number is
// determined to be composite, it still occupies a virtual processor and
// still participates in the computation.
//
// David Kotz 1994
// $Id: prime.cc,v 2.13 94/09/29 12:18:28 dfk Exp $
#include
#include
#include
#include "dapple.h"
const int N = 100;
const intVector VP(N, Identity); // which VP am I?
int
main(int argc, char **argv)
{
booleanVector candidate(N); // VP i is a candidate if candidate[i] true
int prime; // a prime number
// each VP represents one of the possible numbers 0..N-1
// those where candidate==true are possible prime numbers
// initially, all >= 2 are considered possible prime numbers
candidate = (VP >= 2); // true except for VPs 0 and 1
// repeatedly,
// note that the first VP with candidate==true is a prime number
// print that prime out
// set candidate=false for all VPs whose index is divisible by prime
// stop when there are no remaining candidates.
while (any(candidate)) {
ifp (candidate)
prime = first(VP); // first number is a prime
cout << prime << endl; // print that prime number
ifp (VP % prime == 0) // all those VPs divisible by this prime
candidate = false; // drop out from consideration
}
return(0);
}
Demonstration:
prime
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97