User Tools

Site Tools


notes:comporg:spring2025:projects:pncx

This is an old revision of the document!


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

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

notes/comporg/spring2025/projects/pncx.1744115273.txt.gz · Last modified: 2025/04/08 12:27 by tkastne1