next up previous contents index
Next: Planar Convex-Hull Up: Examples Previous: String Searching



Our second example finds all the primes less than n. The algorithm is based on the sieve of Eratosthenes. The basic idea of the sieve is to find all the primes less than tex2html_wrap_inline9610 , and then use multiples of these primes to ``sieve out'' all the composite numbers less than n. Since all composite numbers less than n must have a divisor less than tex2html_wrap_inline9616 , the only elements left unsieved will be the primes. There are many parallel versions of the prime sieve, and several naive versions require a total of tex2html_wrap_inline9618 work and either tex2html_wrap_inline9620 or tex2html_wrap_inline9622 parallel time. A well designed version should require no more work than the serial sieve ( tex2html_wrap_inline9624 ), and polylogarithmic parallel time.

Figure: Finding all the primes less than n.

The version we use (see Figure 7) requires tex2html_wrap_inline9628 work and tex2html_wrap_inline9630 depth. It works by first recursively finding all the primes up to tex2html_wrap_inline9632 , (sqr_primes). Then, for each prime p in sqr_primes, the algorithm generates all the multiples of p up to n (sieves). This is done with the [s:e:d] construct. The sequence sieves is therefore a nested sequence with each subsequence being the sieve for one of the primes in sqr_primes. The function flatten, is now used to flatten this nested sequence by one level, therefore returning a sequence containing all the sieves. For example,

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 depth. Since primes is called recursively on a problem of size tex2html_wrap_inline9636 the total depth required by the algorithm can be written as the recurrence:


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


where p are the primes [24], the length of this sequence is:


therefore giving a work complexity of tex2html_wrap_inline9640 .

Figure 8: An example of the quickhull algorithm. Each sequence shows one step of the algorithm. Since A and P are the two x extrema, the line AP is the original split line. J and N are the farthest points in each subspace from AP and are, therefore, used for the next level of splits. The values outside the brackets are hull points that have already been found.

next up previous contents index
Next: Planar Convex-Hull Up: Examples Previous: String Searching

Jonathan Hardwick
Tue Nov 28 13:57:00 EST 1995