User Tools

Site Tools


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

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

notes/comporg/spring2025/projects/pncx.txt · Last modified: 2025/04/24 06:02 by bdildine