NCL 111: Working with Numbers

So far, we've learned how to store numbers, change them, compare them, and choose different paths through a program.

We've also learned how to repeat a group of instructions by jumping backward.

This time, we're not going to introduce another operation.

Instead, we're going to combine the ones we already know to make the computer do some tedious work for us.

The problem

You've probably found greatest common divisors by hand before.

The greatest common divisor, or GCD, of two integers is the largest integer that divides both values evenly.

For example, 48 and 18 are both divisible by:

1
2
3
6

The greatest of those is 6, so:

gcd(48, 18) = 6

Finding a GCD by hand isn't especially difficult, but it can become tedious when the numbers get larger.

Fortunately, the computer doesn't mind tedious.

If we can describe a procedure for finding a GCD using operations the CPU understands, we can give it two numbers and let it do the repetitive work for us.

Euclid's algorithm

We could find the GCD by testing possible divisors one at a time.

Instead, we'll use a much better procedure called Euclid's algorithm.

Why Euclid's algorithm works is an interesting mathematical question, but it isn't the problem we're solving here. We'll take the procedure as given and concentrate on turning its steps into a program.

The algorithm works like this:

1. Start with two values, a and b.
2. Find the remainder of a divided by b.
3. Replace a with the old value of b.
4. Replace b with the remainder.
5. Repeat until b becomes zero.
6. The value left in a is the GCD.

Let's try it with:

a = 1071
b = 462

The first remainder is:

1071 MOD 462 = 147

So the next pair becomes:

a = 462
b = 147

Then:

462 MOD 147 = 21

So:

a = 147
b = 21

Then:

147 MOD 21 = 0

So:

a = 21
b = 0

Now b is zero, so we're finished.

The GCD is:

21

The full trace looks like this:

a	b	a MOD b
1071	462	147
462	147	21
147	21	0
21	0	—

Nothing especially complicated happened in any one step.

The useful part is that we kept repeating the same transformation.

Set up the registers

The algorithm needs to keep track of three values:

• the current value of a;
• the current value of b;
• the remainder we just calculated.

We'll use three integer registers:

#a r0
#b r1
#remainder r2

Then give #a and #b their starting values:

MOVE #a 1071
MOVE #b 462

At this point:

Register	Value
#a	1071
#b	462
#remainder	—

We're ready to perform the first step of the algorithm.

Perform one step

The first thing we need is the remainder of #a divided by #b.

We already know an operation for that:

MOD #remainder #a #b

Now:

Register	Value
#a	1071
#b	462
#remainder	147

The algorithm tells us to replace a with the old value of b.

That's simply:

MOVE #a #b

Then the remainder becomes the new value of b:

MOVE #b #remainder

After those three instructions:

Register	Value
#a	462
#b	147
#remainder	147

Compare that with the first two rows of our manual trace:

a	b	a MOD b
1071	462	147
462	147	21

We've successfully moved from the first pair to the second.

Do it again

Now perform exactly the same three operations again:

MOD #remainder #a #b
MOVE #a #b
MOVE #b #remainder

This time:

462 MOD 147 = 21

and the registers become:

Register	Value
#a	147
#b	21
#remainder	21

Do it once more:

147 MOD 21 = 0

and we get:

Register	Value
#a	21
#b	0
#remainder	0

We've reached the end of the algorithm.

We've also found something familiar.

We're doing the same three things over and over:

MOD #remainder #a #b
MOVE #a #b
MOVE #b #remainder

Instead of writing them repeatedly, we can make the CPU repeat them for us.

Turn the repeated work into a loop

Put the repeated instructions under a label:

$again
MOD #remainder #a #b
MOVE #a #b
MOVE #b #remainder
JUMP $again

Now the CPU will perform one step, jump backward, perform another step, jump backward, and keep going.

Unfortunately, it will keep going forever.

We need to tell it when the algorithm is finished.

Look back at our trace:

a	b	a MOD b
1071	462	147
462	147	21
147	21	0
21	0	—

We stop when #b becomes zero.

We already know how to make that decision:

BEQ $done #b 0

Put that check at the beginning of the loop:

$again
BEQ $done #b 0

MOD #remainder #a #b
MOVE #a #b
MOVE #b #remainder
JUMP $again

Now every trip through the loop begins with a question:

Is #b zero?

If it isn't, execution continues and performs another step.

If it is, execution jumps to $done.

Display the result

The algorithm tells us that when #b reaches zero, the value left in #a is the GCD.

So $done only needs to display #a:

$done
D.TXT #a
D.BLT

Put everything together:

#a r0
#b r1
#remainder r2

MOVE #a 1071
MOVE #b 462

$again
BEQ $done #b 0

MOD #remainder #a #b
MOVE #a #b
MOVE #b #remainder
JUMP $again

$done
D.TXT #a
D.BLT

Run it.

The Display shows:

21

We gave the computer two numbers, and it did the tedious part.

Trace the program

Let's walk through the loop once more, this time in terms of the program itself.

We begin with:

Register	Value
#a	1071
#b	462

Execution reaches:

$again
BEQ $done #b 0

#b contains 462.

462 is not equal to zero, so the branch is not taken. Execution continues to the next instruction.

MOD #remainder #a #b

calculates:

1071 MOD 462 = 147

and stores 147 in #remainder.

Then:

MOVE #a #b

changes #a to 462.

Next:

MOVE #b #remainder

changes #b to 147.

Finally:

JUMP $again

sends execution back to the beginning of the loop.

Now the CPU asks the same question again:

BEQ $done #b 0

but this time #b contains 147.

It still isn't zero, so another step begins.

The instructions haven't changed.

The values have.

Eventually, execution reaches $again with:

Register	Value
#a	21
#b	0

Now:

BEQ $done #b 0

takes the branch.

Execution moves to:

$done
D.TXT #a
D.BLT

and the program displays 21.

Try different values

Our program isn't limited to 1071 and 462.

Change the starting values:

MOVE #a 48
MOVE #b 18

Run it again.

The result is:

6

Try:

MOVE #a 17
MOVE #b 13

The result is:

1

Try:

MOVE #a 0
MOVE #b 462

The result is:

462

And:

MOVE #a 462
MOVE #b 0

also produces:

462

If both values begin as zero, this program produces zero.

Try some starting values of your own.

You can follow the values through the loop by hand if you're curious, or just let the computer do what computers are good at: repeat the same little operations until it's finished.

One algorithm, many inputs

We changed the starting values, but we didn't change the algorithm.

The instructions inside the loop stayed exactly the same.

That's one of the most useful ideas we've reached so far.

We didn't write a program that calculates:

gcd(1071, 462)

We wrote a program that performs the GCD algorithm on whatever starting values we give it.

The individual pieces are all familiar:

• registers hold the current values;
• MOD calculates a remainder;
• MOVE updates those values;
• BEQ decides when we're finished;
• JUMP repeats the work;
• the Display shows the result.

None of those instructions knows what a greatest common divisor is.

The CPU doesn't need to understand the whole problem.

It only needs to follow the next instruction.

The result comes from arranging simple operations so that each one prepares the values needed by the next.

---

In the 100-level, we've learned how a program can remember values, change them, make decisions from them, and repeat work until a condition is reached.

In this lesson, we combined those pieces into an algorithm that does something useful for many different starting values.

In NCL 201: Remembering Text, we'll start giving the computer something else to remember: text.