Lab46 Wiki

User Tools

Site Tools

You are here: start » haas » summer2017 » cprog » projects » pnc1
haas:summer2017:cprog:projects:pnc1

Differences

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

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision		Previous revision
haas:summer2017:cprog:projects:pnc1 [2017/06/19 15:10] – [Grabit Integration] wedgehaas:summer2017:cprog:projects:pnc1 [2017/06/19 15:41] (current) – [Submission] wedge
Line 26: Line 26:
 Some optimizations can be the result of sheer common sense observations. For instance, with the exception of 2, all primes are odd numbers. Some optimizations can be the result of sheer common sense observations. For instance, with the exception of 2, all primes are odd numbers.
  
-So does it make sense to check an even number for primality? Hopefully you can see that: no, it doesn't.+So does it make sense to check an even number for primality? Hopefully you can see that no, it doesn't.
  
 And can we predict even numbers? Yes, we can: they occur every other number. And can we predict even numbers? Yes, we can: they occur every other number.
Line 70: Line 70:
 This program should be an optimization based on your **primebrk** program from pnc0. This program should be an optimization based on your **primebrk** program from pnc0.
  
-====sqrt() + odds (primebrksrtodd)====+====sqrt() + odds (primebrkoddsrt)====
 In the previous program we used **sqrt()** against all the values, even or odd. In the previous program we used **sqrt()** against all the values, even or odd.
  
Line 101: Line 101:
 </cli> </cli>
  
-Square root of 81 is 9, but so is the square root of 82, 83, 84... etc. up until we hit 100.+Or, if perhaps we instead order by square root value:
  
-If we were checking 87 to be prime, we'd only have to check up to 9.+<cli> 
 +lab46:~$ oldsqrt=$(echo "sqrt(2)" | bc -q); for ((i=2; i<49; i++)); do newsqrt=$(echo "sqrt($i)" | bc -q); if [ "${newsqrt}" -ne "${oldsqrt}" ]; then echo; fi; printf "[%3d] %2d " "${i}" "${newsqrt}"; oldsqrt="${newsqrt}"; done; echo 
 +[  2]  1 [  3]  1 
 +[  4]  2 [  5]  2 [  6]  2 [  7]  2 [  8]  2 
 +[  9]  3 [ 10]  3 [ 11]  3 [ 12]  3 [ 13]  3 [ 14]  3 [ 15]  3 
 +[ 16]  4 [ 17]  4 [ 18]  4 [ 19]  4 [ 20]  4 [ 21]  4 [ 22]  4 [ 23]  4 [ 24]  4 
 +[ 25]  5 [ 26]  5 [ 27]  5 [ 28]  5 [ 29]  5 [ 30]  5 [ 31]  5 [ 32]  5 [ 33]  5 [ 34]  5 [ 35]  5 
 +[ 36]  6 [ 37]  6 [ 38]  6 [ 39]  6 [ 40]  6 [ 41]  6 [ 42]  6 [ 43]  6 [ 44]  6 [ 45]  6 [ 46]  6 [ 47]  6 [ 48]  6 
 +</cli> 
 + 
 +We see that the square root of 36 is 6, but so is the square root of 37, 38, 39... etc. up until we hit 49 (where the whole number square root increments to 7). 
 + 
 +Therefore, if we were checking 42 to be prime, we'd only have to check up to 6.
  
 We don't need a **sqrt()** function to tell us this, we can determine the approximate square root point ourselves- by squaring the current factor being tested, and so long as it hasn't exceeded the value we're checking, we know to continue. We don't need a **sqrt()** function to tell us this, we can determine the approximate square root point ourselves- by squaring the current factor being tested, and so long as it hasn't exceeded the value we're checking, we know to continue.
Line 134: Line 146:
  
 Your program should: Your program should:
