Lab46 Wiki

User Tools

Site Tools

You are here: start » haas » spring2016 » cprog » projects » pnc0
haas:spring2016: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:spring2016:cprog:projects:pnc0 [2016/02/22 18:59] – [Bonus Points] wedgehaas:spring2016:cprog:projects:pnc0 [2016/02/27 13:13] (current) – [Program] wedge
Line 17: Line 17:
   * ability to iterate sections of code (for/while statement)   * ability to iterate sections of code (for/while statement)
  
 +=====Algorithmic Complexity=====
 +A concept in Computer Science curriculum is the notion of computational/algorithmic complexity.
 +
 +Basically, a solution to a problem exists on a spectrum of efficiency (typically constrained by time vs. space): if optimizing for time, the code size tends to grow.
 +
 +Additionally, if optimizing for time (specifically to reduce the amount of time taken), strategic approaches are taken to reduce unnecessary or redundant operations (yet still achieving the desired end results).
 +
 +This project will endeavor to introduce you to the notion that the algorithms and constructs you use in coding your solution can and do make a difference to the overall runtime of your code.
 =====Background===== =====Background=====
 In mathematics, a **prime** number is a value that is only evenly divisible by 1 and itself; it has no other factors. Numbers that have divisibility/factors are known as **composite** numbers. In mathematics, a **prime** number is a value that is only evenly divisible by 1 and itself; it has no other factors. Numbers that have divisibility/factors are known as **composite** numbers.
