Implementing the Sieve of Eratosthenes using the LC-3 Language

GT STUDENTS: DO YOUR WORK ON YOUR OWN! DON’T MAKE ME TELL LEAHY THAT YOU GUYS HAVE BEEN VISITING THIS.

-Warning: Todays post may be difficult to understand if you have little to no knowledge of programming and/or low-level computing systems-

RISING FROM THE DEPTHS OF ANDREW’S SCHOOL WORK- It has been a long time since I’ve updated here since I’ve started yet another semester at college. I thought I would keep you updated on some of the topics I’ve been studying.

Today I will be going over the basics of the LC-3 computer and it’s assembly programming language. The specific task we are going to implement is to find the all the prime numbers from 0-3000 by using the Sieve of Erathosthenes algorithm. This was one of my most recent assignments and while not perfect, it satisfied the requirements of the assignment. Feel free to help me perfect it if you feel like it. The first step we need to do is get a handle on how the algorithm works.

The Sieve of Ertathosthenes works by first creating a list of all the numbers you wish to analyze. Then selecting a current number, starting with 2, you go through the list eliminating all of the factors of your current number. After you have iterated through the list, you then select the next number in the list. Here is an example. For simplicity we are going to use 0 through 23. I will set the numbers we are eliminating to zero. So here is our list:

*Note: We eliminate 0 and 1 because they are known primes*
LIST (Pre-Method):0 0 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

First iteration: Current number=2
Eliminate 4,6,8,10,12,14,16,18,20,22

LIST (After First iteration): 0 0 2 3 0 5 0 7 0 9 0 11 0 13 15 0 0 17 0 19 0 21 0 23

Second iteration: Current number=3
Eliminate 9,15,21

LIST (After Second iteration): 0 0 2 3 0 5 0 7 0 0 0 11 0 13 0 0 0 17 0 19 0 0 0 23

If you notice, we have already found all of the primes for 0-23.

So now that we know the basics of the algorithm, we can approach the problem. The first step I do is to block out the algorithm using pseudocode:
//Sieve of Erathosthenes Pseudocode
//Author: Andrew Melim

Integer list = new Integer[3001];

//Initialize the array
for(int i=0; i<3001; i++)
{
list[i]=i;
}

//Take care of 1, our speical case
list[1]=0;

//Perform Algorithm
for(int x=2; x<=3000; x++)//Set our starting number to 2
{
start=2*x; //Ignore our current number

for(int y=start; y<=3000; y=y+x)//Traverse through our factors, //starting at the factor after our current number
{
list[y]=0; //Eliminate this factor
}

}

print list;


So what I have done is create a program which will print out three thousand numbers with 0’s representing non-prime numbers and the number itself if it is prime. Now let’s take a look at the LC-3 code after modeling it after our pseudocode.

;SIEVE OF ERATHOSTHENES
;FEB 18, 2007

.orig x3000
N3000 .FILL#-3000

ADD R0, R0, #-1 ;PRIMES VALUE
LEA R2, PRIMES ;PRIMES MEMORY ADDRESS

This our first block of code. We start off by claiming our starting memory location at x3000 and creating a constant of -3000, which we will be using during our main nested loops. Next, we set our R0 register to -1. This register will count up and represent our integers. We start at -1 because we start our loop by incrementing by 1 (So we will really be starting at 0). We then load our PRIMES starting memory address by calling LEA (Load Effective Address) which loads the address into our Third Register, R2.

INIT
ADD R0, R0, #1 ;INCREMENT PRIMES VALUE
STR R0, R2, #0 ;MEM[R2(PRIMES)]<- R0(PRIMES VALUE)
ADD R2, R2, #1 ;INCREMENT PRIMES ADDRESS
BRNP INIT ;CONTINUE WHILE NOT ZERO
;END INIT

This represents our initialization for-loop in our pseudocode. We start off by incrementing our current integer(R0) by 1. We then place that current integer into our array at our current memory address. We continue for the rest of the array.

;SET 1 TO ZERO BECAUSE IT IS PRIME
LEA R2, PRIMES ;RELOAD PRIMES ADDRESS
AND R0, R0, #0 ;RESET PRIMES VALUE TO ZERO
ADD R2, R2, #1 ;SET TO PRIMES[1]
STR R0, R2, #0 ;MEM[R2(PRIMES+1)]<- 0
;END LOGIC SET 1

This is where we take care of our special case, the number 1.

