PROJECT: Prime Number Computation (PNC1)

OBJECTIVE

Continue exploring algorithm/implementation comparison and optimization with respect to various approaches of computing prime numbers.

TASK

Add to your two separate, independent programs, one in Vircon32 C, and other in Vircon32 assembly, functionality that:

implements individual and combined functionality for the following optimizations (both in C and assembly):
- odds: above 2, does odds-only processing (both number and factor check)
- break: breaks from trial division/brute force when a viable factor is found (break on composite)
- sqrt: only processes up through the square root point of the number being evaluated
- possibilities here include the 3 identified variants (odds, break, sqrt) along with their combinations (odds+break, odds+sqrt, break+sqrt, odds+break+sqrt)
collects the same timing data with common workloads to the brute force variants from pnc0
new variants added to the runtime graph you made in pnc0, adjusting and re-running pnc0 variants to allow for a consistent presentation of information
you may consider a lower upper-bound runtime threshold for the pnc1 variants (perhaps somewhere between 2 and 8 seconds, compared to the 16 seconds for pnc0).
- be sure to use distinctive colors/patterns to distinguish items on the graph (again, line graph is a recommended choice)

REFERENCE

The following are reference screenshots of what your implementations should approximate.

PNC1

C implementation

EDIT

You will want to go here to edit and fill in the various sections of the document:

https://lab46.g7n.org/notes/comporg/spring2025/projects/pncX

PNCX

algorithm: brute force / trial-by-division

variant: naive

The naive implementation is our baseline: implement with no awareness of potential tweaks, improvements, or optimizations. This should be the worst performing when compared to any optimization.

START TIMEKEEPING
NUMBER: FROM 2 THROUGH UPPERBOUND:
    ISPRIME <- YES
    FACTOR: FROM 2 THROUGH NUMBER-1:
        SHOULD FACTOR DIVIDE EVENLY INTO NUMBER:
            ISPRIME <- NO
    PROCEED TO NEXT FACTOR
    SHOULD ISPRIME STILL BE YES:
        INCREMENT OUR PRIME TALLY
PROCEED TO NEXT NUMBER
STOP TIMEKEEPING

Future Proofing

Print Subroutine

Printing Seconds

The amount of runtime a method takes can be measure in both cycle count and frame count. Since the cycle count resets every frame, frame count is needed for any time over 1/60th of a second

The Frame count can be added onto the cycle count to find a total time count. To do this the frame count needs to be multiplied by the number of cycles in a frame

Printing out the time can be separated into the whole portion and the fractional portion

The whole and fractional part can be found by dividing the cycle count by the amount of cycles in a unit of time (seconds for whole, milliseconds for fractional)

ADD FRAME TIME TO CYCLE TIME
DIVIDE THE CYCLE TIME BY THE CYCLES PER SECOND
PRINT THE WHOLE PORTION

MODULATE THE CYCLE TIME BY THE CYCLES PER SECOND
DIVIDE THE CYCLE TIME BY THE CYCLES PER MILLISECOND
   ADD ZEROS TO THE LEFT UNTIL STRING IS THE CORRECT LENGTH
PRINT THE FRACTIONAL PORTION

variant: break on composite (BOC)

variant: odds-only processing

variant: sqrt point

How to Sqrt

variant: break+odds

variant: break+sqrt

variant: break+odds+sqrt

ALGORITHM: sieve of eratosthenes

variant: baseline soe

START TIMEKEEPING
NUMBER: FROM 2 THROUGH UPPERBOUND:
    SHOULD THE NUMBER SLOT BE TRUE:
        VALUE AT NUMBER IS PRIME, INCREMENT TALLY
        MULTIPLE: FROM NUMBER+NUMBER THROUGH UPPERBOUND:
            VALUE AT MULTIPLE IS NOT PRIME
            MULTIPLE IS MULTIPLE PLUS NUMBER
        PROCEED TO NEXT MULTIPLE
    INCREMENT NUMBER
PROCEED TO NEXT NUMBER
STOP TIMEKEEPING

variant: sieve of eratosthenes with sqrt trick (soes)

