.. title: Prime Checking in NASM
.. slug: prime-check-nasm
.. date: 2018-09-25 05:00:00 UTC
.. tags: mathjax, assembler, math, coding
.. category:
.. link:
.. description:
.. type: text
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:
.. code::
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:
.. code::
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:
.. code::
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 :math:`N`:
.. math::
f(x) = \frac{x + N / x}{2}
Repeated application of :math:`f` onto any seed (number to start with) will result in a number that gets closer and closer to the true value of :math:`\sqrt{N}`. If :math:`x = \sqrt{N}` exactly, then :math:`f` will return the same value:
.. math::
f(\sqrt{N}) = \frac{\sqrt{N} + N / \sqrt{N}}{2}
= \frac{\sqrt{N} + \sqrt{N}}{2}
= \sqrt{N}.
For our purposes, we chose the seed :math:`x = N / 2`. Calculating one iteration of the Babylonian method then yields:
.. math::
f(x) = \frac{(N / 2) + N / (N / 2)}{2}
= \frac{(N / 2) + 2}{2}
= \frac{N + 4}{4}.
Using this convenient expression instead rids our algorithm of those pesky square roots:
.. code::
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.
.. code::
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.