Table of Contents

Corning Community College

CSCS2330 Discrete Structures

PROJECT: PRIME NUMBER FUN moar (PNF1)

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.

The algorithms you are to implement are during program runtime can select include the following trial-by-division-based approaches:

Time how long it takes to execute (displaying elapsed time for the run at its conclusion; this is useful for comparisons), and display this result, especially in relation to the work load and algorithm used.

Note that the “break on composite”, “odds-only”, and “square-root” optimizations can be selectively combined for a program runtime.

That means, your program needs to support running the following modes (selectable by the user at program start):

But, you will want to arrange your logic so you aren't supporting eight distinct operating modes, containing mostly redundant code. Instead: ONE routine for prime processing, bringing various optimizations online or not, depending on initial selection.

Additionally, the entire class will be participating in documenting and filling out this project page. It is the responsibility of EACH class member to:

Background

TIC80

TIC80 works on a system of carts. The carts present on a system can be listed via a familiar call to `ls`, or, at a more involved level, the system folder which TIC80 uses to store its data can be accessed via the `folder` command in the TIC80 terminal. A new cart can be made with the `new` command, and the loaded cart can be saved via the `save` command. The code content of these cards after `load`ing them can be accessed by pressing [ESC] from the terminal, opening the included basic IDE equipped with a code, sprite, map, sfx, and music editor.

The code editor is relatively simple: 64KB are allotted for a script written in any of: Lua, JavaScript, Moonscript, Wren, Fennel, and Squirrel. External packages may also be used to allow for the usage of more languages. The first step in writing a basic program in TIC80 is to supply a series of comments (formatted in the choice language) which allow TIC80 to ascertain four pieces of metadata, as in: 

-- title: PrintThing(TM)
-- author: Wedgie
-- desc: Print.. something.
-- script: lua

for Lua, or: 

// title: PrintThing(TM)
..
// script: js

for JavaScript, and so on.

Once a language is selected, a developer will need to include a `TIC()` function. This is essentially the “main” function as many other programs would have, and is called automatically once the `run` command is issued on the cart 60 times per second. This can be relied on to provide synchronous 60fps display and physics or other necessary mechanics. Additionally, the `spr()`, `print()`, and `cls()` functions will prove essential. The `spr()` (Sprite) function is used to call upon sprites designed in the sprite editor and place them at some location on-screen. `print()` (Print) is more clear: this will print text directly to screen in the default font. It should be noted that the print function can also accept additional arguments for text position, size, and color. `cls` (Clear Screen) simply clears the screen of all pixel data and resets to blank.

Specifications

Process

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

Before we can jump into how to program our prime number detection algorithm, we must understand the basic rules of prime numbers.

Prime Numbers Must Be:

With your knowledge of programming and the rules of prime numbers, you should be able to make a detection algorithm now! There are different computational methods for figuring out the primality of a number, we will take a look at one of the simplest ones first (more may be added in the future to this page).

Trial-By-Division Algorithm

One of the most basic methods of checking the primality of a number, this method relies on dividing a given number by the numbers in a set range. This is to see if any numbers in that range divide the given number cleanly; no remainders exist in the mathematical output. Clean division is a sign of a composite number.

Let's assume we have an integer, n, in order to see if n is a prime number we should first determine our lower and upper bounds for the division test(s):

Both of these bounds may be confusing, let me explain…

For our lower bound, we most definitely want to start on the lowest number possible. Since we know that the potential factors for our integer, n, must be natural/counting numbers that means the lowest we could try to start at is 0. Is there an issue with this? Yes. Perhaps we can start at 1? No.

Hopefully, you understand why starting at 0 for division tests would not be such a good idea. Starting at 1 would be superfluous; everything is divisible by 1. At this point, having our lower bound set to 2 ensures no issues and is the lowest we can go for our lower bound.

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:

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.
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

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

References

https://github.com/nesbox/TIC-80/wiki

https://github.com/nesbox/TIC-80/wiki/Cheatsheet

https://www.lua.org/manual/5.3/

Submission

I'll be looking for the following: 

78:pnf1:final tally of results (78/78)
*:pnf1:no errors, program runs in TIC-80 [13/13]
*:pnf1:user can specify lower and upper bounds at runtime [13/13]
*:pnf1:algorithm selection is implemented and functional [13/13]
*:pnf1:specified algorithms are implemented and functional [13/13]
*:pnf1:timing information is displayed [13/13]
*:pnf1:project page contributions as per project specifications [13/13]

Additionally: