This is an old revision of the document!
Table of Contents
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
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.
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
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.
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.
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.
variant: odds-only processing
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.
variant: sqrt point
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.
How to Sqrt
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.
__function_sqrt: push BP mov BP, SP push R1 mov R0, [BP+2] mov R1, 0.5 pow R0, R1 pop R1
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:
_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
So while this is similar to the generated function we needed to make use of cif and cfi and then pow works.
variant: break+odds
variant: break+sqrt
variant: break+odds+sqrt
variant: sieve of eratosthenes (soe)
variant: sieve of eratosthenes with sqrt trick (soes)
timing
A potential example using the dokuwiki dataplot plugin for graphing data:
wedge pnc1 runtimes
Wolfgang pnc0 runtimes
Josiah pnc0 runtimes
Raw times for my code:
C | Asm | |
---|---|---|
1024 | .48333 | 0.333 |
2048 | 1.95 | 1.399 |
4096 | 7.83333 | 5.599 |
8192 | 31.3166 | 22.366 |