haas:spring2017:cprog:projects:pnc0
Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
| haas:spring2017:cprog:projects:pnc0 [2017/02/12 22:25] – [Submission] wedge | haas: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 | + | To perform it, we simply attempt to evenly divide all the values between |
| 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/ | ||
| + | * 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, | + | To automate our comparisons, |
| ====header files==== | ====header files==== | ||
| Line 183: | Line 193: | ||
| ====Displaying the runtime==== | ====Displaying the runtime==== | ||
| - | Once we having | + | Once we have the starting and ending times, we can display this to STDERR. You'll want this line: |
| <code c> | <code c> | ||
haas/spring2017/cprog/projects/pnc0.1486938359.txt.gz · Last modified: 2017/02/12 22:25 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
