Lab46 Wiki

CNV1 is an introduction to program and algorithm optimization. We will be revisiting our cnv0 program, and we will make it harder, better, faster, and stronger.

There are 5 levels of optimization that could potentially be called upon simultaneously, with some exceptions.

• 0 none
• 1 break
• 2 odds
• 4 map
• 8 sqrt
• 16 approx sqrt

The numbers on the left represent binary positions.

Recall binary numbers and their position values.

0   0  0  0  0 0 0 0
128 64 32 16 8 4 2 1

You may take “optimizations” as a program argument or use an environment variable with getenv.

The optimizations should be a single argument or environment variable, for example the optimization argument of 19 would equal the following optimizations: 16 goes into 19, so approx sqrt would be activated & 2 goes into 19 - 16, so odds would be enabled & finally, 1 goes into 19 - 16 - 2, so the break optimization would be enabled.

• Break→Stop checking once you have determined that the value is not of the correct n-ary value
  
• Odds→Since all prime numbers beyond 2 are odd, there is no need to check whether or not the evens are prime
  
• Map→Only check numbers that lay upon the (6n±1) equation
  
• Sqrt→You only need to check up to and including the square root of the value being checked to discover half of all possible factor pairs
  
• Approx sqrt→Same as sqrt, but without the sqrt function from the math library. Instead run a rough sqrt point that grows as the value checked does.

* 6n±1: This formula defines all prime numbers above 3. Every prime number follows the 6n±1 equation where n is any integer, 1 or greater. All prime numbers follow this pattern, although the resulting number will not necessarily be a prime number.

For the approximate square root functionality you will have a “square root point”, this point is the approximation of the square root for the number you're checking.

Start with this point equal to 2. The point will increase when ( number to check > point * point ).

For example, when the number to check is 10, the point will be 3 (10 > 3*3), and therefore the approximate square root of 10 is 3.

The starting value of 2 should be used as the approximation for numbers 2-8 however when the number to check reaches 9, (9 > 2*2), so the point will increase to 3.

Examples:

• sqrt of 2-8 is 2
• sqrt of 9-15 is 3
• sqrt of 16-24 is 4
• sqrt of 25-35 is 5
• sqrt of 36-48 is 6
• etc…

With map, you are pretty much only doing the calculations if the valueToCheck is equal to the value given from the equation 6n(+/-)1, where n is a number > 1. If it is not equal to this, then go to the next value rather than doing the calulations.

With break, you are aiming to reduce the program run time by breaking out of the check when the total factors of the current number exceeds that of the given nary value. This will drastically reduce the time, especially if you are checking larger numbers with a small nary value.

Odds and Map are only to be used during nary 1 (when dealing with prime numbers).

*Our task is to ask questions on Discord or in class and document our findings on this wiki page collaboratively, regarding the functionality of this project.

*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 should output the same as cnv0. The only difference is using the optimizations, your optimized version should be for the most part, faster than the cnv0 or zero optimization equivalent of the same operation.

Similar to cnv0, there is no makefile. However, output doesn't change for this program, only the time. To verify, make sure your times when using optimizations are less than the times without optimizations.