-  * obtain 1 parameter from the command-line (see **command-line arguments** section below): +  * obtain 2-4 parameters from the command-line (see **command-line arguments** section below). 
-    * argv[1]: maximum value to calculate to (your program should run from (approximately) 2 through that number (inclusive of that number) +    * check to make sure the user indeed supplied enough parameters, and exit with an error message if not. 
-    * this value should be a positive integer value; you can make the assumption that the user will always do the right thing. +    * argv[1]: maximum quantity of primes to calculate (your program should run until it discovers **that** many primes). 
-  * do the specified algorithmic optimizations +      * this value should be an integer value, greater than or equal to 0. 
-    * please take note in differences in run-time, contemplating the impact the various algorithms and approaches have on performance. +        * if argv[1] is 0, disable the quantity check, and rely on provided lower and upper bounds (argv[4] would be required in this case). 
-  * start your stopwatch (see **timing** section below): +    * argv[2]: reserved for future compatibility; for now, assume it is **1**. 
-  * perform the correct algorithm against the input +    * argv[3]: **conditionally optional** lower bound (starting value). Most of the time, this will probably be **2**, but should be a positive integer greater than or equal to 2. This defines where you program will start its prime quantity check from. 
-  * display (to STDOUT) the prime numbers found in the range +      * if omitted, assume a lower bound of **2**. 
-  * output the processing run-time to STDERR +      * if you desired to specify an upper bound (argv[4]), you obviously MUST provide the lower bound argument under this scheme. 
-  * your output **MUST** be conformant to the example output in the **execution** section below. This is also a test to see how well you can implement to specifications. Basically:+    * argv[4]: **conditionally optional** upper bound (ending value). If provided, this is the ending value you'd like to check to. 
 +      * If doing a quantity run (argv[1] NOT 0), this value isn't necessary. 
 +      * If doing a quantity run AND you specify an upper bound, whichever condition is achieved first dictates program termination. That is, upper bound could override quantity (if it is achieved before quantity), and quantity can override the upper bound (if it is achieved before reaching the specified upper bound). 
 +    * for each argument: you should do a basic check to ensure the user complied with this specification, and exit with a unique error message (displayed to STDERR) otherwise: 
 +      * for insufficient quantity of arguments, display: **PROGRAM_NAME: insufficient number of arguments!** 
 +      * for invalid argv[1], display: **PROGRAM_NAME: invalid quantity!** 
 +      * for invalid argv[2], display: **PROGRAM_NAME: invalid value!** 
 +      * for invalid argv[3], display: **PROGRAM_NAME: invalid lower bound!** 
 +        * if argv[3] is not needed, ignore (no error displayed not forced exit, as it is acceptable defined behavior). 
 +      * for invalid argv[4], display: **PROGRAM_NAME: invalid upper bound!** 
 +        * if argv[4] is not needed, ignore (no error displayed nor forced exit, as it is acceptable defined behavior). 
 +      * In these error messages, **PROGRAM_NAME** is the name of the program being run; this can be accessed as a string stored in **argv[0]**. 
 +    * please take note in differences in run-time, contemplating the impact the various algorithms/optimizations have on performance. 
 +  * start your stopwatch (see **timing** section below). 
 +  * perform the correct algorithm against the input(s) given. 
 +  * display to STDOUT (file pointer **stdout**) the prime numbers calculated. 
 +  * stop your stopwatch. Calculate the time that has transpired (ending time minus starting time). 
 +  * a further coding restriction: in each program, you are not allowed to use a given loop type (for(), while(), do-while()) more than once! If you find you need more than one loop in a program, they **CANNOT** be the same type (this is to get you exposed to them and thinking differently). 
 +  * output the processing run-time to STDERR (file pointer **stderr**). 
 +  * your output **MUST** conform to the example output in the **execution** section below. This is also a test to see how well you can implement to specifications. Basically:
     * as primes are being displayed, they are space-separated (first prime hugs the left margin), and when all said and done, a newline is issued.     * as primes are being displayed, they are space-separated (first prime hugs the left margin), and when all said and done, a newline is issued.
-    * the timing information will be displayed in accordance to code I will provide (in the **timing** section). +    * the timing information will be displayed in accordance to code I will provide below (see the **timing** section).
 =====Grabit Integration===== =====Grabit Integration=====
 For those familiar with the **grabit** tool on lab46, I have made some skeleton files and a custom **Makefile** available for this project. For those familiar with the **grabit** tool on lab46, I have made some skeleton files and a custom **Makefile** available for this project.
Line 296: Line 326:
  
 <cli> <cli>
-lab46:~/src/cprog/pnc1$ ./primesqrt 90 +lab46:~/src/cprog/pnc1$ ./primebrkodd 32 1 
-2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89  +2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 
-  0.000088+  0.000133
 lab46:~/src/cprog/pnc1$  lab46:~/src/cprog/pnc1$ 
 </cli> </cli>
  
 The execution of the programs is short and simple- grab the parameters, do the processing, produce the output, and then terminate. The execution of the programs is short and simple- grab the parameters, do the processing, produce the output, and then terminate.
- 
 =====Check Results===== =====Check Results=====
 If you'd like to compare your implementations, I rigged up a script called **primerun** which you can run. If you'd like to compare your implementations, I rigged up a script called **primerun** which you can run.
Line 343: Line 372:
 I also include a validation check- to ensure your prime programs are actually producing the correct list of prime numbers. If the check is successful, you will see "OK" displayed beneath in the appropriate column; if unsuccessful, you will see "MISMATCH". I also include a validation check- to ensure your prime programs are actually producing the correct list of prime numbers. If the check is successful, you will see "OK" displayed beneath in the appropriate column; if unsuccessful, you will see "MISMATCH".
  
 +Analyze the times you see... do they make sense, especially when comparing the algorithm used and the quantity being processed? These are related to some very important core Computer Science considerations we need to be increasingly mindful of as we design our programs and implement our solutions. Algorithmic complexity and algorithmic efficiency will be common themes in all we do.
 =====Submission===== =====Submission=====
 To successfully complete this project, the following criteria must be met: To successfully complete this project, the following criteria must be met:
Line 350: Line 380:
   * 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 algorithm(s) presented above.
-    * **primeodds.c** +    * **primebrkodd.c** 
-    * **primesqrt.c** +    * **primebrksrt.c** 
-    * **primesqrtodds.c** +    * **primebrkoddsrt.c** 
-    * **primesqrtopt.c** +    * **primebrksrtopt.c** 
-    * **primesqrtoptodds.c**+    * **primebrkoddsrtopt.c**
   * Code must be commented   * Code must be commented
     * have a properly filled-out comment banner at the top     * have a properly filled-out comment banner at the top
Line 366: Line 396:
  
 <cli> <cli>
-$ submit cprog pnc1 primeodds.c primesqrt.c primesqrtodds.c primesqrtopt.c primesqrtoptodds.c+$ submit cprog pnc1 primebrkodd.c primebrksrt.c primebrkoddsrt.c primebrksrtopt.c primebrkoddsrtopt.c
 Submitting cprog project "pnc1": Submitting cprog project "pnc1":
-    -> primeodds.c(OK) +    -> primebrkodd.c(OK) 
-    -> primesqrt.c(OK) +    -> primebrksrt.c(OK) 
-    -> primesqrtodds.c(OK) +    -> primebrkoddsrt.c(OK) 
-    -> primesqrtopt.c(OK) +    -> primebrksrtopt.c(OK) 
-    -> primesqrtoptodds.c(OK)+    -> primebrkoddsrtopt.c(OK)
  
 SUCCESSFULLY SUBMITTED SUCCESSFULLY SUBMITTED
Line 383: Line 413:
 <code> <code>
 78:pnc1:final tally of results (78/78) 78:pnc1:final tally of results (78/78)
-*:pnc1:submit all programs correctly named using submit tool [3/3] +*:pnc1:submit all programs correctly perform argument checking [3/3] 
-*:pnc1:primeodds.c no negative compiler messages [2/2] +*:pnc1:primebrkodd.c no negative compiler messages [2/2] 
-*:pnc1:primeodds.c implements only specified algorithm [4/4] +*:pnc1:primebrkodd.c implements only specified algorithm [4/4] 
-*:pnc1:primeodds.c adequate indentation and comments [3/3] +*:pnc1:primebrkodd.c adequate indentation and comments [3/3] 
-*:pnc1:primeodds.c output conforms to specifications [3/3] +*:pnc1:primebrkodd.c output conforms to specifications [3/3] 
-*:pnc1:primeodds.c primerun runtime tests succeed [3/3] +*:pnc1:primebrkodd.c primerun runtime tests succeed [3/3] 
-*:pnc1:primesqrt.c no negative compiler messages [2/2] +*:pnc1:primebrksrt.c no negative compiler messages [2/2] 
-*:pnc1:primesqrt.c implements only specified algorithm [4/4] +*:pnc1:primebrksrt.c implements only specified algorithm [4/4] 
-*:pnc1:primesqrt.c adequate indentation and comments [3/3] +*:pnc1:primebrksrt.c adequate indentation and comments [3/3] 
-*:pnc1:primesqrt.c output conforms to specifications [3/3] +*:pnc1:primebrksrt.c output conforms to specifications [3/3] 
-*:pnc1:primesqrt.c primerun runtime tests succeed [3/3] +*:pnc1:primebrksrt.c primerun runtime tests succeed [3/3] 
-*:pnc1:primesqrtodds.c no negative compiler messages [2/2] +*:pnc1:primebrkoddsrt.c no negative compiler messages [2/2] 
-*:pnc1:primesqrtodds.c implements only specified algorithm [4/4] +*:pnc1:primebrkoddsrt.c implements only specified algorithm [4/4] 
-*:pnc1:primesqrtodds.c adequate indentation and comments [3/3] +*:pnc1:primebrkoddsrt.c adequate indentation and comments [3/3] 
-*:pnc1:primesqrtodds.c output conforms to specifications [3/3] +*:pnc1:primebrkoddsrt.c output conforms to specifications [3/3] 
-*:pnc1:primesqrtodds.c primerun runtime tests succeed [3/3] +*:pnc1:primebrkoddsrt.c primerun runtime tests succeed [3/3] 
-*:pnc1:primesqrtopt.c no negative compiler messages [2/2] +*:pnc1:primebrksrtopt.c no negative compiler messages [2/2] 
-*:pnc1:primesqrtopt.c implements only specified algorithm [4/4] +*:pnc1:primebrksrtopt.c implements only specified algorithm [4/4] 
-*:pnc1:primesqrtopt.c adequate indentation and comments [3/3] +*:pnc1:primebrksrtopt.c adequate indentation and comments [3/3] 
-*:pnc1:primesqrtopt.c output conforms to specifications [3/3] +*:pnc1:primebrksrtopt.c output conforms to specifications [3/3] 
-*:pnc1:primesqrtopt.c primerun runtime tests succeed [3/3] +*:pnc1:primebrksrtopt.c primerun runtime tests succeed [3/3] 
-*:pnc1:primesqrtoptodds.c no negative compiler messages [2/2] +*:pnc1:primebrkoddsrtopt.c no negative compiler messages [2/2] 
-*:pnc1:primesqrtoptodds.c implements only specified algorithm [4/4] +*:pnc1:primebrkoddsrtopt.c implements only specified algorithm [4/4] 
-*:pnc1:primesqrtoptodds.c adequate indentation and comments [3/3] +*:pnc1:primebrkoddsrtopt.c adequate indentation and comments [3/3] 
-*:pnc1:primesqrtoptodds.c output conforms to specifications [3/3] +*:pnc1:primebrkoddsrtopt.c output conforms to specifications [3/3] 
-*:pnc1:primesqrtoptodds.c primerun runtime tests succeed [3/3]+*:pnc1:primebrkoddsrtopt.c primerun runtime tests succeed [3/3]
 </code> </code>
  
haas/summer2017/cprog/projects/pnc1.1497885041.txt.gz · Last modified: 2017/06/19 15:10 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