Lab46 Wiki

User Tools

Site Tools

You are here: start » haas » fall2017 » cprog » projects » pnc0
haas:fall2017: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:fall2017:cprog:projects:pnc0 [2017/09/24 16:44] – wedgehaas:fall2017:cprog:projects:pnc0 [2017/10/15 20:51] (current) – [Evaluation Criteria] wedge
Line 3: Line 3:
 <WRAP><fs 150%>CSCS1320 C/C++ Programming</fs></WRAP> <WRAP><fs 150%>CSCS1320 C/C++ Programming</fs></WRAP>
 </WRAP> </WRAP>
- 
-~~TOC~~ 
  
 ======Project: ALGORITHMS - PRIME NUMBER CALCULATION (pnc0)====== ======Project: ALGORITHMS - PRIME NUMBER CALCULATION (pnc0)======
Line 91: Line 89:
       * an inner loop that tests that current number to see if it has any factors       * an inner loop that tests that current number to see if it has any factors
   * you know the starting value and the terminating condition, so you have a clear starting and ending point to work with.   * you know the starting value and the terminating condition, so you have a clear starting and ending point to work with.
-  * I want you to use two **DIFFERENT** kind of loops in your programs. If you use a **for()** loop in your outer loop, I want you to use a **while()** or **do-while()** loop in your inner loop (and whatever combination you end up with). 
   * I do **NOT** want to see ambiguous, one-letter variables used in your implementation(s). Please use //meaningful// variable names.   * I do **NOT** want to see ambiguous, one-letter variables used in your implementation(s). Please use //meaningful// variable names.
     * Some good examples of variable names would be:     * Some good examples of variable names would be:
Line 106: Line 103:
     * and remember, the baseline brute force algorithm (**primereg**) may well identify a value as composite, but won't terminate the loop.     * and remember, the baseline brute force algorithm (**primereg**) may well identify a value as composite, but won't terminate the loop.
   * your timing should start before the loop (just AFTER argument processing), and terminate immediately following the terminating output newline outside the loops.   * your timing should start before the loop (just AFTER argument processing), and terminate immediately following the terminating output newline outside the loops.
-  * you may **NOT** split **qty** and **range** functionality into two separate code blocks (ie have two sets of two loops). Only the one set as indicated.  
-=====prime algorithm optimizations===== 
-To give us a decent appreciation of the subtleties of algorithm development in a theme of programs, I have identified the following optimizations that we will be implementing. 
  
-For simplicity, I have encoded this information in the file name (and therefore resulting executable/binary) that will correspond to the indicated algorithm+optimizations.+=====prime algorithm implementation===== 
 +For simplicity, I have encoded important implementation information into the file name (and therefore resulting executable/binary) that will correspond to the indicated algorithm plus any optimizations.
  
 To break it down, all prime programs will be of the form: To break it down, all prime programs will be of the form:
Line 117: Line 112:
     * is immediately followed by a 3-letter (lowercase) abbreviation of the algorithm to be implemented (**reg**, for instance)     * is immediately followed by a 3-letter (lowercase) abbreviation of the algorithm to be implemented (**reg**, for instance)
     * and then is followed by 0 or more layered attributes describing the particular optimization that is applied (again, if any: **zero** or more).     * and then is followed by 0 or more layered attributes describing the particular optimization that is applied (again, if any: **zero** or more).
