Differences

This shows you the differences between two versions of the page.

--- notes:comporg:spring2024:projects:pncx [2024/04/17 20:50] – [Josiah pnc0 runtimes] jwieland
+++ notes:comporg:spring2024:projects:pncx [2024/04/24 23:18] (current) – [dmorey2 pnc2 runtimes] dmorey2
@@ Line 100: / Line 100: @@
 ====variant: break+odds====
+Combining the Break method with the Odds optimization further enhances the efficiency of the prime number generation algorithm. The Break method ensures that after finding a factor, the algorithm breaks out of the loop, thus eliminating unnecessary iterations and conserving computational resources.
+By considering only odd numbers and incorporating the Break method, the Break+Odds optimization significantly reduces the computational load. It starts with 3 as the first odd prime number and subsequently generates and tests odd numbers for primality. With the Break method in place, the algorithm terminates the inner loop as soon as a factor is found, leading to a faster and more efficient process of identifying prime numbers.
+The implementation follows the structure of the brute force algorithm but with the additional optimization of skipping even numbers and breaking out of the loop upon finding a factor. This combined approach drastically improves the performance of the prime number generation process.
 ====variant: break+sqrt====
+Integrating the Break method with the Square Root optimization further refines the prime number generation algorithm. By breaking out of the loop after finding a factor and limiting the search space to the square root of the current number, unnecessary iterations are avoided, resulting in a more streamlined and efficient algorithm.
+The Break+Square Root optimization leverages the approximate square root to determine the upper limit of the inner loop while also incorporating the Break method to terminate the loop early upon finding a factor. This combined approach reduces both the computational complexity and runtime of the algorithm.
+The implementation follows a similar structure to the brute force algorithm, with the addition of both the Square Root and Break optimizations. By iterating up to the square root of the current number and breaking out of the loop upon finding a factor, the algorithm achieves significant performance improvements compared to the naive approach.
 ====variant: break+odds+sqrt====
-====variant: sieve of eratosthenes (soe)====
+Break+odds+Sqrt is a culmination of all that you have done up to this point, so lets list out the requirements over the normal brute force.
+  - Use sqrt/approximate square root to limit how far up the inner for loop goes.
+  - Start at 3 for both for loops, and increment both loop counter by 2.
+  - As soon as it hits a value that changes if it is counted as a prime, it breaks.
+This is what your c implementation should look like. This piece of code utilizes the approximate square root, which you can see by the j*j.
+<code c>
+  bool isprime=true;
+  int primecounter=0;
+  for(int i=3; i<n; i+=2){
+      isprime=true;
+      for(int j=3;j*j<=i; j+=2){
+          if(i%j==0){
+              isprime=false;
+              break;
+          }
+      }
+      if(isprime){
+          primecounter++;
+      }
+  }
+  primecounter++;
+</code>
+=====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>
+  3  4  5  6  7  8  9 10
+12 13 14 15 16 17 18 19 20
+22 23 24 25 26 27 28 29 30
+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>
+  3     5     7     9
+    13    15    17    19
+    23    25    27    29
+    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>
+  3     5     7
+    13          17    19
+    25          29
+          35    37
+</code>
+You go through the entire list, and when you get to the end, you are only left with prime numbers:
+<code>
+  3     5     7
+    13          17    19
+                29
+                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=====
 A potential example using the dokuwiki dataplot plugin for graphing data:
