Lab46 Wiki

User Tools

Site Tools

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

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:spring2017:cprog:projects:pnc0 [2017/02/12 22:07] – [Submission] wedgehaas:spring2017:cprog:projects:pnc0 [2017/02/16 21:14] (current) – [brute force] wedge
Line 1: Line 1:
 <WRAP centeralign round box> <WRAP centeralign round box>
 <WRAP><color red><fs 200%>Corning Community College</fs></color></WRAP> <WRAP><color red><fs 200%>Corning Community College</fs></color></WRAP>
-<WRAP><fs 150%>CSCS2330 Discrete Structures</fs></WRAP>+<WRAP><fs 150%>CSCS1320 C/C++ Programming</fs></WRAP>
 </WRAP> </WRAP>
  
Line 17: Line 17:
  
 The number **17** is a **prime** number, as no numbers other than 1 and 17 can be evenly divided. The number **17** is a **prime** number, as no numbers other than 1 and 17 can be evenly divided.
- 
-=====Caution===== 
-Some from last semester will recognize this project. Please take note that the specifications are not identical to the program from last semester! 
- 
  
 =====Calculating the primality of a number===== =====Calculating the primality of a number=====
Line 32: Line 28:
 The brute force approach is the simplest to implement (and likely also the worst-performing). We will use it as our baseline (it is nice to  have something to compare against). The brute force approach is the simplest to implement (and likely also the worst-performing). We will use it as our baseline (it is nice to  have something to compare against).
  
-To perform it, we simply attempt to evenly divide all the values between 1 and the number in question. If any one of them divides evenly, the number is **NOT** prime, but instead a composite value.+To perform it, we simply attempt to evenly divide all the values between 2 and one less than the number in question. If any one of them divides evenly, the number is **NOT** prime, but instead a composite value.
  
 Checking the remainder of a division indicates whether or not a division was clean (having 0 remainder indicates such a state). Checking the remainder of a division indicates whether or not a division was clean (having 0 remainder indicates such a state).
Line 67: Line 63:
 Even though you have identified the number as a composite, you MUST **CONTINUE** evaluating the remainder of the values (up to 119-1). It might seem pointless (and it is for a production program), but I want you to see the performance implications this creates. Even though you have identified the number as a composite, you MUST **CONTINUE** evaluating the remainder of the values (up to 119-1). It might seem pointless (and it is for a production program), but I want you to see the performance implications this creates.
  
 +===algorithm===
 +Some things to keep in mind on your implementation:
 +
 +  * loops, you will want to use loops for this. Especially these two brute force algorithms.
 +  * a nested loop makes the most sense.
 +  * you know the starting value and the terminating condition, so a clear starting and ending point. for() loops make the most sense.
 +  * let the loops drive the overall process. Identify prime/composite status separate from loop terminating conditions.
 +    * and remember, the baseline brute force algorithm may well identify a value as composite, but won't terminate the loop. The optimized brute force will act on the identification of a composite value by terminating the processing of additional values.
 +  * your timing should start before the loop, and terminate immediately following the terminating newline outside the loops.
 ====brute force optimization==== ====brute force optimization====
 The optimized version of brute force will make but one algorithmic change, and that takes place at the moment of identifying a number as composite. So, if we had our 119 example above, and discovered that 7 was a factor: The optimized version of brute force will make but one algorithmic change, and that takes place at the moment of identifying a number as composite. So, if we had our 119 example above, and discovered that 7 was a factor:
Line 89: Line 94:
   * perform the correct algorithm against the input   * perform the correct algorithm against the input
   * display (to STDOUT) the prime numbers found in the range   * display (to STDOUT) the prime numbers found in the range
 +  * stop your stopwatch. Calculate the time that has transpired.
   * output the processing run-time to STDERR   * output the processing run-time to STDERR
   * 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:   * 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:
Line 95: Line 101:
  
 =====Command-Line Arguments===== =====Command-Line Arguments=====
-To automate our comparisons, we will be making use of command-line arguments in our programs. As we have yet to really get into arrays, I will provide you same code that you can use that will allow you to utilize them for the purposes of this project.+To automate our comparisons, we will be making use of command-line arguments in our programs. As we have yet to really get into arrays, I will provide you some code that you can use that will allow you to utilize them for the purposes of this project.
  
 ====header files==== ====header files====
Line 187: Line 193:
  
 ====Displaying the runtime==== ====Displaying the runtime====
-Once we having the starting and ending times, we can display this to STDERR. You'll want this line:+Once we have the starting and ending times, we can display this to STDERR. You'll want this line:
  
 <code c> <code c>
Line 202: Line 208:
  
 <cli> <cli>
-lab46:~/src/sysprog/pnc0$ ./primebrute 90+lab46:~/src/cprog/pnc0$ ./primebrute 90
 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 
   0.000088   0.000088
-lab46:~/src/sysprog/pnc0$ +lab46:~/src/cprog/pnc0$ 
 </cli> </cli>
  
Line 218: Line 224:
  
 <cli> <cli>
-lab46:~/src/discrete/pnc0$ primerun+lab46:~/src/cprog/pnc0$ primerun
 =================================== ===================================
     range        brute     bruteopt     range        brute     bruteopt
Line 237: Line 243:
  verify:       OK           OK  verify:       OK           OK
 =================================== ===================================
-lab46:~/src/discrete/pnc0$ +lab46:~/src/cprog/pnc0$ 
 </cli> </cli>
  
Line 276: Line 282:
  
 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:pnc0:final tally of results (52/52)
 +*:pnc0:primebrute.c submitted with submit tool [2/2]
 +*:pnc0:primebrute.c no negative compiler messages [4/4]
 +*:pnc0:primebrute.c implements only specified algorithm [6/6]
 +*:pnc0:primebrute.c adequate indentation and comments [4/4]
 +*:pnc0:primebrute.c output conforms to specifications [4/4]
 +*:pnc0:primebrute.c primerun runtime tests succeed [6/6]
 +*:pnc0:primebruteopt.c submitted with submit tool [2/2]
 +*:pnc0:primebruteopt.c no negative compiler messages [4/4]
 +*:pnc0:primebruteopt.c implements only specified algorithm [6/6]
 +*:pnc0:primebruteopt.c adequate indentation and comments [4/4]
 +*:pnc0:primebruteopt.c output conforms to specifications [4/4]
 +*:pnc0:primebruteopt.c primerun runtime tests succeed [6/6]
 +</code>
haas/spring2017/cprog/projects/pnc0.1486937245.txt.gz · Last modified: 2017/02/12 22:07 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