Lab46 Wiki

User Tools

Site Tools

You are here: start » haas » spring2017 » cprog » projects » pnc2
haas:spring2017:cprog:projects:pnc2

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Next revision		Previous revision
haas:spring2017:cprog:projects:pnc2 [2017/03/05 15:39] – created wedgehaas:spring2017:cprog:projects:pnc2 [2017/03/08 13:52] (current) – [Grabit Integration] wedge
Line 32: Line 32:
   * if you exceed 64 million and get "--error!---" that's okay. I have memory limits in place (just like I have time limits in place).   * if you exceed 64 million and get "--error!---" that's okay. I have memory limits in place (just like I have time limits in place).
   * if applicable, you can base your code on primebruteopt, but you may find the sieve algorithms to be different enough where you may not want to adapt existing code, but start fresh.   * if applicable, you can base your code on primebruteopt, but you may find the sieve algorithms to be different enough where you may not want to adapt existing code, but start fresh.
 +
 +====your own optimizations (primeopt)====
 +The first program to consider for this project offers you a chance to try out your own algorithm-optimizing skills. In both **pnc0** and **pnc1**, you implemented various approaches, often employing some very common sense improvements to the process.
 +
 +Here, I want you to take that knowledge you've gained, and combined with your own numerical fluency, attempt to hash out your own optimized algorithm for computing primes, plotting its time performance out against your other implementations.
 +
 +The **primerun** tool will recognize prime number calculating programs by the following names and process them accordingly:
 +
 +  * **primeopt**
 +  * **primeopt1**
 +  * **primeopt2**
 +  * **primeopt3**
 +  * **primeopt4**
 +
 +For credit, you only need to have ONE prime**opt** program... but these other slots are here should you wish to experiment.
 +
 +NOTE: this is to be an implementation different from the others.
 +
 +Compare your **primeopt** performance against that of the others to get a feel for how changes you make or implement impact overall runtime.
  
 ====sieve of Eratosthenes (primesieveoferat)==== ====sieve of Eratosthenes (primesieveoferat)====
-The first sieve we will be implementing will be one of the best known and likely longest-known sieves, the sieve of Eratosthenes.+The next program will be a sieve algorithm. We will be implementing one of the best known and likely longest-known sieves: the sieve of Eratosthenes.
  
 The sieve, instead of calculating to determine the eligibility of a prime, works in a manner of marking off patterns of values that cannot be prime (so, it is composite-focused in approach vs. prime-focused). The sieve, instead of calculating to determine the eligibility of a prime, works in a manner of marking off patterns of values that cannot be prime (so, it is composite-focused in approach vs. prime-focused).
Line 54: Line 73:
 ===Overview of Algorithm=== ===Overview of Algorithm===
  
-To find all the prime numbers less than or equal to a given integer n by Eratosthenes' method:+To find all the prime numbers less than or equal to a given integer **n** by Eratosthenes' method:
  
-  - Create a list of consecutive integers from 2 through n: (2, 3, 4, ..., n).+  - Create a list of consecutive integers from 2 through **n**: (2, 3, 4, ..., n).
   - Initially, let p equal 2, the smallest prime number.   - Initially, let p equal 2, the smallest prime number.
   - Enumerate the multiples of p by counting to n from 2p in increments of p, and mark them in the list (these will be 2p, 3p, 4p, ... ; the p itself should not be marked).   - Enumerate the multiples of p by counting to n from 2p in increments of p, and mark them in the list (these will be 2p, 3p, 4p, ... ; the p itself should not be marked).
   - Find the first number greater than p in the list that is not marked. If there was no such number, stop. Otherwise, let p now equal this new number (which is the next prime), and repeat from step 3.   - Find the first number greater than p in the list that is not marked. If there was no such number, stop. Otherwise, let p now equal this new number (which is the next prime), and repeat from step 3.
  
-When the algorithm terminates, the numbers remaining not marked in the list are all the primes below n.+When the algorithm terminates, the numbers remaining in the list that are not marked are the primes below **n**.
  
 ===Program Implementation=== ===Program Implementation===
-As this is a space-constrained algorithm, we will need a chunk of space to store these values. Think about what a lot of this looks like with respect to how you know how to organize data.+This is a space-constrained algorithm, therefore we will need a chunk of space to store these values. Think about what a lot of this looks like with respect to how you know how to organize data.
  
 ====sieve of Sundaram (primesieveofsund)==== ====sieve of Sundaram (primesieveofsund)====
Line 93: Line 112:
 It is your task to write some optimized prime number calculating programs: It is your task to write some optimized prime number calculating programs:
  
 +  - **primeopt.c**: implementing an approach of your own
   - **primesieveoferat.c**: using the space-oriented sieve algorithm   - **primesieveoferat.c**: using the space-oriented sieve algorithm
   - **primesieveofsund.c**: another sieve   - **primesieveofsund.c**: another sieve