AND R0, R0, #0 ;RESET R0 TO 0. R0 IS NOW ARRAY INDEX
ADD R0, R0, #1 ;SET STARTING VALUE AT 1
AND R1, R1, #0 ;OUR ZERO VALUE TO SET NON-PRIMES TO ZERO
LEA R4, N3000 ;THIS IS THE CHECK REGISTER TO SEE IF WE ARE DONE
LEA R2, PRIMES ;RELOAD PRIMES ADDRESS

OUTERLOOP
ADD R0, R0, #1 ;INCREMENT OUR ARRAY INDEX
ADD R2, R2, R0 ;INCREMENT R2 BY R0 (ignore first factor)

INNERLOOP
ADD R2, R2, R0 ;INCREMENT R2 BY R0 (GO THROUGH FACTORS)
LEA R4, N3000 ;RESET CHECK REGISTER
STR R1, R2, #0 ;MEM[R2(PRIMES ADDRESS)]3000 (R4 WILL BE POSITIVE IF TRUE)
ADD R4, R4, R2
BRZP INNERLOOP ;CONTINUE WHILE NEGATIVE

LEA R2, PRIMES ;RELOAD PRIMES ADDRESS
LEA R4, N3000 ;RESET CHECK REGISTER
ADD R4, R4, R0 ;CHECK TO SEE IF R0>3000 (R4 WILL BE POSITIVE OR ZERO IF TRUE)
BRZP OUTERLOOP ;CONTINUE WHILE NEGATIVE

This represents our nested for-loops while we go through the factors. Within the inner-loop we set the factors to zero using the STR command.

HALT
PRIMES .BLKW #3001

.END

Lastly, make sure we halt and end the program. We also need to set aside our block to represent our array.

Now, I need to say this right now. There is a bug within this code which causes it to go beyond the array and start inputing values into higher memory addresses. I haven’t debugged this too much because honestly, I have no idea what it is. If any of you feel up for a challenge, feel free to post a solution in the comments section. Feel free to do the same if you have any questions.
Here is the full code:

;SIEVE OF ERATHOSTHENES
;FEB 18, 2007

.orig x3000
N3000 .FILL#-3000

ADD R0, R0, #-1 ;PRIMES VALUE
LEA R2, PRIMES ;PRIMES MEMORY ADDRESS

INIT
ADD R0, R0, #1 ;INCREMENT PRIMES VALUE
STR R0, R2, #0 ;MEM[R2(PRIMES)]<- R0(PRIMES VALUE)
ADD R2, R2, #1 ;INCREMENT PRIMES ADDRESS
BRNP INIT ;CONTINUE WHILE NOT ZERO
;END INIT

;SET 1 TO ZERO BECAUSE IT IS PRIME
LEA R2, PRIMES ;RELOAD PRIMES ADDRESS
AND R0, R0, #0 ;RESET PRIMES VALUE TO ZERO
ADD R2, R2, #1 ;SET TO PRIMES[1]
STR R0, R2, #0 ;MEM[R2(PRIMES+1)]<- 0
;END LOGIC SET 1

AND R0, R0, #0 ;RESET R0 TO 0. R0 IS NOW ARRAY INDEX
ADD R0, R0, #1 ;SET STARTING VALUE AT 1
AND R1, R1, #0 ;OUR ZERO VALUE TO SET NON-PRIMES TO ZERO
LEA R4, N3000 ;THIS IS THE CHECK REGISTER TO SEE IF WE ARE DONE
LEA R2, PRIMES ;RELOAD PRIMES ADDRESS

OUTERLOOP
ADD R0, R0, #1 ;INCREMENT OUR ARRAY INDEX
ADD R2, R2, R0 ;INCREMENT R2 BY R0 (ignore first factor)
INNERLOOP
ADD R2, R2, R0 ;INCREMENT R2 BY R0 (GO THROUGH FACTORS)
LEA R4, N3000 ;RESET CHECK REGISTER
STR R1, R2, #0 ;MEM[R2(PRIMES ADDRESS)]3000 (R4 WILL BE POSITIVE IF TRUE)
BRZP INNERLOOP ;CONTINUE WHILE NEGATIVE
LEA R2, PRIMES ;RELOAD PRIMES ADDRESS
LEA R4, N3000 ;RESET CHECK REGISTER
ADD R4, R4, R0 ;CHECK TO SEE IF R0>3000 (R4 WILL BE POSITIVE OR ZERO IF TRUE)
BRZP OUTERLOOP ;CONTINUE WHILE NEGATIVE

HALT
PRIMES .BLKW #3001

.END