- 
-The optimizations we will be implementing in this project (and their naming values) include: 
-  * **break on composite (b)** - once a tested number is proven composite, there is no need to continue processing: break out of the factor loop and proceed to the next number 
-  * **mapping factors of 6 (m)** - it turns out that, aside from the initial primes of **2** and **3**, that **all** prime numbers fall to a +1 or -1 off a factor of six (there is an algorithm for this: **6a+/-1**). This optimization will utilize this property, only testing numbers +/-1 off of factors of 6 (how might this impact overall processing?) 
-  * **odds-only checking (o)** - aside from **2**, **all** other prime numbers are odd. Therefore, there is zero need to perform a composite check on an even number, allowing us to focus exclusively on odd values (luckily, they seem to occur in a predictable pattern). 
-  * **sqrt() trick (s)** - mathematically it has been shown that if a number has any evenly divisible factors, at least one half of that factor pair will occur by the square root point of the number being tested. 
-  * **sqrt()-less square root approximation (a)** - **sqrt()**, a function in the math library, does an industrial strength square root calculation. We don't need that, merely a whole integer value corresponding to the approximate square root. Here we will implement our own logic to approximate square root, hopefully with a considerable performance impact. 
  
 Unless specified in the encoded name, your algorithm should only implement the algorithm and optimization(s) specified. Unless specified in the encoded name, your algorithm should only implement the algorithm and optimization(s) specified.
  
-That is, if your program to implement is **primerego**, that means you are ONLY to implement the brute force algorithm and odds-only checking. **NO** break on composite, **NO** sqrt() trick, etc. We are establishing separate data points for analytical comparison. +That is, if your program to implement is **primereg**, that means you are ONLY to implement the brute force algorithm, in all its unoptimized, inefficient glory. This is important for establishing separate data points for analytical comparison (with future projects).
- +
-Some of these optimizations can co-exist easily (break + map, odd + sqrt()), others are partially compatible (map + odd can coexist in a certain form), while others are mutually exclusive (sqrt() and approximated square root conflict). So there are definitely a few combinations that are possible using this scheme. +
- +
-Here are the variants you'll be implementing for this project: +
- +
-====break on composite (primeregb)==== +
-This optimization to primereg 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: +
- +
-There is no further need to check the remaining values, as once we have proven the non-primality of a number, the state is set: it is composite. So be sure to use a **break** statement to terminate the computation loop (how does this impact overall performance???). +
- +
-Make no other optimizations- this first project is to set up some important base line values that we can use for algorithmic comparison later on. +
- +
-====mapping factors of 6 (primeregm)==== +
-This optimization will check only the numbers that fall on either side of a factor of 6 for primality. +
- +
-NOTE: If applicable, just display the initial "2" and "3" as hardcoded values. +
- +
-====odds-only checking (primerego)==== +
-This optimization will check only the odd numbers for primality, skipping the evens entirely. +
- +
-NOTE: If applicable, just display the initial "2" as a hardcoded value. +
- +
-====sqrt() trick (primeregs)==== +
-This optimization employs the square root trick utilizing the C library's **sqrt()** function. +
- +
-====sqrt()-less square root approximation (primerega)==== +
-This optimization employs the approximated square root trick (**NOT** utilizing an existing square root function, but using simpler logic you implement to approximate the square root point). +
- +
-===Further explanation=== +
-An optimization to the previous process, which used **sqrt()**, this variation will do the exact same thing, but without using the **sqrt()** function. It will approximate the square root. +
- +
-We know that a square root (especially a whole numbered square root), is when we have whole number factors that are squared. But in addition, only considering the whole number aspect of the square root, we start seeing series of values with the same whole square root value: +
- +
-<cli> +
-lab46:~$ count=0; for ((i=2; i<152; i++)); do printf "[%3d] %2d " "${i}" `echo "sqrt($i)" | bc -q`; let count=count+1; if [ "${count}" -eq 10 ]; then echo; count=0; fi; 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 [ 49]  7 [ 50]  7 [ 51]  7 +
-[ 52]  7 [ 53]  7 [ 54]  7 [ 55]  7 [ 56]  7 [ 57]  7 [ 58]  7 [ 59]  7 [ 60]  7 [ 61]  7 +
-[ 62]  7 [ 63]  7 [ 64]  8 [ 65]  8 [ 66]  8 [ 67]  8 [ 68]  8 [ 69]  8 [ 70]  8 [ 71]  8 +
-[ 72]  8 [ 73]  8 [ 74]  8 [ 75]  8 [ 76]  8 [ 77]  8 [ 78]  8 [ 79]  8 [ 80]  8 [ 81]  9 +
-[ 82]  9 [ 83]  9 [ 84]  9 [ 85]  9 [ 86]  9 [ 87]  9 [ 88]  9 [ 89]  9 [ 90]  9 [ 91]  9 +
-[ 92]  9 [ 93]  9 [ 94]  9 [ 95]  9 [ 96]  9 [ 97]  9 [ 98]  9 [ 99]  9 [100] 10 [101] 10 +
-[102] 10 [103] 10 [104] 10 [105] 10 [106] 10 [107] 10 [108] 10 [109] 10 [110] 10 [111] 10 +
-[112] 10 [113] 10 [114] 10 [115] 10 [116] 10 [117] 10 [118] 10 [119] 10 [120] 10 [121] 11 +
-[122] 11 [123] 11 [124] 11 [125] 11 [126] 11 [127] 11 [128] 11 [129] 11 [130] 11 [131] 11 +
-[132] 11 [133] 11 [134] 11 [135] 11 [136] 11 [137] 11 [138] 11 [139] 11 [140] 11 [141] 11 +
-[142] 11 [143] 11 [144] 12 [145] 12 [146] 12 [147] 12 [148] 12 [149] 12 [150] 12 [151] 12 +
-</cli> +
- +
-Or, if perhaps we instead order by square root value: +
- +
-<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. +
- +
-There are some important lessons at play here: +
- +
-  * approximation can be powerful +
-  * approximation can result in a simpler algorithm, improving runtime +
-    * **sqrt()** is more complex than you may be aware, not to mention it is in a function. By avoiding that function call, we eliminate some overhead, and that can make a difference in runtime performance. +
- +
-Depending on how you implement this and the original sqrt() algorithms, this version may have a noticeable performance difference. If, on the other hand, you were really optimal in both implementations, the performance difference may be narrower (if negligible). +
-  +
-====primeregbm==== +
-To get a taste for combining optimizations, you'll also implement a variant that incorporates both the **break** AND the **map** optimizations. +
- +
-NOTE: If applicable, just display the initial "2" and "3" as hardcoded values. +
- +
-====primeregbo==== +
-To get a taste for combining optimizations, you'll also implement a variant that incorporates both the **break** AND the **odds-only checking** optimizations. +
- +
-NOTE: If applicable, just display the initial "2" as a hardcoded value. +
- +
-====primeregbs==== +
-To get a taste for combining optimizations, you'll also implement a variant that incorporates both the **break** AND the **sqrt()** optimizations. +
- +
-====primeregba==== +
-To get a taste for combining optimizations, you'll also implement a variant that incorporates both the **break** AND the **approximated square root** optimizations.+
  
 =====Programs===== =====Programs=====
Line 226: Line 121:
  
   - **primereg.c**: our baseline (does JUST the process, no optimizations)   - **primereg.c**: our baseline (does JUST the process, no optimizations)
-  - **primeregb.c**: tests specifically the break optimization 
-  - **primeregm.c**: tests specifically the map traversal 
-  - **primerego.c**: tests specifically the odd traversal 
-  - **primeregs.c**: tests specifically the square root trick (using sqrt()) 
-  - **primerega.c**: tests specifically the square root trick by approximating square root 
-  - **primeregbm.c**: tests the break and map optimizations (together) 
-  - **primeregbo.c**: tests the break and odd optimizations (together) 
-  - **primeregbs.c**: tests the break and sqrt() optimizations (together) 
-  - **primeregba.c**: tests the break and approximated square root optimizations (together) 
  
 ====Program Specifications==== ====Program Specifications====
Line 264: Line 150:
   * perform the correct algorithm and optimization(s) against the command-line input(s) given.   * perform the correct algorithm and optimization(s) against the command-line input(s) given.
     * each program is to have no fewer and no more than 2 loops in this prime processing section.     * each program is to have no fewer and no more than 2 loops in this prime processing section.
-    * in each program, you are not allowed to use a given loop type (for(), while(), do-while()) more than once! +  * display identified primes (space-separated) to **STDOUT** 
-  * display identified primes (space-separated) to a file pointer called **primelist** +  * stop your stopwatch immediately following your prime processing loops (and terminating newline display to **STDOUT**). Calculate the time that has transpired (ending time minus starting time). 
-  * stop your stopwatch immediately following your prime processing loops (and terminating newline display to **primelist**). Calculate the time that has transpired (ending time minus starting time). +  * output the processing run-time to **STDERR**
-  * output the processing run-time to the file pointer called **timing**+
   * 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:   * 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 (to **STDOUT**).
     * the timing information will be displayed in accordance to code I will provide below (see the **timing** section).     * the timing information will be displayed in accordance to code I will provide below (see the **timing** section).
  
