Differences

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

--- notes:discrete:fall2022:projects:cnv2 [2022/11/05 01:31] – [ARRAY-BASED PRIME FACTOR] hcordell
+++ notes:discrete:fall2022:projects:cnv2 [2022/11/09 18:27] (current) – [SIEVE OF ERATOSTHENES] gsuber
@@ Line 5: / Line 5: @@
 ====ARRAY-BASED PRIME FACTOR====
-Focused only on prime numbers
+For the array optimisation, we will be using an array to aid us in the finding of primes. For the size of the array, it is recommended to reserve space equivalent to 1/3 of the range (assume that we are operating on range rather than quantity). The way this works is that when we find a prime number, we will store it in the array, and then when testing a value for being prime we will test it against our array contents rather than an incrementing value. If the value is not divisible by any of the values in our array, then it must be prime. For initialisation, it is recommended to put 2 in the array from the get-go (assume we are starting at 2). Note that while it is possible and recommended that the array optimisation coexist with the other optimisations, it is acceptable to have array as a standalone optimisation.
-Additional optimization level
-Make an array, and store the prime numbers as they are discovered. Then only check your test number against those prime numbers.
-\*\*I will fix these notes later - Ash
 ====SIEVE OF ERATOSTHENES====
 The sieve only works with prime numbers, you might find it easier just to create a separate file that contains the code for your sieve of eratosthenes. If you do, add your filename to the end of "BIN = $(PROJ)" inside of the makefile. Example: if you have a file named sieve.c, your new Makefile should read "BIN = $(PROJ) sieve". You can test if you did it right by running **make** and it will show sieve.c as well as your cnv2.c file.
@@ Line 20: / Line 15: @@
 You have a populated array starting from your checking value to your upper bound.
-You will cross out all other numbers that are divisible by the number you are checking.
+You will cross out all other numbers that are divisible by the number you are checking (for example if you start with 2, it will cross off 4, 4+2, 6+2, 8+2...(n+2), where (n+2) < = max. Also, one way you can "cross off" the numbers is by creating and initializing a second bool array...This is a helpful way to only display values in your array that are prime numbers.
 This will reduce the numbers you will be checking. Afterwards, move to the your checking number to the next number that is not a crossed out number, and test if that is a prime. If it is, remove that number from the list of available numbers, until you reach the upper bound. Repeat this process until either your quantity or upper bound is reached.
@@ Line 35: / Line 30: @@
 *For anybody interested in editing the wiki page, here is the dokuwiki user guide: https://www.dokuwiki.org/wiki:syntax#basic_text_formatting -Ash
 =====PROGRAM=====
+If you create a second source file for your sieve, you can include it in the makefile by adding the following line:
+<code>
+BIN = $(PROJ) <name of sieve file, without the .c>
+</code>
+Add it below the line that says:
+<code>
+BIN = $(PROJ)
+</code>
+For example, if your file is named sieve.c:
+<code>
+BIN = $(PROJ)
+BIN = $(PROJ) sieve
+</code>
 =====OUTPUT SPECIFICATIONS=====
+New functions should output prime numbers, separated by newline characters. This will largely follow the format of the previous iterations of cnv (cnv0, cnv1).
 =====VERIFICATION=====
+Similar to the other cnvX projects, there is no verification script, or unit test for you to test against. However, cnv2 only deals with prime numbers, so you can test the output against a list of prime numbers. Also, your new optimization, the array, should be consistently faster than the non-optimized version of the same parameters. The sieve should blow the times out of the water and be extremely quick.

Lab46 Wiki

User Tools

Site Tools

Differences

Page Tools