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!