CIS-3012 Homework #6: Concurrency

Due: Friday, December 15, 2023

This assignment is extra credit and worth 10 points (instead of the usual 20).

Reading: Finish me!

The Sieve of Eratosthenes is a method for finding prime numbers. It entails creating an array of bool, initially all true, and then "checking off" numbers that can't be prime leaving behind only the numbers that are prime. The Wikipedia article on the method has a nice animation that shows how it works. Implementations in various languages (including C and C++) are on this page on the Geeks for Geeks website. For this assignment, feel free to use one of those implementations, possibly adjusted (but make a note in your program if you do).

For this assignment, be sure you create the array as a global variable. We need to do this because we will want to make it large, and large local arrays tend to cause stack overflows. We will also want multiple threads to access it, which requires that it be visible to all threads (i.e., not a local variable).

Part 1

Write a function that computes all primes between 2 and 1,000,000,000 using the Sieve of Eratosthenes (feel free to use an implementation you find online, just be sure to provide a reference). Also write a function that counts the number of primes found by going through the array and counting the number of elements that are true.
Write a program that executes both of the functions you created above, to display the number of primes between 2 and 1,000,000,000. You might want to adjust the upper bound depending on the speed of your computer and its available memory. You want the computation to take several seconds, but not an unreasonable length of time.
Next, run the sieving function in its own thread while the main thread prints a dot every second as feedback to the user. To do this, I suggest using a different approach for creating the thread than what was discussed in class. In particular, I suggest using a future. The code looks like this:
```
      #include <chrono>
      #include <future>
      ...
      std::future<void> result = std::async( std::launch::async, SieveOfEratosthenes );
      while( result.wait_for( std::chrono::seconds( 1 ) ) != std::future_status::ready ) {
          std::cout << "." << std::flush;
      }
      std::cout << std::endl;
    
```
This code starts the function SieveOfEratosthenes asynchronously (i.e., in its own thread) and stores the value returned by the function in the future result. In this case, the function returns void, but we can still use the future to coordinate other parts of the program with the execution of the sieve. In particular, the while loop will wait one second for the result to be ready. If it is not, the loop will print a dot, and then wait another second. The effect is that you will see a series of dots, one second apart, while the computation is being done in a separate thread.

If you want to check if your program is computing the right number, consult the Wikipedia page on the prime counting function. It gives a table of the number of primes less than or equal to various large values. The first column of the table, under the heading π(x), is the exact answer.

Submission

Submit your program to Canvas. You do not need to submit (or even use) a Makefile.