NCL 109: Choosing Between Many Paths

In the last lesson, we changed our even-and-odd program from:

MOD #remainder #number 2

to:

MOD #remainder #number 3

That changed the possible remainders.

Dividing by 2 can leave:

0
1

Dividing by 3 can leave:

0
1
2

Our program still only had two paths.

Let's fix that.

Three possible results

Suppose we have:

#number 8
#remainder r0

MOD #remainder #number 3

The remainder will be one of three values:

0
1
2

We want the program to handle each one separately.

We already know how to branch when a value matches something:

BEQ $one #remainder 1

And if that branch does not happen, execution continues to the next instruction.

That next instruction can be another branch.

BEQ $one #remainder 1
BEQ $two #remainder 2

Now the program asks two questions in sequence.

First:

Is the remainder 1?

If not:

Is the remainder 2?

If neither branch happens, the remainder must be 0.

Handling all three cases

Here is a complete example:

#number 8
#remainder r0

MOD #remainder #number 3

BEQ $one #remainder 1
BEQ $two #remainder 2

D.TXT "R0"
JUMP $done

$one
D.TXT "R1"
JUMP $done

$two
D.TXT "R2"

$done
D.BLT

With:

#number 8

the program displays:

R2

because:

8 ÷ 3 leaves remainder 2

Following the branches

The two branch instructions are:

BEQ $one #remainder 1
BEQ $two #remainder 2

Let's see what happens for each possible remainder.

#remainder	First BEQ	Second BEQ	Path
0	Not taken	Not taken	Continue downward
1	Taken	Not reached	$one
2	Not taken	Taken	$two

If #remainder contains 1, the first branch succeeds and the CPU goes directly to:

$one

If it contains 2, the first branch fails, but the second succeeds.

If it contains 0, both branches fail.

Execution simply continues downward:

D.TXT "R0"

We do not need another branch for the zero case.

Once 1 and 2 have been ruled out, 0 is the only possibility left.

The fall-through case

The zero case is handled by falling through the branches.

BEQ $one #remainder 1
BEQ $two #remainder 2

D.TXT "R0"

If neither branch changes the path, the CPU reaches the instruction immediately below them.

This gives us a useful pattern:

BEQ $first #value 1
BEQ $second #value 2

-- default case
JUMP $done

$first
-- first case
JUMP $done

$second
-- second case

$done

The first branch checks one possibility.

If it fails, the next branch checks another.

If all of the branches fail, execution reaches the fall-through case.

Why the jumps are needed

Take another look at the first case:

D.TXT "R0"
JUMP $done

Why do we need the JUMP?

Without it:

D.TXT "R0"

$one
D.TXT "R1"

execution would continue directly into the next case.

A remainder of 0 would write both:

R0R1

The JUMP sends execution past the other cases once one path has finished.

The same is true for the $one path:

$one
D.TXT "R1"
JUMP $done

The final case does not need a jump because it is already immediately before $done.

Putting it back into the loop

Now let's return to the program from NCL 108 and handle all three possible remainders.

#number r0
#remainder r1
#limit 10

MOVE #number 1

$again
D.TXT #number
D.TXT ":"

MOD #remainder #number 3

BEQ $one #remainder 1
BEQ $two #remainder 2

D.TXT "R0 "
JUMP $next

$one
D.TXT "R1 "
JUMP $next

$two
D.TXT "R2 "

$next
INC #number
BLE $again #number #limit

D.BLT

The program displays:

1:R1 2:R2 3:R0 4:R1 5:R2 6:R0 7:R1 8:R2 9:R0 10:R1 

Each number is divided by 3.

The remainder determines which path the program follows.

Following a few numbers

Let's trace three consecutive values.

For 6:

6 ÷ 3 leaves remainder 0

Both BEQ instructions fail, so execution falls through to the R0 path.

For 7:

7 ÷ 3 leaves remainder 1

The first BEQ succeeds, so execution branches to $one.

For 8:

8 ÷ 3 leaves remainder 2

The first BEQ fails, the second succeeds, and execution branches to $two.

#number	#remainder	Path
6	0	Fall through
7	1	$one
8	2	$two

Then the pattern repeats.

Chaining conditions

What we have built is a chain of conditions:

BEQ $one #remainder 1
BEQ $two #remainder 2

A conditional branch that is not taken does not stop the program.

The CPU continues to the next instruction.

That means several conditional branches can be placed one after another to choose between several possible paths.

The program tests each condition in order until one succeeds.

If none succeeds, the fall-through case handles whatever remains.

Try it

Change:

MOD #remainder #number 3

to:

MOD #remainder #number 4

Now the possible remainders are:

0
1
2
3

The program only handles:

0
1
2

Add another branch for the new case.

You will need a new label:

$three

and another output path:

D.TXT "R3 "

Decide where the new BEQ belongs in the chain.

Then trace one number that produces each possible remainder.

Make sure the program handles all four cases separately.

---

In NCL 110: Combining Conditions, we'll make several branches work together to describe a single larger condition.