Line 109: Line 117:
  
 One assumption I will allow you to make for your optimized solution is that the single-digit primes (2, 3, 5, 7) can be assumed prime, and just printed out if having them be calculated would otherwise break your algorithm (might be helpful to some people; I certainly found it useful in some of my solutions). One assumption I will allow you to make for your optimized solution is that the single-digit primes (2, 3, 5, 7) can be assumed prime, and just printed out if having them be calculated would otherwise break your algorithm (might be helpful to some people; I certainly found it useful in some of my solutions).
 +
 +===some optimization ideas===
 +  * [[https://primes.utm.edu/notes/faq/six.html|Prime patterns of 6]]
 +  * [[https://lab46.g7n.org/~wedge/php/web.php?width=800&height=600&div=6&max=145&prime=1&factor=0&spiral=0|Visualization of Primes in a web of 6 divisions]]
 +  * [[https://lab46.g7n.org/~wedge/php/web.php?width=800&height=600&div=12&max=145&prime=1&factor=0&spiral=0|Visualization of Primes in a web of 12 divisions]]
 +  * [[https://en.wikipedia.org/wiki/Ulam_spiral|Ulam spiral]]
 +  * [[https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes|Sieve of Eratosthenes]]
 +
 +Of particular note: the sieve algorithms take advantage of a increased storage space, where others (like brute force) are predominantly time-based. The sieve is also more detailed... even if you don't decide to implement a sieve, take a look and compare the algorithm to what you've done to see the differences in approaches.
 =====Program===== =====Program=====
 It is your task to write 3 separate prime number calculating programs: It is your task to write 3 separate prime number calculating programs:
  
-  - primebrute.c: for your brute force implementation +  - **primebrute.c**: for your brute force implementation 
-  - primesqrt.c: for your square root-optimization of the brute force +  - **primesqrt.c**: for your square root-optimization of the brute force 
-  - primeopt.c: for your optimized solution, be it basing off the existing ones, or taking a different approach+  - **primeopt.c**: for your optimized solution, be it basing off the existing ones, or taking a different approach
  
 Your program should: Your program should:
Line 122: Line 139:
     * these values should be positive integer values; you can make the assumption that the user will always do the right thing.     * these values should be positive integer values; you can make the assumption that the user will always do the right thing.
   * start your stopwatch (see **timing** section below):   * start your stopwatch (see **timing** section below):
-  * perform the correct algorithm against the input+  * perform the algorithm against the value
   * if enabled, display the prime numbers found in the range   * if enabled, display the prime numbers found in the range
   * output the processing run-time to STDERR (do this always).   * output the processing run-time to STDERR (do this always).
Line 129: Line 146:
     * 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 (in the **timing** section).
  
 +====Other considerations====
 +All your programs MUST perform the calculations to determine primality- you may not always be printing it out (depending on argv[2]), but work must be done to ensure the value is identified as a prime/composite value.
 +
 +For example:
 +
 +<code>
 +if (show == 1)
 +{
 + work to determine if it is prime
 + if prime
 + print number
 +}
 +</code>
 +
 +will actually skip the core processing, and you’ll see some amazing runtimes as a result. They may be amazing, but they’re not real, because you’re not actually doing anything.
 +
 +What you want instead:
 +
 +<code>
 +work to determine if it is prime
 +if (show == 1)
 +{
 + if prime
 + print number
 +}
 +</code>
 +
 +there are many ways to express the above, through compound if statements and other arrangements, but notice how nothing is holding back “work to determine if it is prime”.
 +
 +That also isn’t to say you can’t avoid doing a work run if you’re able to determine its non-primality with a simple pretest (even value, factor of 3, etc.), but that’s actually considered more of the core “work”, so it is more than okay (and encouraged in the primeopt).
 =====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 same code that you can use that will allow you to utilize them for the purposes of this project.
Line 290: Line 337:
  
 <cli> <cli>
-lab46:~/src/prime$ primerun +lab46:~/src/cprog/pnc0$ primerun
-   range       brute        sqrt         opt+
 ============================================ ============================================
-       8    0.000002    0.000009    0.000001 +   range       brute        sqrt         opt  
-      16    0.000002    0.000003    0.000002 +============================================ 
-      32    0.000003    0.000007    0.000002 +       8    0.000002    0.000002    0.000002   
-      64    0.000005    0.000006    0.000002 +      16    0.000002    0.000002    0.000002   
-     128    0.000012    0.000008    0.000003 +      32    0.000003    0.000004    0.000002   
-     256    0.000038    0.000027    0.000006 +      64    0.000005    0.000020    0.000003   
-     512    0.000178    0.000036    0.000012 +     128    0.000012    0.000023    0.000003   
-    1024    0.000540    0.000081    0.000028 +     256    0.000037    0.000029    0.000006   
-    2048    0.001779    0.000190    0.000066 +     512    0.000165    0.000036    0.000014   
-    4096    0.006087    0.000448    0.000163 +    1024    0.000540    0.000080    0.000033   
-    8192    0.021272    0.001037    0.000414 +    2048    0.001761    0.000187    0.000078   
-   16384    0.077553    0.002529    0.001028 +    4096    0.006115    0.000438    0.000189   
-   32768    0.281896    0.006146    0.002621 +    8192    0.021259    0.001036    0.000458   
-   65536    1.046907    0.015268    0.006740 +   16384    0.077184    0.002520    0.001153   
-  131072    5.160277    0.045539    0.020873 +   32768    0.281958    0.006156    0.002826   
-  262144   18.302749    0.119166    0.055821+   65536    1.046501    0.015234    0.007135   
 +  131072    5.160141    0.045482    0.021810   
 +  262144    --------    0.119042    0.057520   
 +  524288    --------    0.301531    0.146561   
 + 1048576    --------    0.758027    0.370700   
 + 2097152    --------    1.921014    0.943986   
 + 4194304    --------    4.914725    2.423202   
 + 8388608    --------    --------    --------   
 +============================================ 
 + verify:       OK          OK          OK     
 ============================================ ============================================
 lab46:~/src/cprog/pnc0$  lab46:~/src/cprog/pnc0$ 
 </cli> </cli>
  
 +For evaluation, each test is run 4 times, and the resulting time is averaged. During development, I have it set to only run each test once.
 +
 +If the runtime of a particular prime variant exceeds an upper threshold (likely to be set at 2 seconds), it will be omitted from further tests, and a series of dashes will instead appear in the output.
 +
 +If you don't feel like waiting, simply hit **CTRL-c** and the script will terminate.
 +
 +In the example output above, my **primeopt** is playing with an implementation of the **6a+/-1** algorithm.
 +
 +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 be "MISMATCH".
 +
 +If you'd like to experiment with other variations, the script also recognizes prime variants of the following names:
 +  * primeopt0 (for an additional optimization)
 +  * primeopt1 (and another)
 +  * primeopt2 (if you'd like another entry for another optimization)
 +  * primeopt3 (for yet another optimization)
 +  * primeopt4 (and one more; hey, I want you to have nice things)
 =====Bonus Points===== =====Bonus Points=====
 There will be an additional bonus point opportunity with this project, based on processing run-time of your optimized solution. There will be an additional bonus point opportunity with this project, based on processing run-time of your optimized solution.
haas/spring2016/cprog/projects/pnc0.1456167565.txt.gz · Last modified: 2016/02/22 18:59 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