Differences

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

--- haas:summer2017:cprog:projects:pnc2 [2017/03/08 13:52] – external edit 127.0.0.1
+++ haas:summer2017:cprog:projects:pnc2 [2017/07/08 12:47] (current) – [Approximating array size] wedge
@@ Line 14: / Line 14: @@
 A concept in Computer Science curriculum is the notion of computational/algorithmic complexity.
-Basically, a solution to a problem exists on a spectrum of efficiency (typically constrained by time vs. space): if optimizing for time, the code size tends to grow.
+Basically, a solution to a problem exists on a spectrum of efficiency (typically constrained by time vs. space). Once you've hashed out an implementation:
-In the previous projects, we focused on algorithms that were constrained by time- taking progressively more time the larger the data set to be processed. These time-constrained algorithms also happens to be the type of algorithm you're most familiar with (at least, were indoctrinated into thinking... your third grade self potentially would have found more familiarity with these space-constrained methods).
+  * if optimizing for (or trying to take up less) time, the code size tends to grow or become more complex.
+  * if optimizing for (or trying to take up less) space, the program runtime can grow.
-In contrast to time-constrained approaches we have space-constrained approaches, which will utilize more space in the solving of the program to the benefit of requiring less time.
+Let it be clear: using modern computers bound by fourth dimensional constraints, we **cannot** write solutions without some foothold in both space and time (any program has statements in it that accomplish the task at hand (space occupied), and that same program takes time to run (even if it happens rather quickly)). What we can do is influence where on the space-time spectrum our implementation falls, and if done strategically for the particular constraint at hand, can aid us in achieving desired improvements in program efficiency.
-We can never be entirely time- or space-constrained... some element of the other will always be present. But by embracing the advantages of an approach, we can really make an impact in the desired area.
+In the previous projects, we focused on algorithms that were more constrained by time- taking progressively more time the larger the data set to be processed. These time-constrained algorithms also happen to be the type of algorithm you're most familiar with (or at least, were indoctrinated into thinking with...) your third grade self, on the other hand,  potentially would have found more familiarity with the space-constrained methods this project will explore.
-What we will be looking at in this project is a type of prime number calculating algorithm known as a sieve. It will utilize space in solving the problem instead of exclusively using time.
+So in contrast to time-constrained approaches we have space-constrained approaches, which will utilize more space (ie allocating memory) in the solving of the program to the benefit of requiring less time.
+We can never be entirely time- or space-free... some element of the other will always be present. But by embracing the advantages of an approach, we can really make an impact in the desired area.
+What we will be looking at in this project is a type of prime number calculating algorithm known as a sieve. It will make strategic use of space to aid us in the solving of the problem instead of exclusively relying on time.
+Of note, the "mainstream" prime number computing efforts typically make use of sieves.
 =====Optimizing the prime number calculation=====
@@ Line 29: / Line 36: @@
 For this project, please assume the following:
