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

<code>
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
</code>


====variant: break on composite (BOC)====
just add a break; statement within your brute loop like so:

<code>
START TIMEKEEPING
NUMBER: FROM 2 THROUGH UPPERBOUND:
    ISPRIME <- YES
    FACTOR: FROM 2 THROUGH NUMBER-1:
        SHOULD FACTOR DIVIDE EVENLY INTO NUMBER:
            ISPRIME <- NO
            BREAK
    PROCEED TO NEXT FACTOR
    SHOULD ISPRIME STILL BE YES:
        INCREMENT OUR PRIME TALLY
PROCEED TO NEXT NUMBER
STOP TIMEKEEPING
</code>
====variant: odds-only processing====
Start at 3 and increment by two to get only odd numbers. Then add one to tally count to account for 2 like so:

<code>
START TIMEKEEPING
NUMBER: FROM 3 THROUGH UPPERBOUND:
    ISPRIME <- YES
    FACTOR: FROM 3 THROUGH NUMBER-1:
        SHOULD FACTOR DIVIDE EVENLY INTO NUMBER:
            ISPRIME <- NO
    PROCEED TO NEXT FACTOR BY TWO
    SHOULD ISPRIME STILL BE YES:
        INCREMENT OUR PRIME TALLY
PROCEED TO NEXT NUMBER BY TWO
ONCE UPPERBOUND IS REACHED ADD A ONE TO YOUR PRIME TALLY TO ACCOUNT FOR NOT STARTING AT TWO
STOP TIMEKEEPING
</code>
====variant: sqrt point====
Say you're using i for the outer loop and j for the inner loop, now rather that j < i you want j * j < = i
<code>
START TIMEKEEPING
NUMBER: FROM 2 THROUGH UPPERBOUND:
    ISPRIME <- YES
    FACTOR: FROM 2 * 2 THROUGH NUMBER-1:
        SHOULD FACTOR DIVIDE EVENLY INTO NUMBER:
            ISPRIME <- NO
    PROCEED TO NEXT FACTOR BY TWO
    SHOULD ISPRIME STILL BE YES:
        INCREMENT OUR PRIME TALLY
PROCEED TO NEXT NUMBER BY TWO
ONCE UPPERBOUND IS REACHED ADD A ONE TO YOUR PRIME TALLY TO ACCOUNT FOR NOT STARTING AT TWO
STOP TIMEKEEPING
</code>





====variant: break+odds====

<code>
START TIMEKEEPING
NUMBER: FROM 3 THROUGH UPPERBOUND:
    ISPRIME <- YES
    FACTOR: FROM 3 THROUGH NUMBER-1:
        SHOULD FACTOR DIVIDE EVENLY INTO NUMBER:
            ISPRIME <- NO
            BREAK
    PROCEED TO NEXT FACTOR BY TWO
    SHOULD ISPRIME STILL BE YES:
        INCREMENT OUR PRIME TALLY
PROCEED TO NEXT NUMBER BY TWO
ONCE UPPERBOUND IS REACHED ADD A ONE TO YOUR PRIME TALLY TO ACCOUNT FOR NOT STARTING AT TWO
STOP TIMEKEEPING
</code>
====variant: break+sqrt====
Same as sqrt but add a break
<code>
START TIMEKEEPING
NUMBER: FROM 2 THROUGH UPPERBOUND:
    ISPRIME <- YES
    FACTOR: FROM 2 * 2 THROUGH NUMBER-1:
        SHOULD FACTOR DIVIDE EVENLY INTO NUMBER:
            ISPRIME <- NO
            BREAK
    PROCEED TO NEXT FACTOR BY TWO
    SHOULD ISPRIME STILL BE YES:
        INCREMENT OUR PRIME TALLY
PROCEED TO NEXT NUMBER BY TWO
ONCE UPPERBOUND IS REACHED ADD A ONE TO YOUR PRIME TALLY TO ACCOUNT FOR NOT STARTING AT TWO
STOP TIMEKEEPING
</code>


====variant: break+odds+sqrt====

For this version, you will combine all three of the above into one process!
=====ALGORITHM: sieve of eratosthenes=====

====variant: baseline soe====

The sieve of Eratosthenes is one of the best algorithms for finding prime numbers, you may have noticed that up to this point all the code we have written has a complexity of O(n^2). The soe takes the next step and goes to O(nlog(log(n)).

Here is how the Sieve of Eratosthenes works:

First, you start with 2, and count up to your upper bound. For this example, let's say it is 40:

<code>
    2  3  4  5  6  7  8  9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
</code>

Then, you go through the list and remove multiples of 2. After that, you go to the next remaining number, which you now know is prime. Then, you remove multiples of that number, and so on.

To continue from above, 2 is a prime number, so you leave it alone, and remove any multiples of 2:

<code>
    2  3     5     7     9  
11    13    15    17    19  
21    23    25    27    29  
31    33    35    37    39  
</code>

Then, you go to the next number: 3. Now you know 3 is a prime number, so you can remove multiples of 3:

<code>
    2  3     5     7        
11    13          17    19  
      23    25          29  
31          35    37        
</code>

You go through the entire list, and when you get to the end, you are only left with prime numbers:

<code>
    2  3     5     7        
11    13          17    19  
      23                29  
31                37        
</code>

<code>
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
</code>

====variant: sieve of eratosthenes with sqrt trick (soes)====

<code>
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
</code>
=====timing=====


====wedge pnc1 runtimes====
<dataplot center linespoints smooth 600x400 xlabel="range" ylabel="time (s)">
1024 0.550 0.083 0.116 0.016 0.033 0.0 0.0 0.0
2048 2.233 0.300 0.516 0.066 0.133 0.016 0.016 0.0
4096 8.950 1.150 2.083 0.183 0.533 0.033 0.033 0.016
8192 35 4.200 8.383 0.533 1.966 0.100 0.116 0.050
</dataplot>
====cgrant9 pnc1 runtimes====
{{ :notes:fall2024:projects:pnc1.png?600 |}}

====VerbalGnat48's pnc1 runtimes====
{{ :notes:fall2024:projects:carter_pnc1.png?600 |}}

====MrVengeance's pnc1 runtimes====
{{ :notes:fall2024:projects:pnc1-graph.png?600 |}}
====XaViEr'S pnc1 runtimes====
{{ :notes:fall2024:projects:xavierspnc.png?600 |}}

====Cburling's pnc1 runtimes====
{{:notes:fall2024:projects:cb-pnc1.png?400|}}

====Blaize Patricelli pnc1 runtimes====
<dataplot center linespoints smooth 600x400 xlabel="range" ylabel="time (s)">
1024 0.483 0.083 0.033 0.17 0.033 0.0 0.017 0.0
2048 1.967 0.283 0.117 0.017 0.133 0.017 0.017 0.0
4096 7.867 1.017 0.467 0.05 0.467 0.05 0.017 0.017
8192 31.367 3.683 1.717 0.117 1.717 0.100 0.05 0.05
</dataplot>
Lab46 Wiki

User Tools

Site Tools

Page Tools
