# 8086 Primes O(1) Check

# Checking primes *efficiently* in x86 asm

This topic is frequently discussed on the interwebs, however I propose
a solution of time/~~space~~ complexity of O(1).

**EDIT: My Professor pointed out the flaws in logic, it takes exponential space :(.
Also Performance is typically dominated by memory access times, so this method sucks.**

# High-level Algorithm

(I will be using a single byte in this example for the sake of simplicity.)

Given that we want to check unsigned bytes, they can have a value
between \(0\) and \(255\) inclusive (i.e., \(2^8\)). We can create a
boolean array of size 256, where `true`

represent a prime number, and
vice-versa.

Python is used in the following examples:

```
# 0 1 2 3 4
isPrime = [False, False, True, True, False, ...]
```

We can now check if a number is prime as follows:

```
isPrime[0] # False
isPrime[2] # True
isPrime[3] # True
isPrime[4] # False
```

There you have it! A O(1) algorithm…

I would say it is incredibly space inefficient! A boolean can be
represented in one *bit*, however we use a full byte. [Actually python
uses `bool`

type which is 4 to 8 bytes long! even worse, but that is
beside the point I’m making. (You could argue that we can use NumPy
which is more space efficient)]

# Bit optimization

Using a `0`

and `1`

sequence would decrease the space
used. Specifically, the space used would be divided by
`2^(sizeof(byte))`

, which in is x86 is `2^3`

. So 8 values will fit in
each byte.

To clarify, instead of 256 bytes to represent each `False`

/`True`

value, we use `256/2^3 = 32`

bytes.

In python it could be defined as:

```
# define it yourself.
# It should return 0 and 1, for non-primes and primes respectively
def isPrime(number):
pass
# bits = [0, 0, 1, 1, ...]
bits = [isPrime(i) for i in range(0,256)]
# chunks = [[0, 0, 1, 1, 0, 1, 0, 1],
# [0, 0, 0, 1, 0, 1, 0, 0],
# ...]]
chunks = [bits[i:i+8] for i in range(0, len(bits), 8)]
# is there a faster way? :)
# bytes = [53, 20, 81, 5, 4, 81, ...]
bytes = [int(''.join(str(i) for i in chunk), 2) for chunk in chunks]
```

I find using octave/Matlab far simpler (In fact I don’t enjoy python :D)

```
bits = isprime(0:255)' % [0, 0, 1, 1, 0, ...]
bytes = bit2int(bits,8) % [53, 20, 81, 5, 4, 81, ...]
```

Now we need first to access the byte, then choose the correct bit, which should be simple in python, so lets just do it in x86 directly.

# x86 asm

First define the byte array at the end of your code (or data segment)

```
; Define the byte array
PRIMES DB 53, 20, 81, 5, 4, 81, 4, 20, 17, 65, 16, 64, 69, 20, 64, 1, 16, 80, 5, 4, 17, 4, 20, 1, 69, 0, 16, 1, 20, 65, 64, 16
```

Now lets say we want to check if `CX`

is prime or not.

```
# the number we test in this example
MOV CX, 17
; Shifting by 3 equivilent to dividing by 8.
; Used to index at byte level
; Now BX = 2
MOV BX, CX
SHR BX, 3
; BL = the byte, in our case PRIMES[2] = 81 ; 81 = 01010001
MOV BL, [PRIMES + BX]
; Last 3 bits used to index which bit of the byte
; In our case, 17 & 07 = 1
AND CL, 07 ; bit mask 0b111
; CL = 2. Increment to change to index that starts at 1
INC CL
; 81 << 2.
; we get 0 or 1 that represents if the number is prime or not.
; It is then moved to carry bit.
SHL BL, CL
JC PRIME
PRIME:
NOP ; anything :)
```

Contact me if you know of a faster way or can use less than two registers!