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:10] – [prime algorithm implementation] wedgehaas:fall2017:cprog:projects:pnc1 [2017/10/15 21:27] (current) – [Full Verification Compliance] wedge
Line 128: Line 128:
 Here are the variants you'll be implementing for this project: 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 422: 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 448: 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 480: 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.1508101808.txt.gz · Last modified: 2017/10/15 21:10 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