-  * you are doing all values (odds AND evens).
+  * unless otherwise specified, you are doing all values (odds AND evens).
-  * if you exceed 64 million and get "--error!---" that's okay. I have memory limits in place (just like I have time limits in place).
+  * if you exceed 64 million and get "--error!---" from primerun that's okay. I have memory limits in place (just like I have time limits in place).
-  * if applicable, you can base your code on primebruteopt, but you may find the sieve algorithms to be different enough where you may not want to adapt existing code, but start fresh.
+  * as the space-based approach to solving our prime number computation problem is fundamentally different from those we took in previous projects, you will want to look to start from scratch. Trying to reuse old code and shoehorn it into what effectively amounts to an entirely different paradigm will create a lot of problems.
-====your own optimizations (primeopt)====
-The first program to consider for this project offers you a chance to try out your own algorithm-optimizing skills. In both **pnc0** and **pnc1**, you implemented various approaches, often employing some very common sense improvements to the process.
-Here, I want you to take that knowledge you've gained, and combined with your own numerical fluency, attempt to hash out your own optimized algorithm for computing primes, plotting its time performance out against your other implementations.
-The **primerun** tool will recognize prime number calculating programs by the following names and process them accordingly:
-  * **primeopt**
-  * **primeopt1**
-  * **primeopt2**
-  * **primeopt3**
-  * **primeopt4**
-For credit, you only need to have ONE prime**opt** program... but these other slots are here should you wish to experiment.
-NOTE: this is to be an implementation different from the others.
-Compare your **primeopt** performance against that of the others to get a feel for how changes you make or implement impact overall runtime.
+But, the conceptual level we'll be pursuing will be the space-based equivalent of **primebrute**/**primebrk**, that is, no fancy optimizations for odd numbers, nor the **sqrt()** trick, just straight up processing of the values that need to be processed.
-====sieve of Eratosthenes (primesieveoferat)====
+=====Sieve of Eratosthenes (primesoe)=====
-The next program will be a sieve algorithm. We will be implementing one of the best known and likely longest-known sieves: the sieve of Eratosthenes.
+Your next program, and first sieve, will be the Sieve of Eratosthenes. Perhaps among the best  and likely longest-known sieves, its origins date from antiquity.
-The sieve, instead of calculating to determine the eligibility of a prime, works in a manner of marking off patterns of values that cannot be prime (so, it is composite-focused in approach vs. prime-focused).
+This sieve, instead of calculating to determine the eligibility of a prime, works in a manner of marking off patterns of values that cannot be prime (so, it is composite-focused in approach vs. prime-focused).
 In order for it to work, we must store all the values we're processing so we can obtain what is left when done-- what remains are the prime values.
@@ Line 85: / Line 75: @@
 This is a space-constrained algorithm, therefore we will need a chunk of space to store these values. Think about what a lot of this looks like with respect to how you know how to organize data.
-====sieve of Sundaram (primesieveofsund)====
+=====Optimizations on sieve of Eratosthenes=====
-As with any approach, there are multiple ways to go about implementing it. Just as our brute force time-constrained algorithms could benefit from algorithmic optimizations, so too can our sieves.
-The other program I would like you to write is an implementation of the sieve of Sundaram algorithm.
+====odds-only processing (primesoeodd)====
+Taking the **primesoe** codebase, enhance it to do odds-only processing, ideally considering overall storage used.
-Here is the wikipedia page: https://en.wikipedia.org/wiki/Sieve_of_Sundaram
+====sqrt() trick (primesoesrt)====
+Taking the **primesoe** codebase, enhance it to utilize the **sqrt()** (or **sqrt()-less square root**) trick.
-Here is an animated image of this sieve in action (from wikipedia):
+Compared to the brute/brk algorithms from the previous projects, the performance differences between using **sqrt()** and approximating the square root should be minimal. You are free to utilize either approach in your implementation for this project.
-{{:haas:fall2016:discrete:projects:sieve_of_sundaram.gif|}}
+NOTE: this variant is still to process all values (odd and even).
-Here's another page that discusses this sieve: [[https://plus.maths.org/content/sundarams-sieve|Sieve of Sundaram]]
+NOTE: if you are curious in comparing actual performance between sqrt() and approximated square root, **primerun** will recognize the following program names:
-===Overview of algorithm===
+  * **primesoesrt**
-  * Receive **max** value from command-line
+  * **primesoesrtopt**
-  * Produce an array of the values from 0 to **max**.
-  * Disqualify all values that are of the form (**i** + **j** + (2*i*j)), provided:
+====odds-only+sqrt() trick (primesoesrtodd)====
-    * **i** and **j** are less than **max**
+Taking the **primesoe** codebase, enhance it to do odds-only processing AND utilize the **sqrt()** (or **sqrt()-less square root**) trick.
-    * **j** is always greater than or equal to **i**
-    * **i** is greater than or equal to 1 (one)
+Compared to the brute/brk algorithms from the previous projects, the performance differences between using **sqrt()** and approximating the square root should be minimal. You are free to utilize either approach in your implementation for this project.
-    * The equation (**i** + **j** + (2*i*j)) is less than or equal to **max**
-  * Multiply the remaining numbers by 2, and add 1.
+NOTE: if you are curious in comparing actual performance between sqrt() and approximated square root for this odds-processing variant, **primerun** will recognize the following program names:
+  * **primesoesrtodd**
+  * **primesoesrtoptodd**
-This process will yield prime numbers less than 2*max + 2.
 =====Program=====
