Differences

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

--- notes:fall2024:projects:pnc1 [2024/04/25 03:18] – created - external edit 127.0.0.1
+++ notes:fall2024:projects:pnc1 [2024/10/17 01:51] (current) – bpatrice
@@ Line 19: / Line 19: @@
 </code>
-====Future Proofing====
-From the previous dap projects, we learned a lot about stacks and creating subroutines. With that newfound knowledge, we can create a couple of subroutines to help us with this and later pnc projects. When taking a step back and looking at the output we see that we are displaying strings, integers, and floats. So that three subroutines that we can create now and use later. Further, we can also create a subroutine for doing the brute logic of finding prime numbers. I personally started by creating these as separate files but found later on that having them in one big file is just easier to work with.
-===Print Subroutine===
-For the print subroutine, we actually can work with two old programs. Looking at any of the dap code that we wrote, let's grab the starting and end logic of the subroutine that relates pushing and popping registers along with the code that gets our X, Y, and "Thing" from the stack. Now for the brains of our program. What actually happens in the subroutine was created in one of our very first classes. We created a little program that printed Hello World in ASM. We can use that!
-Do note that we cannot just simply copy and paste all of this, and it suddenly works, there are some adjustments that need to be made but by this point, you are 90% of the way there.
-===Printing Seconds===
-When printing the seconds that it takes to do the brute force there are generally two approaches that you may want to consider using int's and arithmetic or using the float with some fancy math. But before that, how do you get the seconds? Its relatively easy in assembly all you have to do is record the frames before and after you complete the run. One example of this is something like below.
-<code asm>
-  in R8, TIM_FrameCounter
-  mov startFrames, R8
-  call _brute_force
-  in R8, TIM_FrameCounter
-  mov endFrames, R8
-  ;Later in the code
-  mov R8, startFrames
-  mov R9, endFrames
-  isub R9, R8 ; subtract the start frames from end
-  CIF R9 ;changing data type to float
-  fdiv R9, 60 ;dividing by 60 to get the amount of seconds
-  mov seconds, R9 ;store the seconds for use later in the code
-</code>
-int: integer
-Float
-There is more than one way to print the runtime as an integer with three decimal places. One way is by subtracting the initial frame count (before the brute force) from the final frame count (after the brute force) to get the total frames elapsed, multiply that by 1000, then divide by 60 (since there are 60 frames per second). The result will be the time in milliseconds. Using your print/itoa subroutine, you can print the first three digits, then a decimal place, then the last three digits. There might be a simpler way that makes more sense to you (such as using floats), but this is what I did.
 ====variant: break on composite (BOC)====
-Break on Composite is one of the first, and simplest, improvements that can be made to a prime number generator.
+just add a break; statement within your brute loop like so:
-In the Brute Force algorithm, every number between 2 and the current number is checked to see if it is a factor. Even after a factor is found, it keeps going through the rest of the possible factors.
+<code>
+START TIMEKEEPING
-What "Break on Composite" does is that after it finds a factor, it does not need to check further, and can break out of the loop.
+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:
-Optimizing prime number generation by considering only odd numbers can significantly enhance the efficiency of the algorithm. Since even numbers (except 2) are inherently not prime, eliminating them from consideration reduces the number of iterations required for testing primality. By starting with 3 as the first odd prime number, subsequent odd numbers are generated and tested for primality. This optimization effectively cuts the search space in half, as it eliminates the need to check even numbers, leading to a faster algorithm.
+<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
-By recognizing that factors of a number occur in pairs, one of which is less than or equal to the square root of the number, we can limit our search space. This method significantly reduces the number of iterations required to test primality, as we only need to examine potential factors up to the square root of the number in question. Consequently, computational resources are conserved, resulting in a faster and more streamlined algorithm.
+<code>
+START TIMEKEEPING
-===How to Sqrt===
+NUMBER: FROM 2 THROUGH UPPERBOUND:
-While sqrt might seem easy at first it is kind of involved if you don't fully understand what is going on. To best understand how to sqrt let's look at the generated function from the .asm you get from complaining your c program.
+    ISPRIME <- YES
+    FACTOR: FROM 2 * 2 THROUGH NUMBER-1:
-<code asm>
+        SHOULD FACTOR DIVIDE EVENLY INTO NUMBER:
-__function_sqrt:
+            ISPRIME <- NO
-  push BP
+    PROCEED TO NEXT FACTOR BY TWO
-  mov BP, SP
+    SHOULD ISPRIME STILL BE YES:
-  push R1
+        INCREMENT OUR PRIME TALLY
-  mov R0, [BP+2]
+PROCEED TO NEXT NUMBER BY TWO
-  mov R1, 0.5
+ONCE UPPERBOUND IS REACHED ADD A ONE TO YOUR PRIME TALLY TO ACCOUNT FOR NOT STARTING AT TWO
-  pow R0, R1
+STOP TIMEKEEPING
-  pop R1
 </code>
