Prime Checking in NASM

Primality Checking

It's very difficult to quickly determine the prime factors of a number because there's no known deterministic algorithm to do so. Therefore, the only method to determine prime factors and primality is a brute force approach with as much information as possible.

Simple Brute-Force

It's rather trivial to show that if a number n has multiple prime factors, every prime factor must be strictly smaller than n. Therefore, the simplest algorithm to check the primality of a number starts n and loops all the way down to 2, stopping before it reaches 1 (every number is divisible by 1). The pseudocode for this is:

function is_prime(n) {
         i = n
         while i > 1 {
               if (n % i) == 0 {
                     // n is divisible by i, abort
                     return false
               }
               i -= 1
         }
         return true // we've made it through
}

Although this algorithm has to iterate through lots of possible divisors, it does work.

Bounded Brute-Force

A less trivial fact is that non-prime number must have at least one prime factor less than or equal to its square root. We proceed by contradiction: multiple factors must exist, since the number is composite, each being larger than the square root, whose product will then at least be larger than the product of the square root with itself, and thus larger than the given number itself.

Therefore, we may set an upper bound of sqrt(n) on our set of divisors, while still ensuring that at least 1 exists. This is promising, because as the number grows, its square root grows more and more slowly, making our algorithm more and more performant for larger integers. Thus, we can use our same is_prime implementation, with a significantly smaller upper bound:

function is_prime(n) {
         i = sqrt(n)
         while i > 1 {
               if (n % i) == 0 {
                     // n is divisible by i, abort
                     return false
               }
               i -= 1
         }
         return true // we've made it through
}

One more trick we can apply is checking first if a number is even. If a number is even and it isn't 2, the number is divisible by 2 and is thus not prime. We'll apply this trick before we start doing any type of intensive computation:

function is_prime(n) {
         if (i % 2) == 0 {
            if i == 2 { return true  }
            else      { return false }
         }
         i = sqrt(n)
         while i > 1 {
               if (n % i) == 0 {
                     // n is divisible by i, abort
                     return false
               }
               i -= 1
         }
         return true // we've made it through
}

Babylonian Bounded Brute-Force

Now, hold on a second... NASM doesn't have a convenient means of taking the square root truncated to an integer. To calculate the square root would necessitate loading to/from the FPU, which is very computationally intensive. However, we may instead use the Babylonian approximation for the square root of a number instead of the square root; which will still satisfyingly reduce the size of our test space. Recall the Babylonian method to calculate the square root of \(N\):

\begin{equation*} f(x) = \frac{x + N / x}{2} \end{equation*}

Repeated application of \(f\) onto any seed (number to start with) will result in a number that gets closer and closer to the true value of \(\sqrt{N}\). If \(x = \sqrt{N}\) exactly, then \(f\) will return the same value:

\begin{equation*} f(\sqrt{N}) = \frac{\sqrt{N} + N / \sqrt{N}}{2} = \frac{\sqrt{N} + \sqrt{N}}{2} = \sqrt{N}. \end{equation*}

For our purposes, we chose the seed \(x = N / 2\). Calculating one iteration of the Babylonian method then yields:

\begin{equation*} f(x) = \frac{(N / 2) + N / (N / 2)}{2} = \frac{(N / 2) + 2}{2} = \frac{N + 4}{4}. \end{equation*}

Using this convenient expression instead rids our algorithm of those pesky square roots:

function is_prime(n) {
         if (i % 2) == 0 {
            if i == 2 { return true  }
            else      { return false }
         }
         i = (n + 4) / 4
         while i > 1 {
               if (n % i) == 0 {
                     // n is divisible by i, abort
                     return false
               }
               i -= 1
         }
         return true // we've made it through
}

NASM Implementation

Below is the final implementation, in NASM, of the proposed prime checking algorithm. The number to check is passed in on register eax and the result, 0 (not prime) or 1 (prime) is returned in the same eax register.

is_prime:
        ;; save registers
        push ebx ;; store the value of eax, ebx, ecx, edx \
        push ecx ;; so functions called before and after won't have \
        push edx ;; values changed

       ;; even/odd check
       test eax, 1
       cmp eax, 2
       je is_prime_end
       jmp not_prime_end

       ;; save the value of eax in ebx
       mov ebx, eax

       ;; calculate our square root approximation
       add eax, 4 ;; eax = eax + 4

       mov ecx, 4 ;; set dividend to 0
       mov edx, 0 ;; set remainder to 0
       div ecx    ;; divide eax by ecx and put rounded result in eax

       ;; store our iteration variable in ecx
       mov ecx, eax

       is_prime_loop:
                ;; if ecx is 1 and we haven't found
                ;; a factor, it's prime
                cmp ecx, 1
                je is_prime_end

                ;; restore eax to original value
                mov eax, ebx

                ;; divide by ecx
                mov edx, 0 ;; set remainder to 0
                div ecx    ;; divide eax by ecx, leaving remainder in edx

                ;; if edx is 0, there's no remainder and we found a divisor
                cmp edx, 0
                je is_not_prime

                ;; decrement iterator
                dec ecx

                ;; loop through again
                jmp is_prime_loop

       is_not_prime:
                ;; restore values of registers
                pop edx
                pop ecx
                pop ebx

                ;; return value 0 in eax
                mov eax, 0
                ret

       is_prime:
                ;; restore values of registers
                pop edx
                pop ecx
                pop ebx

                ;; return value 1 in eax
                mov eax, 1
                ret

System Information

I ran this code on my Linux machine using the Netwide Assembler (NASM). Note that any other assembler may be used (the Intel instruction set is the same), but syntax may differ.