Download A Nested Data-Parallel Language

Transcript
function primes(n) =
if n == 2 then [2]
else
let sqr primes = primes(ceil(sqrt(float(n))));
sieves = –[2*p:n:p]: p in sqr primes˝;
flat sieves = flatten(sieves);
flags = dist(t,n) <- –(i,f): i in flat sieves˝
in drop(–i in [0:n]; flag in flags| flag˝, 2) ;
Figure 8: Finding all the primes less than n.
flatten([[4, 6, 8, 10, 12, 14, 16, 18], [6, 9, 12, 15, 18]]);
⇒
[4, 6, 8, 10, 12, 14, 16, 18, 6, 9, 12, 15, 18] : [int]
This sequence of sieves is used by the <- function to place a false flag in all positions that
are a multiple of one of the sqr primes. This will return a boolean sequence, flags, which
contains a t in all places that were not knocked out by a sieve—these are the primes.
However, we want primes to return the indices of the primes instead of flags. To generate
these indices the algorithm creates a sequences of all indices between 0 and n ([0:n]) and
uses subselection to remove the nonprimes. The function drop is then used to remove the
first two elements (0 and 1), which are not considered primes but do not get explicitly
sieved.
The functions [s:e:d], flatten, dist, <- and drop all require a constant number
√
of steps. Since primes is called recursively on a problem of size n the total number of
steps require by the algorithm can be written as the recurrence:
(
S(n) =
O(1)
n=1
√
S( n) + O(1) n > 1
= O(lg lg n)
Almost all the work done by primes is done in the first call. In this first call, the work is
proportional to the length of the sequence flat sieves. Using the standard formula
X
1/p = log log x + C + O(1/ log x)
p≤x
where p are the primes [18], the length of this sequence is:
X
√
n/p = O(n log log n)
√
p≤ n
= O(n log log n)
therefore giving a work complexity of O(n log log n).
19