Differences

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

--- haas:summer2017:cprog:projects:pnc2 [2017/07/07 23:53] – [Submission] wedge
+++ haas:summer2017:cprog:projects:pnc2 [2017/07/08 12:47] (current) – [Approximating array size] wedge
@@ Line 235: / 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 302: / Line 469: @@
 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
+7 11 13 17
+.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
+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>
+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.

Lab46 Wiki

User Tools

Site Tools

Differences

Page Tools