Finding Prime Numbers - A Simple Assembly Language Example Using NASM

Lately I've been really getting into low level programming. As much as I love .NET, coding no longer feels like man vs machine; it's now more like man vs framework. Now don't get me wrong, I'm haven't gone off the deep end yet, I am in no way considering (or advocating) leaving our modern programming comforts to go back to the ways of old. I do, however, believe that any good software engineer should know what's going on under the hood, and there really is no other way of doing that other than coding in assembly (well, I guess you could code all the instructions in binary...).

For all intents and purposes, this is my first assembly program. Yes, like most other Computer Science students, I took an assembly language course in college. Unfortunately, our professor didn't get us much further than the "Hello World" program, which hardly qualifies me as being experienced with assembly. Please keep in mind that this is my first stab at it, and if you see stuff that doesn't look quite right, then it very well may be my inexperience coming to light.

I used NASM for this example. I feel that NASM is a bit cleaner and easier to understand than MASM. I really wish that there would be more NASM documentation, however. Most books and tutorials are written using MASM. Thankfully the two aren't too different. You can read the MASM stuff, do a few NASM tutorials to get a feel for the difference, and you'll be pretty much in sync. I also use a C skeleton program to call the assembly procedure. Yes, its "cheating" a bit, since I'm using C to get me into protected mode and to set up the segments and segment registers. Quite honestly though, that isn't the stuff I'm interested in, or at least not now. I use the DJGPP environment to use gcc as my c compiler.

Note (4/20/2008): There's PLENTY of room for optimization here - this is a very slow algorithm. Still, I think it serves as a good starting point for assembly language as solving primes is an easy, but not trivial problem.

Note 2: I had to move the code comments around because the way the code was laid out before was breaking IE (big surprise). If something looks out of place please let me know.

Assembly Code

    
;Amount of double words (32 bits each) that we will reserve
%define RESSIZE 10000000          

;Uninitialized data goes in bss segment   
segment .bss      
    
    ;Reserve plenty of space for primes (38MB)                
    Primes resd RESSIZE    
    
    ;Reserve space for answer
	RetVal resd 1                 

;Code goes in the text section
segment .text
     ;global <procedure name>                      
     global _asm_main lets C program "see" the procedure            
                                  
     ;procedure start
     _asm_main:     
        ;setup routine             
        enter 0,0    
        
         ;save register states for when we return to C               
        pusha                    
                                  
    ;indexer for prime number array            
	mov esi,0   
	
	;ebp-1 points to last found prime                  
	mov ebp,0                     
		
	;first prime given free		
	mov [Primes], DWORD 3
	
	;set up to hold next prime        
	inc ebp	                      
	
	;find primes from 3 to X		
	mov ecx, DWORD 3	         
	
	;outer loop
	i:	
	    ;check that we haven't gone past max		      
	    cmp ecx,10000000          
            ja  end
		
		 ;clear "j" (inner loop)		
	    mov esi,0	             
        
        j:
            ;if we've gone past our current list of primes, we're prime
		    cmp esi,ebp               
                                  
		    ja prime              
				
				
			;divide by previous prime
		    mov edx, 0                
		    mov eax, ecx
		    div DWORD [Primes + (esi-1)*4]
		    
		    ;if we have no remainder, skip
		    cmp edx, 0
		    je  next                  
				
			 ;go to next prime
		    inc esi	                 
		jmp j
				
	    ;Add new prime to list
	    prime:		              

	        mov [Primes + ebp * 4], ecx
	        inc ebp
		
            next:	
	        add ecx,2
	        jmp i

	end:
				
	mov eax,[Primes + (ebp-1)*4]
        mov [RetVal],eax
               
         ;Get register states from before we ran procedure         
        popa                   
                                
        ;return back to C
        mov eax, [RetVal]       
        leave
        ret 




   

C code

#include<stdio.h>
int main()
{
        int ret_status;
        
        ret_status = asm_main();
        printf("%d",ret_status);
        return 0;

}
    

How it works

In case you don't remember, a prime number is a number that is divisible only by two numbers. Lots of people say that a prime number is any number divisible by 1 and itself. This is incorrect, since 1 is NOT a prime number (it is only divisible by 1 number, itself).

The simplest prime number program you can write is to have two loops: the outer loop (i) controls the prime number candidate, and the second loop (j) runs from 2 to i-1. Within the middle loop, we divide i by j; if we have no remainder, we know its not a prime, and break from the second loop. While simple, this algorithm is O(n²). Sure, we can double efficiency by eliminating even numbers (which, other then 2, will never be prime), but n²/2 is still O(n²).

Our technique builds upon this little fact about composite (non prime) numbers:
composite numbers are multiples of prime numbers. We can use this to our advantage because now we can check our prime number candidate against previously found prime numbers instead of ALL of the numbers from 1 to i. This puts us at O(nlogn), which is definately better than where we were before. I don't claim that my algorithm is the best, if you search the web you'll probably find more clever algorithms. If you decide to implement it in assembly, please send me a copy!