# ECE 1 09 – 001 Program 1 : lcm .asm Spring 201 6

Is this the question you were looking for? If so, **place your order here** to get started!

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!

0