START TIMEKEEPING
NUMBER: FROM 2 THROUGH NUMBER*NUMBER<UPPERBOUND:
    SHOULD THE NUMBER SLOT BE TRUE:
        VALUE AT NUMBER IS PRIME, INCREMENT TALLY
        MULTIPLE: FROM NUMBER*NUMBER THROUGH UPPERBOUND:
            VALUE AT MULTIPLE IS NOT PRIME
            MULTIPLE IS MULTIPLE PLUS NUMBER
        PROCEED TO NEXT MULTIPLE
    INCREMENT NUMBER
PROCEED TO NEXT NUMBER
STOP TIMEKEEPING

timing

Array in ASM

wedge pnc1 runtimes

Darkmoon pnc0 runtimes

Darkmoon pnc1 runtimes

Darkmoon pnc2 runtimes

TommyK pnc0 runtimes

TommyK pnc1 runtimes

TommyK pnc2 runtimes

BrandonD pnc0 runtimes

BrandonD pnc1 runtimes

BrandonD pnc2 runtimes

SUBMISSION

To be successful in this project, the following criteria (or their equivalent) must be met:

Project must be submit on time, by the deadline.
- Late submissions will lose 33% credit per day, with the submission window closing on the 3rd day following the deadline.
Executed programs must display in a manner similar to provided output
- output formatted, where applicable, must match that of project requirements
Processing must be correct based on input given and output requested
Output, if applicable, must be correct based on values input
Code must be nicely and consistently indented
Code must be consistently written, to strive for readability from having a consistent style throughout
Code must be commented
- Any “to be implemented” comments MUST be removed
  - these “to be implemented” comments, if still present at evaluation time, will result in points being deducted.
  - Sufficient comments explaining the point of provided logic MUST be present
No global variables (without instructor approval), no goto statements, no calling of main()!
Track/version the source code in your lab46 semester repository
Submit a copy of your source code to me using the submit tool by the deadline.

Submit Tool Usage

Let's say you have completed work on the project, and are ready to submit, you would do the following:

lab46:~/src/SEMESTER/DESIG/PROJECT$ submit DESIG PROJECT file1 file2 file3 ... fileN

You should get some sort of confirmation indicating successful submission if all went according to plan. If not, check for typos and or locational mismatches.

RUBRIC

I'll be evaluating the project based on the following criteria:

286:pnc1:final tally of results (286/286)
*:pnc1:submitted C and assembly implementations [26/26]
*:pnc1:each implementation builds cleanly [26/26]
*:pnc1:output conforms to specifications [26/26]
*:pnc1:processing is correct, and to specifications [26/26]
*:pnc1:working break on composite optimization [26/26]
*:pnc1:working odds only processing optimization [26/26]
*:pnc1:working sqrt factor cap optimization [26/26]
*:pnc1:all variants and combinations thereof operational [26/26]
*:pnc1:graph produced from timing data produced [26/26]
*:pnc1:graph posted to discord and documentation page [26/26]
*:pnc1:timing data is taken out to at least 4 decimal places [26/26]

Pertaining to the collaborative authoring of project documentation

each class member is to participate in the contribution of relevant information and formatting of the documentation
- minimal member contributions consist of:
  - near the class average edits (a value of at least four productive edits)
  - near the average class content change average (a value of at least 1024 bytes (absolute value of data content change))
  - no zero-sum commits (adding in one commit then later removing in its entirety for the sake of satisfying edit requirements)
- adding and formatting data in an organized fashion, aiming to create an informative and readable document that anyone in the class can reference
- content contributions will be factored into a documentation coefficient, a value multiplied against your actual project submission to influence the end result:
  - no contributions, co-efficient is 0.50
  - less than minimum contributions is 0.75
  - met minimum contribution threshold is 1.00

Additionally

Solutions not abiding by spirit of project will be subject to a 50% 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 or otherwise maintaining consistency in code style and presentation will be subject to a 25% overall deduction
Solutions not organized and easy to read (assume a terminal at least 90 characters wide, 40 characters tall) are subject to a 25% overall deduction
Individuals who have not participated at least 50% will be subject to a 50% overall deduction.

Lab46 Wiki

User Tools

Site Tools

Sidebar

Table of Contents