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

Both sides previous revisionPrevious revision
Next revision		Previous revision
haas:spring2017:cprog:projects:pnc1 [2017/03/01 10:37] – [sqrt()-less square root (primesqrtopt)] 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:
  
 <cli> <cli>
-lab46:~$ for ((i=8; i<38; i++)); do echo -n "[${i}] "; echo "sqrt($i)" | bc -q; done +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 
-[8] 2 +[  2]  1 [  3]  1 [  4]  2 [  5]  2 [  6]  2 [  7]  2 [  8]  2 [  9]  3 [ 10]  3 [ 11]  3 
-[9] 3 +[ 12]  3 [ 13]  3 [ 14]  3 [ 15]  3 [ 16]  4 [ 17]  4 [ 18]  4 [ 19]  4 [ 20]  4 [ 21]  4 
-[10] 3 +[ 22]  4 [ 23]  4 [ 24]  4 [ 25]  5 [ 26]  5 [ 27]  5 [ 28]  5 [ 29]  5 [ 30]  5 [ 31]  5 
-[11] 3 +[ 32]  5 [ 33]  5 [ 34]  5 [ 35]  5 [ 36]  6 [ 37]  6 [ 38]  6 [ 39]  6 [ 40]  6 [ 41]  6 
-[12] 3 +[ 42]  6 [ 43]  6 [ 44]  6 [ 45]  6 [ 46]  6 [ 47]  6 [ 48]  6 [ 49]  7 [ 50]  7 [ 51]  7 
-[13] 3 +[ 52]  7 [ 53]  7 [ 54]  7 [ 55]  7 [ 56]  7 [ 57]  7 [ 58]  7 [ 59]  7 [ 60]  7 [ 61]  7 
-[14] 3 +[ 62]  7 [ 63]  7 [ 64]  8 [ 65]  8 [ 66]  8 [ 67]  8 [ 68]  8 [ 69]  8 [ 70]  8 [ 71]  8 
-[15] 3 +[ 72]  8 [ 73]  8 [ 74]  8 [ 75]  8 [ 76]  8 [ 77]  8 [ 78]  8 [ 79]  8 [ 80]  8 [ 81]  9 
-[16] 4 +[ 82]  9 [ 83]  9 [ 84]  9 [ 85]  9 [ 86]  9 [ 87]  9 [ 88]  9 [ 89]  9 [ 90]  9 [ 91]  9 
-[17] 4 +[ 92]  9 [ 93]  9 [ 94]  9 [ 95]  9 [ 96]  9 [ 97]  9 [ 98]  9 [ 99]  9 [100] 10 [101] 10 
-[18] 4 +[102] 10 [103] 10 [104] 10 [105] 10 [106] 10 [107] 10 [108] 10 [109] 10 [110] 10 [111] 10 
-[19] 4 +[112] 10 [113] 10 [114] 10 [115] 10 [116] 10 [117] 10 [118] 10 [119] 10 [120] 10 [121] 11 
-[20] 4 +[122] 11 [123] 11 [124] 11 [125] 11 [126] 11 [127] 11 [128] 11 [129] 11 [130] 11 [131] 11 
-[21] 4 +[132] 11 [133] 11 [134] 11 [135] 11 [136] 11 [137] 11 [138] 11 [139] 11 [140] 11 [141] 11 
-[22] 4 +[142] 11 [143] 11 [144] 12 [145] 12 [146] 12 [147] 12 [148] 12 [149] 12 [150] 12 [151] 12
-[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+
 </cli> </cli>
  
-9*9 == 81, the square root of 81 is 9.+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 285: 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$ 
haas/spring2017/cprog/projects/pnc1.1488364654.txt.gz · Last modified: 2017/03/01 10:37 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