Lab46 Wiki

User Tools

Site Tools

You are here: start » notes » discrete » fall2021 » projects » pnf1
notes:discrete:fall2021:projects:pnf1

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
notes:discrete:fall2021:projects:pnf1 [2021/09/09 02:54] – Added trial-by-division method to page smalik3notes:discrete:fall2021:projects:pnf1 [2021/09/09 03:59] (current) – [Prime Detection Algorithm] mbrill1
Line 7: Line 7:
  
 =====Objective===== =====Objective=====
 +
 Using the TIC-80 fantasy console simulator on your pi, implement a program that visually displays a range of values (lower and upper bounds adjustable by the user) that colorfully displays whether each value is a **prime** or **composite** value. Using the TIC-80 fantasy console simulator on your pi, implement a program that visually displays a range of values (lower and upper bounds adjustable by the user) that colorfully displays whether each value is a **prime** or **composite** value.
  
Line 69: Line 70:
  
 An effective way of going about this project is to allow the prime detection algorithm to "step" once every frame. That is, by allowing the TIC() function to call the calculation of the number currently being assessed, greater functionality is easier to implement. For example, animations can be played simultaneously as the calculation occurs since the entire TIC() function is able to run without needing to wait for some checkPrime() or similar process to finish. Additionally, the various optimizations can be more consistently implemented from a user perspective since they will not affect the framerate nearly as drastically as if the entire algorithm was called during a single frame. An effective way of going about this project is to allow the prime detection algorithm to "step" once every frame. That is, by allowing the TIC() function to call the calculation of the number currently being assessed, greater functionality is easier to implement. For example, animations can be played simultaneously as the calculation occurs since the entire TIC() function is able to run without needing to wait for some checkPrime() or similar process to finish. Additionally, the various optimizations can be more consistently implemented from a user perspective since they will not affect the framerate nearly as drastically as if the entire algorithm was called during a single frame.
 +
 ====Prime Detection Algorithm==== ====Prime Detection Algorithm====
  
Line 96: Line 98:
  
 For our upper bound, we want to prioritize testing to what we //absolutely// must test. Testing all values until //n// would be highly inefficient. One important rule to remember is that one of the two factors generated from //n// will be less than or equal to the square root of //n//. Knowing this rule, testing numbers after the square root of //n// is pointless. For our upper bound, we want to prioritize testing to what we //absolutely// must test. Testing all values until //n// would be highly inefficient. One important rule to remember is that one of the two factors generated from //n// will be less than or equal to the square root of //n//. Knowing this rule, testing numbers after the square root of //n// is pointless.
 +
 +We must consider other options, optimizations, to implement. As our objective states, there are some more optimizations besides the ones written here. It is up to you to implement that given what has been written here.
  
 Now that you understand the general process of this algorithm, and what its lower and upper bounds should be, you can finally get into writing this algorithm. Here are a few concluding questions: Now that you understand the general process of this algorithm, and what its lower and upper bounds should be, you can finally get into writing this algorithm. Here are a few concluding questions:
Line 104: Line 108:
  
 ==Optional Functionality== ==Optional Functionality==
 +
 This can be relatively simply and familiarly implemented (at a high level) in the way that the **chmod** accepts permission codes. By assigning each optional optimization to a number (in binary terms, starting with 1, 2, 4, 8, 16, ...) and passing the set of selected optimizations as the sum of those selected numbers, the algorithm can handle, in a way of limited individual variables, optional functions. At runtime, these can be checked from greatest to least: if the options argument is a number greater than the number corresponding to the biggest number, perform that operation, and subtract that value from the argument, then move on to the next-biggest, and so on, until the final option.\\ This can be relatively simply and familiarly implemented (at a high level) in the way that the **chmod** accepts permission codes. By assigning each optional optimization to a number (in binary terms, starting with 1, 2, 4, 8, 16, ...) and passing the set of selected optimizations as the sum of those selected numbers, the algorithm can handle, in a way of limited individual variables, optional functions. At runtime, these can be checked from greatest to least: if the options argument is a number greater than the number corresponding to the biggest number, perform that operation, and subtract that value from the argument, then move on to the next-biggest, and so on, until the final option.\\
 In the case of Break, Odds, and Square Root methodology, break can be 1, odds can be 2, and sqrt can be 4. If the input is then sqrt and odds, for example, and argument input would be 6. If nothing is selected, argument input would be 0, causing the brute force method. In the case of Break, Odds, and Square Root methodology, break can be 1, odds can be 2, and sqrt can be 4. If the input is then sqrt and odds, for example, and argument input would be 6. If nothing is selected, argument input would be 0, causing the brute force method.
  
 ==If Statements== ==If Statements==
 +
 An if statement can be used to accept two conditions instead of just one. In Lua, this is accomplished with `and.` As an example, `if a==2 and b==3 then` only performs an action if a=2 and b=3. This is useful for having multiple menus and deciding which sub-menu to display. It can also be used in conjunction with Optional Functionality. An if statement can be used to accept two conditions instead of just one. In Lua, this is accomplished with `and.` As an example, `if a==2 and b==3 then` only performs an action if a=2 and b=3. This is useful for having multiple menus and deciding which sub-menu to display. It can also be used in conjunction with Optional Functionality.
 +
 +
 +====Break On Composite Algorithm====
 +
 +The idea of the "break on composite algorithm", is very similar to the brute force algorithm. It still incorporates the trial by division idea. Lets say you are checking to see if a number is prime or composite using the trial by division algorithm. That means you are dividing said number by every number between 2 and said number. If it so happens that you come across a number that divides into your number with no remainder, then you would want your program to instantly see that your number is composite. Then move on to the next number in the range of numbers provided by the user.
 ====Display==== ====Display====
  
 =====References===== =====References=====
 +
 https://github.com/nesbox/TIC-80/wiki https://github.com/nesbox/TIC-80/wiki
  
Line 117: Line 129:
  
 https://www.lua.org/manual/5.3/ https://www.lua.org/manual/5.3/
 +
 =====Submission===== =====Submission=====
 +
 I'll be looking for the following: I'll be looking for the following:
  
notes/discrete/fall2021/projects/pnf1.1631156066.txt.gz · Last modified: 2021/09/09 02:54 by smalik3

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