Lab46 Wiki

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
<WRAP centeralign round box>
<WRAP><color red><fs 200%>Corning Community College</fs></color></WRAP>
<WRAP><fs 150%>CSCS2330 Discrete Structures</fs></WRAP>
</WRAP>

======PROJECT: PRIME NUMBER FUN intro (PNF0)======

=====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 algorithm you are to implement is the trial-by-division brute force (naive: NO optimizations)

Time how long it takes to execute (displaying elapsed time for the run at its conclusion; this is useful for comparisons).

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

  * ask copious, clarifying questions (so you can better add content)
  * craft a coherent and organized document, with information located under pertinent headings
  * explain the fundamentals of the process, conceptual background, algorithmic approach, and you can even suggest particulars related to TIC-80 (certain functions that might prove useful- individual, unrelated snippets to do things like capturing time, or displaying text, etc.)
  * to get full credit, each individual that submits must perform no fewer than 4 changes to this document (as viewable from the wiki revision system). Failure to do so will result in documentation penalties being applied.

=====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:
<code>
-- title: PrintThing(TM)
-- author: Wedgie
-- desc: Print.. something.
-- script: lua
</code>
for Lua, or:
<code>
// title: PrintThing(TM)
..
// script: js
</code>
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.

====Priminality====

=====Specifications=====

====Process====

As it is an intentionally minimally optimized (in a way, optimally suboptimal) method, going about this task will be relatively simple, relying on three major areas: **user interaction/input**, **prime checking**, and **visual output**. Chronologically, upon run, the program will execute essentially the following steps:

  - Request input
    - Store
  - Pass input to prime checker
    - Return True/False for Prime/Composite
  - Use return value of prime checker to determine output
    - If prime, positive output (e.g. rainbow/green/bright)
    - If composite, negative/neutral output (e.g. monochrome/red/dull)

====Input====

====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:
  * In the set of natural/counting numbers.
  * Greater than the number 1.
  * Factorable by only two natural/counting numbers: itself and 1.

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):
  * Lower bound: 2
  * Upper bound: <m>sqrt{n}</m>
     * If taking unoptimized route, upper bound can just be //n - 1//.

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.

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:
  * How can we test if a number divides cleanly by //n//?
     * Hint: remainder "%"
  * How can we implement a square root in our code for the upper bound?
  * How do we deal with testing the numbers 0 and 1?

====Display====

The `print` function can be used to print text on the screen, but it also returns the width of the text. For example, `local string=print("Hello, World!",0,0,12)` would not only print the text on the screen, but it would also give the local variable `string` a value equal to the width of "Hello, World!" in pixels. This is especially helpful if you want to display a sprite after a string, but you don't feel like counting out how much space you need manually.

Additionally, text can be appended to `print` alongside variables without the need for two separate lines of code/statements using `..`. For example, if you wanted to print "Times iterated: " and then a number contained within a variable, instead of doing two `print`s for the text and variable individually, you could do `print("Times iterated: "..variable,0,0,12)'.

The `time` function returns the current run-time of the program in milliseconds. This is useful in a variety of circumstances; having something happen at a specific timestamp, having things refresh at a certain interval, etc. For pnf0, specifically, expertly utilizing `print()` alongside `time()` would display the current run-time in seconds, which is a requirement.

=====References=====

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

http://lua-users.org/wiki/MathLibraryTutorial

=====Submission=====
To submit, provide your tic file using the **submit** tool on lab46.

I'll be looking for the following:

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

Additionally:
  * Solutions not abiding by **SPIRIT** of project will be subject to a 25% overall deduction
  * Solutions not utilizing descriptive why and how **COMMENTS** will be subject to a 25% overall deduction
  * Solutions not utilizing **INDENTATION** to promote scope and clarity will be subject to a 25% overall deduction
  * Solutions lacking **ORGANIZATION** and are not easy to read (within 90 char width) are subject to a 25% overall deduction
Lab46 Wiki

User Tools

Site Tools

Page Tools