Line 288: Line 173:
 *** Copy COMPLETE! You may now go to the '/home/USER/src/cprog/pnc0' directory *** *** Copy COMPLETE! You may now go to the '/home/USER/src/cprog/pnc0' directory ***
  
-make: Leaving directory '/var/public/fall2017/cprog/pnc0'+make: Leaving directory '/var/public/SEMESTER/cprog/pnc0'
 lab46:~/src/cprog/$  lab46:~/src/cprog/$ 
 lab46:~/src/cprog$ cd pnc0 lab46:~/src/cprog$ cd pnc0
 lab46:~/src/cprog/pnc0$ ls lab46:~/src/cprog/pnc0$ ls
-Makefile      primereg.c    primeregb.c    primeregm.c +Makefile      primereg.c
-primeregbm.c  primeregba.c  primerego.c    primeregbs.c +
-primeregs.c   primerega.c   primeregbo.c+
 lab46:~/src/cprog/pnc0$  lab46:~/src/cprog/pnc0$ 
 </cli> </cli>
Line 480: Line 363:
  
 <code c> <code c>
-fprintf(timing, "%8.4lf\n",+fprintf(stderr, "%8.4lf\n",
 time_end.tv_sec-time_start.tv_sec+((time_end.tv_usec-time_start.tv_usec)/1000000.0)); time_end.tv_sec-time_start.tv_sec+((time_end.tv_usec-time_start.tv_usec)/1000000.0));
 </code> </code>
Line 803: Line 686:
  
 <code> <code>
-39:pnc0:final tally of results (39/39)+78:pnc0:final tally of results (78/78)
 </code> </code>
  
Line 809: Line 692:
  
 <code> <code>
-*:pnc0:primeALGO.c compiles cleanly, no compiler messages [3/3] +*:pnc0:primeALGO.c compiles cleanly, no compiler messages [9/9] 
-*:pnc0:primeALGO.c implements only specified algorithm [6/6] +*:pnc0:primeALGO.c implements only specified algorithm [11/11] 
-*:pnc0:primeALGO.c consistent indentation throughout code [3/3] +*:pnc0:primeALGO.c consistent indentation throughout code [9/9] 
-*:pnc0:primeALGO.c relevant comments throughout code [3/3] +*:pnc0:primeALGO.c relevant comments throughout code [9/9] 
-*:pnc0:primeALGO.c code conforms to project specifications [3/3] +*:pnc0:primeALGO.c code conforms to project specifications [9/9] 
-*:pnc0:primeALGO.c runtime output conforms to specifications [4/4] +*:pnc0:primeALGO.c runtime output conforms to specifications [6/6] 
-*:pnc0:primeALGO.c make checkqty test times within reason [2/2] +*:pnc0:primeALGO.c make checkqty test times within reason [6/6] 
-*:pnc0:primeALGO.c make checkrange test times within reason [2/2]+*:pnc0:primeALGO.c make checkrange test times within reason [6/6]
 *:pnc0:primeALGO.c make verifyall tests succeed [13/13] *:pnc0:primeALGO.c make verifyall tests succeed [13/13]
 </code> </code>
  
 As the optimizations improve upon others, some evaluations will be based upon differences between a baseline (in some cases, primereg) and the optimization. As the optimizations improve upon others, some evaluations will be based upon differences between a baseline (in some cases, primereg) and the optimization.
haas/fall2017/cprog/projects/pnc0.1506271458.txt.gz · Last modified: 2017/09/24 16:44 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