### Latest Articles

Apr 21, 2008 | Powered By SQLite |

Apr 20, 2008 | Double-Time Blogs Are Back! |

Sep 05, 2006 | Finding Prime Numbers Using C++ |

Jul 01, 2006 | Finding Prime Numbers - A Simple Assembly Language Example Using NASM |

## 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!