Lab46 Wiki

User Tools

Site Tools

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

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Next revision		Previous revision
haas:spring2017:cprog:projects:pnc1 [2017/02/25 20:24] – created wedgehaas:spring2017:cprog:projects:pnc1 [2017/03/01 18:43] (current) – [Check Results] wedge
Line 80: Line 80:
 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. 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. For instance:+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:
  
-9*9 == 81, the square root of 81 is 9.+<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> 
 + 
 +Square root of 81 is 9, but so is the square root of 82, 83, 84... etc. up until we hit 100.
  
-If we were checking 81 to be prime, we'd only have to check up to 9.+If we were checking 87 to be prime, we'd only have to check up to 9.
  
-We don't need a **sqrt()** function to tell us this, we can determine the approximate square root point ourselves- simply square the current factor being tested, and so long as it hasn't exceeded the value we're checking, we know to continue.+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: There are some important lessons at play here:
Line 251: Line 270:
 lab46:~/src/cprog/pnc1$ primerun lab46:~/src/cprog/pnc1$ primerun
 ==================================================================================================== ====================================================================================================
-    range        brute     bruteopt         odds         sqrt     sqrtodds      sqrtopt  sqrtoptodds+    range        brute     bruteopt         odds         sqrt     sqrtodds      sqrtopt  sqrtoptodds 
 ==================================================================================================== ====================================================================================================
-      128     0.000097     0.000061     0.000075     0.000074     0.000074     0.000071     0.000052 +      128     0.000179     0.000139     0.000124     0.000108     0.000085     0.000112     0.000078  
-      256     0.000238     0.000105     0.000094     0.000096     0.000093     0.000061     0.000059 +      256     0.000401     0.000161     0.000120     0.000149     0.000128     0.000119     0.000085  
-      512     0.001000     0.000246     0.000165     0.000137     0.000096     0.000102     0.000070 +      512     0.001535     0.000345     0.000213     0.000207     0.000179     0.000134     0.000134  
-     1024     0.003545     0.000623     0.000333     0.000262     0.000183     0.000129     0.000124 +     1024     0.005385     0.000919     0.000542     0.000428     0.000268     0.000184     0.000159  
-     2048     0.012749     0.001880     0.000994     0.000592     0.000324     0.000249     0.000181 +     2048     0.019076     0.002767     0.001481     0.000857     0.000517     0.000335     0.000302  
-     4096     0.047120     0.006206     0.003176     0.001352     0.000733     0.000493     0.000302 +     4096     0.070836     0.009331     0.004770     0.002034     0.001148     0.000708     0.000480  
-     8192     0.180497     0.021454     0.010806     0.003317     0.001723     0.001093     0.000636 +     8192     0.270955     0.032402     0.016253     0.004934     0.002525     0.001575     0.000950  
-    16384     0.705101     0.077583     0.038932     0.008163     0.004174     0.002539     0.001438 +    16384     1.059970     0.116575     0.058424     0.012190     0.006239     0.003676     0.002117  
-    32768     2.786815     0.282426     0.141502     0.020472     0.010376     0.005936     0.003327 +    32768     4.209891     0.424113     0.212701     0.030711     0.015568     0.008867     0.004950  
-    65536   ----------     1.047397     0.524213     0.052126     0.026311     0.014934     0.008014 +    65536   ----------     1.626774     0.787444     0.078278     0.039605     0.022158     0.012015  
-   131072   ----------     5.159748     2.580796     0.140917     0.070404     0.044539     0.023510 +   131072   ----------     7.769508     3.954632     0.211732     0.105749     0.066574     0.035054  
-   262144   ----------   ----------   ----------     0.368282     0.183205     0.117075     0.060993 +   262144   ----------   ----------   ----------     0.553307     0.275414     0.175391     0.091195  
-   524288   ----------   ----------   ----------     0.961903     0.488336     0.295707     0.152570 +   524288   ----------   ----------   ----------     1.440572     0.713855     0.444240     0.229179  
-  1048576   ----------   ----------   ----------     2.487897     1.235418     0.745615     0.382472 +  1048576   ----------   ----------   ----------     3.743303     1.856485     1.137094     0.574455  
-  2097152   ----------   ----------   ----------   ----------     3.232523     1.893893     0.967266 +  2097152   ----------   ----------   ----------   ----------     4.857408     2.923402     1.451850  
-  4194304   ----------   ----------   ----------   ----------   ----------     4.856079     2.472582 +  4194304   ----------   ----------   ----------   ----------   ----------   ----------     3.708858  
-  8388608   ----------   ----------   ----------   ----------   ----------   ----------   ----------+  8388608   ----------   ----------   ----------   ----------   ----------   ----------   ---------- 
 ==================================================================================================== ====================================================================================================
- verify:       OK           OK           OK           OK           OK           OK           OK+ verify:       OK           OK           OK           OK           OK           OK           OK      
 ==================================================================================================== ====================================================================================================
 lab46:~/src/cprog/pnc1$  lab46:~/src/cprog/pnc1$ 
Line 319: Line 338:
  
 You should get some sort of confirmation indicating successful submission if all went according to plan. If not, check for typos and or locational mismatches. You should get some sort of confirmation indicating successful submission if all went according to plan. If not, check for typos and or locational mismatches.
 +
 +What I will be looking for:
 +
 +<code>
 +78:pnc1:final tally of results (78/78)
 +*:pnc1:submit all programs correctly named using submit tool [3/3]
 +*:pnc1:primeodds.c no negative compiler messages [2/2]
 +*:pnc1:primeodds.c implements only specified algorithm [4/4]
 +*:pnc1:primeodds.c adequate indentation and comments [3/3]
 +*:pnc1:primeodds.c output conforms to specifications [3/3]
 +*:pnc1:primeodds.c primerun runtime tests succeed [3/3]
 +*:pnc1:primesqrt.c no negative compiler messages [2/2]
 +*:pnc1:primesqrt.c implements only specified algorithm [4/4]
 +*:pnc1:primesqrt.c adequate indentation and comments [3/3]
 +*:pnc1:primesqrt.c output conforms to specifications [3/3]
 +*:pnc1:primesqrt.c primerun runtime tests succeed [3/3]
 +*:pnc1:primesqrtodds.c no negative compiler messages [2/2]
 +*:pnc1:primesqrtodds.c implements only specified algorithm [4/4]
 +*:pnc1:primesqrtodds.c adequate indentation and comments [3/3]
 +*:pnc1:primesqrtodds.c output conforms to specifications [3/3]
 +*:pnc1:primesqrtodds.c primerun runtime tests succeed [3/3]
 +*:pnc1:primesqrtopt.c no negative compiler messages [2/2]
 +*:pnc1:primesqrtopt.c implements only specified algorithm [4/4]
 +*:pnc1:primesqrtopt.c adequate indentation and comments [3/3]
 +*:pnc1:primesqrtopt.c output conforms to specifications [3/3]
 +*:pnc1:primesqrtopt.c primerun runtime tests succeed [3/3]
 +*:pnc1:primesqrtoptodds.c no negative compiler messages [2/2]
 +*:pnc1:primesqrtoptodds.c implements only specified algorithm [4/4]
 +*:pnc1:primesqrtoptodds.c adequate indentation and comments [3/3]
 +*:pnc1:primesqrtoptodds.c output conforms to specifications [3/3]
 +*:pnc1:primesqrtoptodds.c primerun runtime tests succeed [3/3]
 +</code>
haas/spring2017/cprog/projects/pnc1.1488054248.txt.gz · Last modified: 2017/02/25 20:24 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