Table of Contents

Corning Community College

CSCS2330 Discrete Structures

PROJECT: Prime Number Computation (PNC2)

OBJECTIVE

After exploring the trial-by-division approach to prime number computation, we will now look at a fundamentally different approach, implementing the sieve of eratosthenes.

TASK

Implement program in Vircon32 C, that:

* bring over the trial-by-divison break on composite + odds only + sqrt variant from pnc1 to use as a basis for comparison. 

  * start at the upper end of the range processed by pnc1 so we have some basis for time comparison.
  * the sieve will potentially be more performant at higher bounds
  * the upper bound should be fairly easy to change, even if it requires an edit and recompile.
  * the values for N have some sufficient quantity large enough where its upper set values will take some amount of time to compute (fast enough to have some relatable value, not to exceed 16 seconds)
  * for each value of N:
  * display that N/upper bound
    * tally: display the number of primes identified (2-N)
    * display the amount of time taken to do the total computation for that value of N, out to at least 6 decimal places
    * display each N value and result in an arrangement on the screen that can be clearly identified and read by the viewer
* timing should go out, as reasonable, to a few decimal places, and should be consistent across all attempts.
  * timing is on the computational process only, not the display of results.
* create a graph (using some external tool) that plots the performance of the C implementation working on various workloads of these selected algorithms according to the various N's and the time it took. Share your graph of your results on the class discord and on the project documentation page.
  * a line graph is the suggested best candidate
* this will not be an interactive program: it starts up, does its thing, outputs it results, then halts.

REFERENCE

Here is an animated image of this sieve in action (from wikipedia):

EDIT

You will want to go here to edit and fill in the various sections of the document:

PNCX

ALGORITHM: sieve of eratosthenes

variant: baseline soe

The sieve of Eratosthenes is one of the best algorithms for finding prime numbers, you may have noticed that up to this point all the code we have written has a complexity of O(n^2). The soe takes the next step and goes to O(nlog(log(n)).

Here is how the Sieve of Eratosthenes works:

First, you start with 2, and count up to your upper bound. For this example, let's say it is 40: 

    2  3  4  5  6  7  8  9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40

Then, you go through the list and remove multiples of 2. After that, you go to the next remaining number, which you now know is prime. Then, you remove multiples of that number, and so on.

To continue from above, 2 is a prime number, so you leave it alone, and remove any multiples of 2: 

    2  3     5     7     9  
11    13    15    17    19  
21    23    25    27    29  
31    33    35    37    39

Then, you go to the next number: 3. Now you know 3 is a prime number, so you can remove multiples of 3: 

    2  3     5     7        
11    13          17    19  
      23    25          29  
31          35    37

You go through the entire list, and when you get to the end, you are only left with prime numbers: 

    2  3     5     7        
11    13          17    19  
      23                29  
31                37        
START TIMEKEEPING
NUMBER: FROM 2 THROUGH UPPERBOUND:
    SHOULD THE NUMBER SLOT BE TRUE:
        VALUE AT NUMBER IS PRIME, INCREMENT TALLY
        MULTIPLE: FROM NUMBER+NUMBER THROUGH UPPERBOUND:
            VALUE AT MULTIPLE IS NOT PRIME
            MULTIPLE IS MULTIPLE PLUS NUMBER
        PROCEED TO NEXT MULTIPLE
    INCREMENT NUMBER
PROCEED TO NEXT NUMBER
STOP TIMEKEEPING
variant: sieve of eratosthenes with sqrt trick (soes)
START TIMEKEEPING
NUMBER: FROM 2 THROUGH NUMBER*NUMBER<UPPERBOUND:
    SHOULD THE NUMBER SLOT BE TRUE:
        VALUE AT NUMBER IS PRIME, INCREMENT TALLY
        MULTIPLE: FROM NUMBER*NUMBER THROUGH UPPERBOUND:
            VALUE AT MULTIPLE IS NOT PRIME
            MULTIPLE IS MULTIPLE PLUS NUMBER
        PROCEED TO NEXT MULTIPLE
    INCREMENT NUMBER
PROCEED TO NEXT NUMBER
STOP TIMEKEEPING

timing

ChrisB's pnc2 runtimes

VerbalGnat48's pnc2 runtimes

Xavier's pnc2 runtimes

MrVengeance's pnc2 runtimes

Darkmoon's pnc2 runtimes

amelvil2's pnc2 runtimes

Blaize patricelli's pnc2 runtimes

 

SUBMISSION

To be successful in this project, the following criteria (or their equivalent) must be met:

Submit Tool Usage

Let's say you have completed work on the project, and are ready to submit, you would do the following: 

lab46:~/src/SEMESTER/DESIG/PROJECT$ submit DESIG PROJECT file1 file2 file3 ... fileN

You should get some sort of confirmation indicating successful submission if all went according to plan. If not, check for typos and or locational mismatches.

RUBRIC

I'll be evaluating the project based on the following criteria: 

234:pnc2:final tally of results (234/234)
*:pnc2:code, XML, build script, and cartridge submitted [26/26]
*:pnc2:processing and output is correct, and to specifications [26/26]
*:pnc2:tbd bos variant present and functional [26/26]
*:pnc2:sieve of eratosthenes present and functional [39/39]
*:pnc2:sqrt optimization of sieve of eratosthenes present and functional [39/39]
*:pnc2:graph produced from timing data produced of all 3 variants [26/26]
*:pnc2:graph posted to discord and documentation page [26/26]
*:pnc2:timing data is the taken out to at least 6 decimal places [26/26]

Pertaining to the collaborative authoring of project documentation

Additionally