-As we can see sqrt actually makes use of the pow instruction. Also note that there is no number directly fed into pow because you can only give registers so you'll need to make use of a temp register here. At this point, you are probably thinking that this is supper easy and isn't that hard to figure out but that is not the case.
-When actually implementing this into your program you'll need to make use of cif and cfi. Lets take a look at the following example:
-<code C>
-_useSqrt:
-    ; Square rooting number
-    mov R12, R9 ; R12 is a temp register in this case
-    cif R12     ; We then convert that int into a float
-    mov R1, 0.5 ; R1 is also temp register and holds the power
-    pow R12, R1 ; Now calling pow with TWO floats
-    cfi R12     ; converting back to int
-</code>
-So while this is similar to the generated function we needed to make use of cif and cfi and then pow works.
@@ Line 100: / Line 77: @@
 ====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.
+<code>
+START TIMEKEEPING
-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.
+NUMBER: FROM 3 THROUGH UPPERBOUND:
+    ISPRIME <- YES
-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.
+    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>
-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====
-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.
+For this version, you will combine all three of the above into one process!
-  - 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=====
@@ Line 214: / Line 190: @@
 </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 292: / Line 199: @@
 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 |}}
-====Wolfgang pncX runtimes====
+====VerbalGnat48's pnc1 runtimes====
-{{:notes:comporg:spring2024:projects:screenshot_2024-04-10_173305.png?600|}}
+{{ :notes:fall2024:projects:carter_pnc1.png?600 |}}
-{{:notes:comporg:spring2024:projects:screenshot_2024-04-17_211718.png?600|}}
-{{:notes:comporg:spring2024:projects:screenshot_2024-04-24_182408.png?600|}}
-====Josiah pnc runtimes====
-Raw times for my code:
-|              ^ C            ^ Asm          ^
+====MrVengeance's pnc1 runtimes====
-^ 1024    | .48333         | 0.333        |
+{{ :notes:fall2024:projects:pnc1-graph.png?600 |}}
-^ 2048    | 1.95           | 1.399        |
+====XaViEr'S pnc1 runtimes====
-^ 4096    | 7.83333        | 5.599        |
+{{ :notes:fall2024:projects:xavierspnc.png?600 |}}
-^ 8192    | 31.3166        | 22.366       |
-pnc0-{{:notes:comporg:spring2024:projects:josiah_pnc0.png?400|}}
+====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)">
+0.483 0.083 0.033 0.17 0.033 0.0 0.017 0.0
+1.967 0.283 0.117 0.017 0.133 0.017 0.017 0.0
+7.867 1.017 0.467 0.05 0.467 0.05 0.017 0.017
+31.367 3.683 1.717 0.117 1.717 0.100 0.05 0.05
+</dataplot>
-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
-{{:notes:comporg:spring2024:projects:pnc0.png?400|}}
-pnc1
-{{:notes:comporg:spring2024:projects:pnc1.png?400|}}
-====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|}}

Lab46 Wiki

User Tools

Site Tools

Differences

Page Tools