Lab46 Wiki

User Tools

Site Tools

You are here: start » haas » fall2017 » cprog » projects » pnc1
haas:fall2017:cprog:projects:pnc1

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:pnc1 [2017/10/15 21:08] – wedgehaas:fall2017:cprog:projects:pnc1 [2017/10/15 21:27] (current) – [Full Verification Compliance] wedge
Line 112: 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 **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).+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.
  
 +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).
 =====Programs===== =====Programs=====
 It is your task to write the following prime number variants: It is your task to write the following prime number variants:
  
-  - **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 
  
 ====Program Specifications==== ====Program Specifications====
Line 411: Line 499:
  
 ====check qty==== ====check qty====
-For instance (running on my implementation of the pnc1 programs, some output omitted to keep the surprise alive):+For instance (running on my implementation of the pnc1 programs):
  
 <cli> <cli>
 lab46:~/src/cprog/pnc1$ make checkqty lab46:~/src/cprog/pnc1$ make checkqty
-================= +========================================================= 
-      qty     reg +      qty     reg    regm    rego    regb    regs    rega 
-================= +========================================================= 
-       32  0.0002 +       32  0.0001  0.0001  0.0001  0.0001  0.0001  0.0001 
-       64  0.0006 +       64  0.0003  0.0001  0.0001  0.0001  0.0001  0.0001 
-      128  0.0028 +      128  0.0012  0.0004  0.0003  0.0002  0.0001  0.0001 
-      256  0.0123 +      256  0.0057  0.0020  0.0014  0.0009  0.0003  0.0003 
-      512  0.0574 +      512  0.0278  0.0098  0.0066  0.0038  0.0009  0.0009 
-     1024  0.2690 +     1024  0.1348  0.0476  0.0318  0.0166  0.0025  0.0025 
-... +     2048  0.6416  0.2317  0.1510  0.0727  0.0073  0.0073 
-   262144  ------ +     4096  3.0281  1.0707  0.7096  0.3144  0.0218  0.0217 
-================= +     8192  ------  ------  3.2926  1.3627  0.0649  0.0649 
- verify:     OK   +    16384  ------  ------  ------  ------  0.1955  0.1954 
-=================+    32768  ------  ------  ------  ------  0.5910  0.5905 
 +    65536  ------  ------  ------  ------  1.7891  1.7864 
 +   131072  ------  ------  ------  ------  ------  ------ 
 +========================================================= 
 + verify:     OK      OK      OK      OK      OK      OK 
 +=========================================================
 lab46:~/src/cprog/pnc1$  lab46:~/src/cprog/pnc1$ 
 </cli> </cli>
Line 437: Line 530:
 <cli> <cli>
 lab46:~/src/cprog/pnc1$ make checkrange lab46:~/src/cprog/pnc1$ make checkrange
-================= +========================================================= 
-    range     reg +    range     reg    regm    rego    regb    regs    rega 
-================= +========================================================= 
-       32  0.0001 +       32  0.0001  0.0000  0.0000  0.0000  0.0001  0.0000 
-       64  0.0001 +       64  0.0001  0.0001  0.0000  0.0000  0.0000  0.0000 
-      128  0.0002 +      128  0.0001  0.0001  0.0001  0.0001  0.0001  0.0001 
-      256  0.0004 +      256  0.0002  0.0001  0.0001  0.0001  0.0001  0.0001 
-      512  0.0015 +      512  0.0006  0.0003  0.0002  0.0002  0.0001  0.0001 
-     1024  0.0053 +     1024  0.0023  0.0008  0.0006  0.0004  0.0002  0.0002 
-     2048  0.0191 +     2048  0.0088  0.0032  0.0021  0.0013  0.0004  0.0004 
-     4096  0.0709 +     4096  0.0344  0.0125  0.0082  0.0047  0.0010  0.0010 
-     8192  0.2712 +     8192  0.1358  0.0495  0.0322  0.0167  0.0025  0.0025 
-... +    16384  0.5402  0.1968  0.1270  0.0616  0.0065  0.0065 
-  2097152  ------ +    32768  2.1530  0.7857  0.5050  0.2271  0.0170  0.0171 
-================= +    65536  ------  3.1395  2.0088  0.8468  0.0454  0.0455 
- verify:     OK  +   131072  ------  ------  ------  3.1817  0.1230  0.1230 
-=================+   262144  ------  ------  ------  ------  0.3359  0.3359 
 +   524288  ------  ------  ------  ------  0.9245  0.9240 
 +  1048576  ------  ------  ------  ------  2.5601  2.5585 
 +  2097152  ------  ------  ------  ------  ------  ------ 
 +========================================================= 
 + verify:     OK      OK      OK      OK      OK      OK 
 +=========================================================
 lab46:~/src/cprog/pnc1$  lab46:~/src/cprog/pnc1$ 
 </cli> </cli>
Line 469: Line 568:
 <cli> <cli>
 lab46:~/src/cprog/pnc1$ make verifyall lab46:~/src/cprog/pnc1$ make verifyall
-================= +========================================================= 
-              reg +              reg    regm    rego    regb    regs    rega 
-================= +========================================================= 
- qtynorm:    OK   + qtynorm:    OK      OK      OK      OK      OK      OK 
- qtypart:    OK   + qtypart:    OK      OK      OK      OK      OK      OK 
- rngnorm:    OK   + rngnorm:    OK      OK      OK      OK      OK      OK 
- rngpart:    OK   + rngpart:    OK      OK      OK      OK      OK      OK 
-    coop:    OK   +    coop:    OK      OK      OK      OK      OK      OK 
-   coop2:    OK   +   coop2:    OK      OK      OK      OK      OK      OK 
-   coop3:    OK   +   coop3:    OK      OK      OK      OK      OK      OK 
-  noargs:    OK   +  noargs:    OK      OK      OK      OK      OK      OK 
- invargs:    OK   + invargs:    OK      OK      OK      OK      OK      OK 
-  invqty:    OK   +  invqty:    OK      OK      OK      OK      OK      OK 
- invnary:    OK   + invnary:    OK      OK      OK      OK      OK      OK 
-  invlow:    OK   +  invlow:    OK      OK      OK      OK      OK      OK 
- invhigh:    OK   + invhigh:    OK      OK      OK      OK      OK      OK 
-=================+=========================================================
 lab46:~/src/cprog/pnc1$  lab46:~/src/cprog/pnc1$ 
 </cli> </cli>
haas/fall2017/cprog/projects/pnc1.1508101707.txt.gz · Last modified: 2017/10/15 21:08 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