+One easy way to get the timing in a consistent way is to have two functions to call, one to start the time and one to end the time. The startCycle/endCycle and startFrame/endFrame all represent different memory addresses.
+<code asm>
+  _time_start:
+        PUSH BP
+        mov BP, SP
+        Push R0
+        in R0, TIM_CycleCounter
+        mov startCycle, R0
+        in R0, TIM_FrameCounter
+        mov startFrames, R0
+        POP R0
+        mov SP, BP
+        POP BP
+        ret
+  _time_end:
+        PUSH BP
+        mov BP, SP
+        Push R0
+        in R0, TIM_CycleCounter
+        mov endCycle, R0
+        in R0, TIM_FrameCounter
+        mov endFrames, R0
+        POP R0
+        mov SP, BP
+        POP BP
+        ret
+</code>
+=====Array in ASM=====
+While Sieve of Eratosthenes might be easier to implement compared to pnc1 it does require knowing how to create an array in assembly which can be challenging if it has been a while sense you messed around with them. First will take a look at the array that we want to create in C and convert it into asm.
+Here is the set up of the array in C:
+<code C>
+    int [8193]primeAr; // Creating array
+    // Filling primeAr with numbers from 2 to upperRange
+    for (int pop=2; pop <= upperBound; pop++)
+    {
+        primeAr[pop]=pop;
+    }
+</code>
+Lets look at what is happening here, so we have created an array called primeAr and we have a loop that starts at 2 and goes till upperBound which could be 1024, 2048, and so on. Inside the loop, we are specifying the index at a given point in the array and assigning it pop. This is populating our array going 2,3,4,5,...upperBound which will be important for the logic later down the line.
+Now lets look at that in asm:
+<code asm>
+    mov R8, primeAr ; Starting point goes into R8
+    iadd R8, 2      ; Incrementing R8 by 2
+    mov R9, 2       ; starting point/number (pop in C)
+_bLoop:
+    ; Loop condition
+    mov R13, R9
+    ile R13, R2
+    jf R13, _bLoopEnd
+    mov [R8], R9 ; R9 moved into R8 array at current index
+    iadd R8, 1   ; Increment memory address
+    iadd R9, 1   ; Increment loop
+    jmp _bLoop ; Back to start of loop
+_bLoopEnd:
+</code>
+As you can see the logic is very similar but just knowing how to write it might be the hard part but after doing a couple look overs and experimenting it will click.
@@ Line 119: / Line 293: @@
 </dataplot>
-====Wolfgang pnc0 runtimes====
+====Wolfgang pncX runtimes====
 {{:notes:comporg:spring2024:projects:screenshot_2024-04-10_173305.png?600|}}
+{{:notes:comporg:spring2024:projects:screenshot_2024-04-17_211718.png?600|}}
-====Josiah pnc0 runtimes====
+{{:notes:comporg:spring2024:projects:screenshot_2024-04-24_182408.png?600|}}
+====Josiah pnc runtimes====
 Raw times for my code:
@@ Line 131: / Line 306: @@
 ^ 8192    | 31.3166        | 22.366       |
-{{:notes:comporg:spring2024:projects:josiah_pnc0.png?400|}}
+pnc0-{{:notes:comporg:spring2024:projects:josiah_pnc0.png?400|}}
-====Josiah pnc1 runtimes====
-{{:notes:comporg:spring2024:projects:screenshot_2024-04-17_205000.png?400|}}
+pnc1-{{:notes:comporg:spring2024:projects:screenshot_2024-04-17_205000.png?400|}}
+pnc2-{{:notes:comporg:spring2024:projects:screenshot_2024-04-18_191116.png?400|}}
 ====jmerri10 pnc0 runtimes====
 pnc0
@@ Line 142: / Line 319: @@
 {{:notes:comporg:spring2024:projects:pnc1.png?400|}}
-====jhimmel2 pnc0 runtimes====
+====jhimmel2 runtimes====
+PNC0
 {{:notes:comporg:spring2024:projects:screenshot_2024-04-10_214015.png?400|}}
 {{:notes:comporg:spring2024:projects:screenshot_2024-04-10_214033.png?400|}}
+PNC1
+{{:notes:comporg:spring2024:projects:screenshot_2024-04-17_230033.png?400|}}
 ====dmorey2 pnc0 runtimes====
 {{:notes:comporg:spring2024:projects:line-graph.png?400|}}
+====dmorey2 pnc1 runtimes====
+{{:notes:comporg:spring2024:projects:meta-chart.png?400|}}
+====dmorey2 pnc2 runtimes====
+{{:notes:comporg:spring2024:projects:meta-chart_1_.png?400|}}
 ====rspringe Runtimes====
 ===pnc0===
 {{:notes:comporg:spring2024:projects:rspringe_pnc0_graph.png?400|}}
 ===pnc1===
+{{:notes:comporg:spring2024:projects:rspringe_pnc1_graph.png?400|}}
 ===pnc2===
+{{:notes:comporg:spring2024:projects:rspringe_pnc2_graph_-_1.png?400|}}
+{{:notes:comporg:spring2024:projects:rspringe_pnc2_graph_-_2.png?400|}}