Line 117: Line 137:
 <cli> <cli>
 lab46:~/src/cprog$ grabit cprog pnc2 lab46:~/src/cprog$ grabit cprog pnc2
-make: Entering directory '/var/public/fall2016/cprog/pnc2' +make: Entering directory '/var/public/spring2017/cprog/pnc2' 
-‘/var/public/fall2016/cprog/pnc2/Makefile’ -> ‘/home/USERNAME/src/cprog/pnc2/Makefile’ +‘/var/public/spring2017/cprog/pnc2/Makefile’ -> ‘/home/USERNAME/src/cprog/pnc2/Makefile’ 
-‘/var/public/fall2016/cprog/pnc2/primesieveoferat.c’ -> ‘/home/USERNAME/src/cprog/pnc2/primesieveoferat.c’ +‘/var/public/spring2017/cprog/pnc2/primeopt.c’ -> ‘/home/USERNAME/src/cprog/pnc2/primeopt.c’ 
-‘/var/public/fall2016/cprog/pnc2/primesieveofsund.c’ -> ‘/home/USERNAME/src/cprog/pnc2/primesieveofsund.c’ +‘/var/public/spring2017/cprog/pnc2/primesieveoferat.c’ -> ‘/home/USERNAME/src/cprog/pnc2/primesieveoferat.c’ 
-make: Leaving directory '/var/public/fall2016/cprog/pnc2'+‘/var/public/spring2017/cprog/pnc2/primesieveofsund.c’ -> ‘/home/USERNAME/src/cprog/pnc2/primesieveofsund.c’ 
 +make: Leaving directory '/var/public/spring2017/cprog/pnc2'
 lab46:~/src/cprog$ cd pnc2 lab46:~/src/cprog$ cd pnc2
 lab46:~/src/cprog/pnc2$ ls lab46:~/src/cprog/pnc2$ ls
-Makefile  primesieveoferat.c  primesieveofsund.c+Makefile  primeopt.c  primesieveoferat.c  primesieveofsund.c
 lab46:~/src/cprog/pnc2$  lab46:~/src/cprog/pnc2$ 
 </cli> </cli>
Line 297: Line 318:
   * Output must be correct, and match the form given in the sample output above.   * Output must be correct, and match the form given in the sample output above.
   * Code must be nicely and consistently indented (you may use the **indent** tool)   * Code must be nicely and consistently indented (you may use the **indent** tool)
-  * Code must utilize the algorithm(s) presented above.+  * Code must utilize the specifications/algorithm(s) presented above. 
 +    * **primeopt.c**
     * **primesieveoferat.c**     * **primesieveoferat.c**
     * **primesieveofsund.c**     * **primesieveofsund.c**
Line 311: Line 333:
  
 <cli> <cli>
-$ submit cprog pnc2 primesieveoferat.c primesieveofsund+$ submit cprog pnc2 primeopt.c primesieveoferat.c primesieveofsund
 Submitting cprog project "pnc2": Submitting cprog project "pnc2":
 +    -> primeopt.c(OK)
     -> primesieveoferat.c(OK)     -> primesieveoferat.c(OK)
     -> primesieveofsund.c(OK)     -> primesieveofsund.c(OK)
Line 320: Line 343:
  
 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. 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.
 +
 +What I will be looking for:
 +
 +<code>
 +52:pnc2:final tally of results (52/0)
 +*:pnc2:submit all programs with submit tool [1/0]
 +*:pnc2:primeopt.c no negative compiler messages [2/0]
 +*:pnc2:primeopt.c implements unique yet viable algorithm [4/0]
 +*:pnc2:primeopt.c adequate indentation and comments [3/0]
 +*:pnc2:primeopt.c output conforms to specifications [4/0]
 +*:pnc2:primeopt.c primerun runtime tests succeed [4/0]
 +*:pnc2:primesieveoferat.c no negative compiler messages [2/0]
 +*:pnc2:primesieveoferat.c implements only specified algorithm [4/0]
 +*:pnc2:primesieveoferat.c adequate indentation and comments [3/0]
 +*:pnc2:primesieveoferat.c output conforms to specifications [4/0]
 +*:pnc2:primesieveoferat.c primerun runtime tests succeed [4/0]
 +*:pnc2:primesieveofsund.c no negative compiler messages [2/0]
 +*:pnc2:primesieveofsund.c implements only specified algorithm [4/0]
 +*:pnc2:primesieveofsund.c adequate indentation and comments [3/0]
 +*:pnc2:primesieveofsund.c output conforms to specifications [4/0]
 +*:pnc2:primesieveofsund.c primerun runtime tests succeed [4/0]
 +</code>
haas/spring2017/cprog/projects/pnc2.1488728346.txt.gz · Last modified: 2017/03/05 15:39 by wedge

Page Tools

Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Share Alike 4.0 International
CC Attribution-Share Alike 4.0 International Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki