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