Lab46 Wiki

User Tools

Site Tools

You are here: start » haas » summer2017 » cprog » projects » pnc2
haas:summer2017:cprog:projects:pnc2

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:summer2017:cprog:projects:pnc2 [2017/07/08 12:38] – [Approximating array size] wedgehaas:summer2017:cprog:projects:pnc2 [2017/07/08 12:47] (current) – [Approximating array size] wedge
Line 310: Line 310:
 ... we would see that the 32nd prime is 131. For the Sieve of Eratosthenes to successfully work in this case, we'd need an array size of at least 132 (if we do the standard mapping of array element to actual number, where element 0 would correspond with the number 0, and element 131 would correspond with number 131; 0-131 = 132 elements). ... we would see that the 32nd prime is 131. For the Sieve of Eratosthenes to successfully work in this case, we'd need an array size of at least 132 (if we do the standard mapping of array element to actual number, where element 0 would correspond with the number 0, and element 131 would correspond with number 131; 0-131 = 132 elements).
  
-But that number isn't immediately known (indeed, the nature of the distribution of prime numbers is the subject of considerable mathematical exploration, with many various proofs demonstrating different aspects of their distribution). And short of some impressive looking and very calculus-requiring integral, there doesn't (at least from some of my searches) seem to be a decent algebraic expression we can use to come close.+But that number isn't immediately known (indeed, the nature of the distribution of prime numbers is the subject of considerable mathematical exploration, with many various proofs demonstrating different aspects of their distribution-- don't believe me? Just google "**distribution of primes**" and read up for yourself). And short of some impressive looking and very calculus-requiring integral, there doesn't (at least from some of my searches) seem to be a decent algebraic expression we can use to come close.
  
 And without this knowledge of the largest prime in the desired quantity, our sieve implementation (with the requirements as I have specified) is sort of at a standstill. And without this knowledge of the largest prime in the desired quantity, our sieve implementation (with the requirements as I have specified) is sort of at a standstill.
Line 323: Line 323:
  
 <code bash 1> <code bash 1>
 +# clear the screen
 clear clear
 +
 +# loop for a powers of 2 progression 32-4194304 (inclusive)
 for((qty=32; qty<=4194304; qty*=2)); do for((qty=32; qty<=4194304; qty*=2)); do
 +
 +    # display the quantity lead-in information
     printf "[%7s] %7sth prime: " "${qty}" "${qty}"     printf "[%7s] %7sth prime: " "${qty}" "${qty}"
 +    
 +    # obtain the last/largest prime in the specified quantity
     value=$(./primebrksrtoptodd ${qty} 1 2>/dev/null | tr ' ' '\n' | tail -2 | head -1)     value=$(./primebrksrtoptodd ${qty} 1 2>/dev/null | tr ' ' '\n' | tail -2 | head -1)
 +
 +    # display it, along with calculating its approximate multiplier
     printf "%8s (x%s)\n" "${value}" $(echo "(${value}/${qty})+1" | bc -q)     printf "%8s (x%s)\n" "${value}" $(echo "(${value}/${qty})+1" | bc -q)
 done done
Line 460: Line 469:
 The execution of the programs is short and simple- grab the parameters, do the processing, produce the output, and then terminate. The execution of the programs is short and simple- grab the parameters, do the processing, produce the output, and then terminate.
  
 +Based on specifications, it should also be able to do the following (override quantity with lower/upper bounds):
 +
 +<cli>
 +lab46:~/src/cprog/pnc2$ ./primesoe 48 1 4 18
 +5 7 11 13 17
 +  0.000080
 +lab46:~/src/cprog/pnc2$ 
 +</cli>
 +
 +And (shift the lower bound, but still count out 32 primes):
 +
 +<cli>
 +lab46:~/src/cprog/pnc2$ ./primesoe 32 1 16
 +17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163
 +  0.000087
 +lab46:~/src/cprog/pnc2$ 
 +</cli>
 +
 +And of course the same for the 3 variants, and the same error message reporting if invalid values are given.
 ====Performance changes==== ====Performance changes====
 You may notice a change with the sieves as compared to the other algorithms you've implemented with respect to performance- there will likely be a lower bound of performance, ie you have to exceed a certain threshold before the algorithm truly enters its power band, and then it may truly be a step-up in terms of performance. You may notice a change with the sieves as compared to the other algorithms you've implemented with respect to performance- there will likely be a lower bound of performance, ie you have to exceed a certain threshold before the algorithm truly enters its power band, and then it may truly be a step-up in terms of performance.
haas/summer2017/cprog/projects/pnc2.1499517485.txt.gz · Last modified: 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