ECE 1 09 – 001 Program 1 : lcm .asm Spring 201 6
This programming assignment must be completed individually. Do not share your
code with or receive code from any other student. The only people who may see your
code are the instructor and the ECE 109 TAs. Evidence of copying or other unauthorized collaboration will be investigated as a potential academic integrity violation. The minimum penalty for cheating on a programming assignment is a grade of -100 on the assignment. If you are tempted to copy because you’re running late, or don’t know what you’re doing, you will be better off missing the assignment and taking a zero.
Providing your code to someone is cheating, just as much as copying someone else’s work.
DO NOT copy code from the Internet, or use programs found online
or in textbooks as a “starting point” for your code. Your job is to design and write this program from scratch, on your own. Evidence of using external code from any source will be investigated as a potential academic integrity violation.
This LC-3 assembly language program will compute the Least Common Multiple (LCM) of two or three positive integers.
The LCM of two numbers {a, b} is the smallest number that is a multiple of both a and b.
The LCM of three numbers {a, b, c} is the smallest number that is a multiple of a, b, and
c.
But wait, you say–doesn’t this require the use of multiply or divide?
To see if something is a multiple of something else? No. We will use a “brute force” method that only requires the use of addition and comparison (aka subtraction).
First, I will give you the detailed specification of the program. Then, we will discus
s the algorithm.
Details
The program must start at address x3000.
Here’s how
the
program must behave:
1.
Before running the program, put the values into R0, R1, and R2. If you only want to find the LCM
of two numbers, then put non
–
zero values into R0 and R1
, and put zero in R2. The input numbers
must all be 16
–
bit non
–
zero, positive 2’s complement integers (between x0001 and x7FFF).
2.
Next, run the program until it reaches the end (HALT).
3.
After the halt, R3 must contain the LCM value.
•
If R2 was initially
zero, then R3 must be the LCM of R0 and R1.
•
If R2 was initially non
–
zero, then R3 must be the LCM of R0, R1, and R2.
•
In either case, if the LCM cannot be calculated because it is out of range (larger than x7FFF),
then R3 must contain
–
1 (xFFFF).
2
The only v
alue that matters
when the program ends is R3. All other registers (including R0, R1, and R2)
are allowed to change during execution.
The Algorithm
In this section, I will describe an algorithm to compute the LCM of two numbers {
a
,
b
}. You will need
to e
xtend this algorithm to work with three numbers. And you will need to translate this algorithm into
LC
–
3 assembly language code.
On the “Art of Problem Solving” web site
1
, the brute force al
gorithm is described as:
list
out the multiples of each until you find a multiple that is common to [both] of them.
(It also notes that this approach is “tedious,” and is therefore only used for small numbers. Well, we
have a computer, so being tedious is not a problem.)
For example,
to find the LCM of 4 and 6:
4 8
12
6
12
This is a reasonable approach, but we need a little more direction. Clearly, it doesn’t mean to list all of
the multiples of
a
and then compare to all of the multiples of
b
. What does that “until” mean? How do
we know when to stop? And how do we compute the multiples of something when we don’t have a
multiplication instruction?
I’ll answer the last question first: The multiples of
a
are
a
,
a+a
,
a
+
a+a
, a+a+a+a
,
a+a+a+a+a
,
etc. In
other words, we can compute all
of the multiples of
a
just using addition.
Now, about the other questions: Assume, for the sake of discussion, that
a
<
b
. We’ll generate
multiples of
a
until we get to a number that is greater than or equal to
b
. If the number is equal to
b
,
then we’v
e found our answer. If not, we then generate the next multiple of
b
, until it’s
greater than or
equal to the last multiple of
a
that we computed. If the two multiples are equal, we’ve found our
answer. If not, we go back to generating multiples of
a
. W
e keep this up, switching between multiples
of
a
and multiples of
b
, until the two multiples are equal
—
that’s our answer.
Here is a more formal description of the algorithm. We will introduce two new variables,
p
and
q
.
(1) If
a
=
b
, we’re done: the L
CM is
a
. Otherwise…
(2) Let
p
=
a
, and
q
=
b
.
(3) While
p
<
q
,
p
←
p
+
a
(replace
p
with
p
+
a
).
This is a loop that generates multiples of
a
. The loop ends when
p
≥
q
.
(4) If
p
=
q
, we’re done: the LCM is
p
.
(5) While
q
<
p
,
q
←
q
+
b
.
This
is a loop that generates multiples of
b
. The loop ends when
q
≥
p
.
(6) If
q
=
p
, we’re done: t
he LCM is
p
.
(7) Go back to (3).
Is this the question you were looking for? If so, place your order here to get started!