-It is your task to write some optimized prime number calculating programs:
+It is your task to write four Sieve of Eratosthenes-oriented prime number calculating programs:
-  - **primeopt.c**: implementing an approach of your own
+  - **primesoe.c**: using the space-oriented sieve algorithm (baseline sieve)
-  - **primesieveoferat.c**: using the space-oriented sieve algorithm
+  - **primesoeodd.c**: applying the odds-only processing to the sieve of Eratosthenes
-  - **primesieveofsund.c**: another sieve
+  - **primesoesrt.c**: applying the sqrt() trick to sieve of Eratosthenes
+  - **primesoesrtodd.c**: applying BOTH odds-only processing and sqrt() trick to sieve of Eratosthenes
-Your program should:
+====Program Specifications====
-  * obtain 1 parameter from the command-line (see **command-line arguments** section below):
+Your programs should:
-    * argv[1]: maximum value to calculate to (your program should run from (approximately) 2 through that number (inclusive of that number)
+  * obtain 2-4 parameters from the command-line (see **command-line arguments** section below).
-    * this value should be a positive integer value; you can make the assumption that the user will always do the right thing.
+    * check to make sure the user indeed supplied enough parameters, and exit with an error message if not.
-  * do the specified algorithmic optimizations
+    * argv[1]: maximum quantity of primes to calculate (your program should run until it discovers **that** many primes).
-    * please take note in differences in run-time, contemplating the impact the various algorithms and approaches have on performance.
+      * this value should be an integer value, greater than or equal to 0.
-  * start your stopwatch (see **timing** section below):
+        * if argv[1] is 0, disable the quantity check, and rely on provided lower and upper bounds (argv[4] would be required in this case).
-  * perform the correct algorithm against the input
+    * argv[2]: reserved for future compatibility; for now, assume it is **1**.
-  * display (to STDOUT) the prime numbers found in the range
+    * argv[3]: **conditionally optional** lower bound (starting value). Most of the time, this will probably be **2**, but should be a positive integer greater than or equal to 2. This defines where you program will start its prime quantity check from.
-  * output the processing run-time to STDERR
+      * if omitted, assume a lower bound of **2**.
-  * your output **MUST** be conformant to the example output in the **execution** section below. This is also a test to see how well you can implement to specifications. Basically:
+      * if you desired to specify an upper bound (argv[4]), you obviously MUST provide the lower bound argument under this scheme.
+    * argv[4]: **conditionally optional** upper bound (ending value). If provided, this is the ending value you'd like to check to.
+      * If doing a quantity run (argv[1] NOT 0), this value isn't necessary.
+      * If doing a quantity run AND you specify an upper bound, whichever condition is achieved first dictates program termination. That is, upper bound could override quantity (if it is achieved before quantity), and quantity can override the upper bound (if it is achieved before reaching the specified upper bound).
+    * for each argument: you should do a basic check to ensure the user complied with this specification, and exit with a unique error message (displayed to STDERR) otherwise:
+      * for insufficient quantity of arguments, display: **PROGRAM_NAME: insufficient number of arguments!**
+      * for invalid argv[1], display: **PROGRAM_NAME: invalid quantity!**
+      * for invalid argv[2], display: **PROGRAM_NAME: invalid value!**
+      * for invalid argv[3], display: **PROGRAM_NAME: invalid lower bound!**
+        * if argv[3] is not needed, ignore (no error displayed not forced exit, as it is acceptable defined behavior).
+      * for invalid argv[4], display: **PROGRAM_NAME: invalid upper bound!**
+        * if argv[4] is not needed, ignore (no error displayed nor forced exit, as it is acceptable defined behavior).
+      * In these error messages, **PROGRAM_NAME** is the name of the program being run; this can be accessed as a string stored in **argv[0]**.
+    * please take note in differences in run-time, contemplating the impact the various algorithms/optimizations have on performance.
+  * start your stopwatch (see **timing** section below).
+  * perform the correct algorithm against the input(s) given.
+  * display to STDOUT (file pointer **stdout**) the prime numbers calculated.
+  * stop your stopwatch. Calculate the time that has transpired (ending time minus starting time).
+  * output the processing run-time to STDERR (file pointer **stderr**).
+  * your output **MUST** conform to the example output in the **execution** section below. This is also a test to see how well you can implement to specifications. Basically:
     * as primes are being displayed, they are space-separated (first prime hugs the left margin), and when all said and done, a newline is issued.
-    * the timing information will be displayed in accordance to code I will provide (in the **timing** section).
+    * the timing information will be displayed in accordance to code I will provide below (see the **timing** section).
 =====Grabit Integration=====
@@ Line 137: / Line 150: @@
 <cli>
 lab46:~/src/cprog$ grabit cprog pnc2
-make: Entering directory '/var/public/spring2017/cprog/pnc2'
+make: Entering directory '/var/public/SEMESTER/cprog/pnc2'
-‘/var/public/spring2017/cprog/pnc2/Makefile’ -> ‘/home/USERNAME/src/cprog/pnc2/Makefile’
+‘/var/public/SEMESTER/cprog/pnc2/Makefile’ -> ‘/home/USERNAME/src/cprog/pnc2/Makefile’
-‘/var/public/spring2017/cprog/pnc2/primeopt.c’ -> ‘/home/USERNAME/src/cprog/pnc2/primeopt.c’
+‘/var/public/SEMESTER/cprog/pnc2/primesoe.c’ -> ‘/home/USERNAME/src/cprog/pnc2/primesoe.c’
-‘/var/public/spring2017/cprog/pnc2/primesieveoferat.c’ -> ‘/home/USERNAME/src/cprog/pnc2/primesieveoferat.c’
+‘/var/public/SEMESTER/cprog/pnc2/primesoeodd.c’ -> ‘/home/USERNAME/src/cprog/pnc2/primesoeodd.c’
-‘/var/public/spring2017/cprog/pnc2/primesieveofsund.c’ -> ‘/home/USERNAME/src/cprog/pnc2/primesieveofsund.c’
+‘/var/public/SEMESTER/cprog/pnc2/primesoesrt.c’ -> ‘/home/USERNAME/src/cprog/pnc2/primesoesrt.c’
-make: Leaving directory '/var/public/spring2017/cprog/pnc2'
+‘/var/public/SEMESTER/cprog/pnc2/primesoesrtodd.c’ -> ‘/home/USERNAME/src/cprog/pnc2/primesoesrtodd.c’
+make: Leaving directory '/var/public/SEMESTER/cprog/pnc2'
 lab46:~/src/cprog$ cd pnc2
 lab46:~/src/cprog/pnc2$ ls
-Makefile  primeopt.c  primesieveoferat.c  primesieveofsund.c
+Makefile  primesoe.c  primesoeodd.c  primesoesrt.c  primesoesrtodd.c
 lab46:~/src/cprog/pnc2$
 </cli>
-Furthermore, if your pnc2/ project directory is next to a pnc1/ and pnc0/ directory, each containing those project's specific prime variants, you can symlink them into the current project directory with a **make link**:
+Furthermore, if your **pnc2/** project directory is next to a **pnc1/** and **pnc0/** directory, each containing those project's specific prime variants, you can symlink them into the current project directory with a **make link**:
 <cli>
 lab46:~/src/cprog/pnc2$ make link
 ‘./primebrute.c’ -> ‘../pnc0/primebrute.c’
-‘./primebruteopt.c’ -> ‘../pnc0/primebruteopt.c’
+‘./primebrk.c’ -> ‘../pnc0/primebrk.c’
-‘./primeodds.c’ -> ‘../pnc1/primeodds.c’
+‘./primebrkodd.c’ -> ‘../pnc1/primebrkodd.c’
-‘./primesqrt.c’ -> ‘../pnc1/primesqrt.c’
+‘./primebrksrt.c’ -> ‘../pnc1/primebrksrt.c’
-‘./primesqrtodds.c’ -> ‘../pnc1/primesqrtodds.c’
+‘./primebrkoddsrt.c’ -> ‘../pnc1/primebrkoddsrt.c’
-‘./primesqrtopt.c’ -> ‘../pnc1/primesqrtopt.c’
+‘./primebrksrtopt.c’ -> ‘../pnc1/primebrksrtopt.c’
-‘./primesqrtoptodds.c’ -> ‘../pnc1/primesqrtoptodds.c’
+‘./primebrkoddsrtopt.c’ -> ‘../pnc1/primebrkoddsrtopt.c’
 lab46:~/src/cprog/pnc2$
 </cli>
@@ Line 171: / Line 185: @@
 Just another "nice thing" we deserve.
-NOTE: You do NOT want to do this on a populated pnc2 project directory-- it will overwrite files. Only do this on an empty directory.
+NOTE: You do NOT want to do this on a populated pnc2/ project directory-- it will overwrite files. Only do this on an empty directory.
 =====Command-Line Arguments=====
@@ Line 195: / Line 209: @@
 The arguments are accessible via the argv array, in the order they were specified:
-  * argv[0]: program invocation (path + program name)
+  * **argv[0]**: program invocation (path + program name)
-  * argv[1]: our maximum / upper bound
+  * **argv[1]**: our maximum / upper bound
 ====Simple argument checks====
@@ Line 221: / Line 235: @@
 And now we can proceed with the rest of our prime implementation.
+=====Allocating large arrays=====
+Being new to arrays, you may not know it yet, but there is an upper bound to how big you can declare an array at **compile time**.
+That is, using the conventional array declaration:
+<code c>
+data_type arrayname[size];
+</code>
+It is likely dependent on some combination of the execution environment (32-, 64-bit?) and the compiler, but in practice I've found things generally get unhappy if we try to request array sizes at some point beyond 1-4million elements (which makes sense, most processes in modern operating systems allocate a default stack size of 4-8MiB... if a short int is 2 bytes, how many consecutive short ints before you hit 4MiB?)
+As we'll be needing array sizes considerably larger than this for the project (will we? If I could drop a hint: **yes, we will**), how do we get around this?
+The answer: **runtime memory allocation**
+We can allocate memory at run-time, which gives us the benefit of populating variables and performing equations to derive more specific values. This is also a rather powerful programming technique/ability to deploy in more complex programs, so keep it handy in your toolkits.
+To do so, we ignore the fake facade that is the array, and treat it like it actually exists to the computer: **a pointer**.
+So when you declare your array, instead of using the square bracket notation, do it as a pointer instead:
+<code c>
+datatype *array_name  = NULL;
+</code>
+THEN, later on in your program when it comes time to allocate the array, we use a memory allocation function, of which for our current purposes one of the following 2 could suit our needs:
+  * **malloc(size)**
+    * allocates **size** bytes and returns the address
+  * **calloc(count, size)**
+    * allocates count * size bytes and returns the address; it also will scrub the memory, making sure everything is set to zero (**malloc()** does not do this; **malloc()** is also faster because of this, something to keep in mind to differentiate the two).
+So, if we wanted a 32768 element integer array, to show examples allocating with each function (you'd obviously only use one, whichever best fit your usage scenario):
+<code c>
+int *array_name  = NULL;
+// using malloc()
+array_name = (int *) malloc (sizeof(int) * 32768);
+// using calloc()
+array_name = (int *) calloc (32768, sizeof(int));
+</code>
+What else is going on here? What's with the parenthesis and the integer pointer?
+That's a typecast, and is a way of telling the compiler to contort data IN THAT INSTANCE to a certain type (because it is a different type, other than what we want).
+As it turns out, **malloc()** and **calloc()** both return //raw memory//, which in C is manifested as type **<nowiki>void *</nowiki>**; if our array is an integer pointer, we should be nice and cast it (apply the rules of an integer pointer to the raw memory, allowing the assignment to take place without the compiler whining-- some compilers, depending on settings in place, may whine more than others).
+With this, we can get around the compile time array limits, because by allocating memory at runtime, we're getting additional memory given to us, vs. trying to fit within the default initial allotment.
+You should then be able to access it using regular array notation, or my preference: pointer arithmetic.
+<code c>
+// C array syntax for accessing 3rd element of array:
+array_name[2]
+// C pointer arithmetic syntax for accessing 3rd element of array:
+*(array_name+2)
+</code>
+=====Approximating array size=====
+The nature of utilizing an array for the sieves, as you will likely discover quickly, is that the sheer quantity of elements needed increments drastically as the desired quantity goes up.
+For example, if we were seeking the first 32 primes:
+<cli>
+lab46:~/src/cprog/pnc2$ ./primebrk 32 1
+3 5 7 11 13 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
+</cli>
+... 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-- 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.
+So how do we get around this? I propose a combination of accepting knowledge from a more aware source (me), and a little algebraic ingenuity. Let's hack ourselves an array size equation! (Do I hear a "heck yeah!" ? "HECK YEAH!")
+First, you can actually produce a lot of this data, from your **pnc1** programs (technically **pnc0** as well, but you'll be waiting a whole heck of a lot longer).
+Let's take one of the purportedly best-running programs from **pnc1** (**primebrksrtoptodd**) and contort it into giving us the information that we need.
+With a little bit of UNIX shell magic (again, I'm not expecting you to know this, so I'm just giving it to you, but from the abstract/conceptual level, you should be able to recognize things here like loops and output statements, and with some informed knowledge of shell syntax, see variables as well), we have the following:
+<code bash 1>
+# clear the screen
+clear
+# loop for a powers of 2 progression 32-4194304 (inclusive)
+for((qty=32; qty<=4194304; qty*=2)); do
+    # display the quantity lead-in information
+    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)
+    # display it, along with calculating its approximate multiplier
+    printf "%8s (x%s)\n" "${value}" $(echo "(${value}/${qty})+1" | bc -q)
+done
+</code>
+We start with **qty** of 32, as that is the default starting point of **primerun** (so why not; makes sense to work with what we've got). But there's still an unknown: the //MAXIMUM// quantity we'll need to deal with, especially in relation to primerun (focus on primerun execution, not to infinity). This is less available to you, short of just guessing some possible maximum.
+I'm going to drop a hint: you'll very likely not be going beyond a quantity of **4194304** (at least with a primerun cut-off limit of 2 seconds), so use THAT as your upper bound of quantity, and that is why I use that number in the shell script given above.
+You don't have to worry about running said shell script, as the output is right here:
+<cli>
+[     32]      32th prime:      131 (x5)
+[     64]      64th prime:      311 (x5)
+[    128]     128th prime:      719 (x6)
+[    256]     256th prime:     1619 (x7)
+[    512]     512th prime:     3671 (x8)
+[   1024]    1024th prime:     8161 (x8)
+[   2048]    2048th prime:    17863 (x9)
+[   4096]    4096th prime:    38873 (x10)
+[   8192]    8192th prime:    84017 (x11)
+[  16384]   16384th prime:   180503 (x12)
+[  32768]   32768th prime:   386093 (x12)
+[  65536]   65536th prime:   821641 (x13)
+[ 131072]  131072th prime:  1742537 (x14)
+[ 262144]  262144th prime:  3681131 (x15)
+[ 524288]  524288th prime:  7754077 (x15)
+[1048576] 1048576th prime: 16290047 (x16)
+[2097152] 2097152th prime: 34136029 (x17)
+[4194304] 4194304th prime: 71378569 (x18)
+</cli>
+What we have is the following:
+  * first column is the specified quantity we are going to (as instantiated by primerun; I just have us doing a simple powers of 2 progression)
+  * the next column (the N-th prime), is the last prime in that quantity sequence (131 IS the 32nd prime, starting from 2)
+  * the last column, the xNUMBER, is the approximate multiplier we get by dividing the N-th prime by the quantity (and taking the ceiling (I just added one, since we're doing integer division and it'll truncate anyway), since it likely will NOT be a clean division)
+So from the data given above, we can see that a rough approximation of space needed for 32 primes would be <nowiki>32*5</nowiki> or 160 elements (131 falls nicely into 160).
+For 1024 we have a multiplier of 8 (<nowiki>1024*8</nowiki> = 8192, which 8161 safely fits into).
+Okay, so we've got some raw numbers, we know the array size needed for the smallest quantity (<nowiki>32*5</nowiki>), we also know the array size needed for the likely largest quantity (<nowiki>4194304*18</nowiki>). So how do we handle the intermediaries?
+As you can see, there is no a clean progression at play here, so no simple patterns we can play off of. I offer a few suggestions (and for the purposes of this project, any are acceptable):
+  * just go with the max size (x18): **<nowiki>array_size = qty * 18;</nowiki>**
+  * deploy some **if()** statements and do a stepped progression.
+For example, we see that since our max multiplier is 18, what if we did some factoring of 18? Say: 6, 12, 18?
+We could rig up something like this:
+<code c>
+if (qty <= 128)
+    array_size = qty * 6;
+else if (qty <= 32768)
+    array_size = qty * 12;
+else
+    array_size = qty * 18;
+</code>
+In general, though, this is just a mild annoyance in our quest to implement the sieve of Eratosthenes, so if you just hard code an 18, while certainly dirty, will get the job done for our current purposes (I will most certainly NOT hold it against you).
+Make sense? Hopefully. And moreso, if you've been able to follow this, it is also indicative of your general level of comprehension: if you understand the overall problem, the specific issue, and can interact conceptually, that makes you a better problem solver/Computer Scientist/programmer.
+And please, ASK QUESTIONS if something doesn't make sense.
 =====Timing=====
@@ Line 280: / Line 461: @@
 <cli>
-lab46:~/src/cprog/pnc2$ ./primesieveoferat 90
+lab46:~/src/cprog/pnc2$ ./primesoe 32 1
-3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89
+3 5 7 11 13 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
 .000088
 lab46:~/src/cprog/pnc2$
@@ Line 288: / Line 469: @@
 The execution of the programs is short and simple- grab the parameters, do the processing, produce the output, and then terminate.
-====Performance changes====
+Based on specifications, it should also be able to do the following (override quantity with lower/upper bounds):
-You may notice a change with the sieves as compared to the other algorithms you've implemented with respect to performance- there will like be a lower bound of performance, ie you have to exceed a certain threshold before the algorithm truly enters its power band.
-=====Check Results=====
+<cli>
-If you'd like to compare your implementations, I rigged up a script called **primerun** which you can run.
+lab46:~/src/cprog/pnc2$ ./primesoe 48 1 4 18
+7 11 13 17
+.000080
+lab46:~/src/cprog/pnc2$
+</cli>
-In order to work, you **MUST** be in the directory where your previous prime programs are. What I do is symlink the sources or copy the binaries into my current directory (pnc2), so I both have access to everything, but everything is still categorized per project.
+And (shift the lower bound, but still count out 32 primes):
-I'm not yet posting my primerun results; if you implement these correctly the results should speak for themselves.
 <cli>
-lab46:~/src/cprog/pnc2$ primerun
+lab46:~/src/cprog/pnc2$ ./primesoe 32 1 16
-COMING SOON
+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
+.000087
 lab46:~/src/cprog/pnc2$
 </cli>
-For evaluation, each test is run 4 times, and the resulting time is averaged. During development, I have it set to only run each test once.
+And of course the same for the 3 variants, and the same error message reporting if invalid values are given.
+====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.
+=====Check Results=====
+To verify your program's correctness and view your implementation's performance, **primerun** will recognize the indicated program names listed above.
+I'll hold off from posting actual primerun output; I want you to see the results without any expectations. Do know that the arrangement of programs (from left to right) is in order of worst to best performance based on my implementations.
-If the runtime of a particular prime variant exceeds an upper threshold (likely to be set at 2 seconds), it will be omitted from further tests, and a series of dashes will instead appear in the output.
+If/when the runtime of a particular prime variant exceeds an upper threshold (likely to be set at 2 seconds), it will be omitted from further tests, and a series of dashes will instead appear in the output.
 If you don't feel like waiting, simply hit **CTRL-c** and the script will terminate.
@@ Line 318: / Line 508: @@
   * Output must be correct, and match the form given in the sample output above.
   * Code must be nicely and consistently indented (you may use the **indent** tool)
-  * Code must utilize the specifications/algorithm(s) presented above.
+  * Code must utilize the algorithm(s) presented above.
-    * **primeopt.c**
+    * **primesoe.c**
-    * **primesieveoferat.c**
+    * **primesoeodd.c**
-    * **primesieveofsund.c**
+    * **primesoesrt.c**
+    * **primesoesrtodd.c**
   * Code must be commented
     * have a properly filled-out comment banner at the top
@@ Line 333: / Line 524: @@
 <cli>
-$ submit cprog pnc2 primeopt.c primesieveoferat.c primesieveofsund
+$ submit cprog pnc2 primesoe.c primesoeodd.c primesoesrt.c primesoesrtodd.c
 Submitting cprog project "pnc2":
-    -> primeopt.c(OK)
+    -> primesoe.c(OK)
-    -> primesieveoferat.c(OK)
+    -> primesoeodd.c(OK)
-    -> primesieveofsund.c(OK)
+    -> primesoesrt.c(OK)
+    -> primesoesrtodd.c(OK)
 SUCCESSFULLY SUBMITTED
@@ Line 347: / Line 539: @@
 <code>
-:pnc2:final tally of results (52/0)
+:pnc2:final tally of results (78/0)
-*:pnc2:submit all programs with submit tool [1/0]
+*:pnc2:submit all programs correctly perform argument checking [2/2]
-*:pnc2:primeopt.c no negative compiler messages [2/0]
+*:pnc2:primesoe.c no negative compiler messages [2/2]
-*:pnc2:primeopt.c implements unique yet viable algorithm [4/0]
+*:pnc2:primesoe.c implements only specified algorithm [8/8]
-*:pnc2:primeopt.c adequate indentation and comments [3/0]
+*:pnc2:primesoe.c adequate indentation and comments [3/3]
-*:pnc2:primeopt.c output conforms to specifications [4/0]
+*:pnc2:primesoe.c output conforms to specifications [3/3]
-*:pnc2:primeopt.c primerun runtime tests succeed [4/0]
+*:pnc2:primesoe.c primerun runtime tests succeed [3/3]
-*:pnc2:primesieveoferat.c no negative compiler messages [2/0]
+*:pnc2:primesoeodd.c no negative compiler messages [2/2]
-*:pnc2:primesieveoferat.c implements only specified algorithm [4/0]
+*:pnc2:primesoeodd.c implements only specified algorithm [8/8]
-*:pnc2:primesieveoferat.c adequate indentation and comments [3/0]
+*:pnc2:primesoeodd.c adequate indentation and comments [3/3]
-*:pnc2:primesieveoferat.c output conforms to specifications [4/0]
+*:pnc2:primesoeodd.c output conforms to specifications [3/3]
-*:pnc2:primesieveoferat.c primerun runtime tests succeed [4/0]
+*:pnc2:primesoeodd.c primerun runtime tests succeed [3/3]
-*:pnc2:primesieveofsund.c no negative compiler messages [2/0]
+*:pnc2:primesoesrt.c no negative compiler messages [2/2]
-*:pnc2:primesieveofsund.c implements only specified algorithm [4/0]
+*:pnc2:primesoesrt.c implements only specified algorithm [8/8]
-*:pnc2:primesieveofsund.c adequate indentation and comments [3/0]
+*:pnc2:primesoesrt.c adequate indentation and comments [3/3]
-*:pnc2:primesieveofsund.c output conforms to specifications [4/0]
+*:pnc2:primesoesrt.c output conforms to specifications [3/3]
-*:pnc2:primesieveofsund.c primerun runtime tests succeed [4/0]
+*:pnc2:primesoesrt.c primerun runtime tests succeed [3/3]
+*:pnc2:primesoesrtodd.c no negative compiler messages [2/2]
+*:pnc2:primesoesrtodd.c implements only specified algorithm [8/8]
+*:pnc2:primesoesrtodd.c adequate indentation and comments [3/3]
+*:pnc2:primesoesrtodd.c output conforms to specifications [3/3]
+*:pnc2:primesoesrtodd.c primerun runtime tests succeed [3/3]
 </code>

Lab46 Wiki

User Tools

Site Tools

Differences

Page Tools