CIS-4230 Homework #6 (Prime Counting Function)

Due: Wednesday, May 9, 2018

  1. Write an MPI program that counts the number of prime numbers in a given range. Use the type unsigned long long (64 bits) to represent each value. This will allow you to explore very large ranges.

    The main program should work as follows: First accept an upper bound on the command line. Divide the range from one to that upper bound into continguous subranges with one subrange for each node. Use MPI_Scatter to send each node a description of the subrange it should process and MPI_Gather to collect the results from the nodes. Add all the counts together and output the result.

    Here is an example run of the MPI program:

              $ mpiexec -np 4 -host node1,node2,node3,node4 count_primes 12
              5
            

    The output is '5' because there are five prime numbers in the range 1 to 12 (namely 2, 3, 5, 7, and 11). In this MPI case, the node with rank 0 (node1) processed the values from 1 to 3, the node with rank 1 processed the values from 4 to 6, etc. Each node tests all of the values in its range for primality and counts the number of values it finds that are prime.

  2. Try running your program for very large ranges. How large a range can you process before the running time becomes uncomfortably long?

  3. Are communication costs asymptotically faster than computation costs for this application? Why is this an important question?

  4. There is an important function in number theory called the prime counting function. It is defined as pi(n) = x where x is the number of prime numbers less than or equal to n. The program you wrote for this assignment computes pi(n) exactly. It turns out that pi(n) can be approximated for large n using the simple formula n/ln(n). See the Wikipedia article on the prime counting function for more information. Pick a large value of n that you used in your test and compare the true result of pi(n) that you calculated with the approximate result n/ln(n). How close is the approximation?

To get you started with this program, here is how you might handle the command line.

      #include <stdio.h>
      #include <stdlib.h>

      int main( int argc, char **argv )
      {
        unsigned long long upper_bound;

        if( argc != 2 ) {
          fprintf( stderr, "Usage: %s upper_bound.\n", argv[0] );
          return EXIT_FAILURE;
        }
        upper_bound = atoll( argv[1] );
        if( upper_bound < 1 ) {
          fprintf( stderr, "Upper bound of %ld is invalid.\n", upper_bound );
          return EXIT_FAILURE;
        }

        // Continue...
      }