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:24] – [Submission] wedgehaas:spring2017:cprog:projects:pnc0 [2017/02/16 21:14] (current) – [brute force] wedge
Line 28: 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 63: 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 85: 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 91: 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 183: 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 277: Line 287:
 <code> <code>
 52:pnc0:final tally of results (52/52) 52:pnc0:final tally of results (52/52)
-*:pnc0:primebrute.c submitted with submit tool [4/4]+*:pnc0:primebrute.c submitted with submit tool [2/2]
 *:pnc0:primebrute.c no negative compiler messages [4/4] *:pnc0:primebrute.c no negative compiler messages [4/4]
-*:pnc0:primebrute.c implements only specified algorithm [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 output conforms to specifications [4/4]
 *:pnc0:primebrute.c primerun runtime tests succeed [6/6] *:pnc0:primebrute.c primerun runtime tests succeed [6/6]
-*:pnc0:primebrute.c adequate indentation and comments [4/4] +*:pnc0:primebruteopt.c submitted with submit tool [2/2]
-*:pnc0:primebruteopt.c submitted with submit tool [4/4]+
 *:pnc0:primebruteopt.c no negative compiler messages [4/4] *:pnc0:primebruteopt.c no negative compiler messages [4/4]
-*:pnc0:primebruteopt.c implements only specified algorithm [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 output conforms to specifications [4/4]
 *:pnc0:primebruteopt.c primerun runtime tests succeed [6/6] *:pnc0:primebruteopt.c primerun runtime tests succeed [6/6]
-*:pnc0:primebruteopt.c adequate indentation and comments [4/4] 
 </code> </code>
haas/spring2017/cprog/projects/pnc0.1486938265.txt.gz · Last modified: 2017/02/12 22:24 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