Input three numbers into the LMC and output them largest to smallest?

Question

So, I've managed to get the bulk of the problem done however I can only output from largest to smallest if the input values are ascending? first = 10, second = 20, third = 30. How would I output this properly if the values were different? (Say, 5,1,3? for example)

This is what I have so far:

        INP
        STA first
        INP
        STA second 
        INP
        STA third
        SUB first
        BRP branch1 
        LDA second 
        STA third 
branch1 LDA third 
        SUB second
        BRP branch2 
        LDA first
        STA third 
branch2 LDA third 
        OUT
        LDA first
        SUB second
        BRP branch3
        LDA second
        OUT
branch3 LDA first
        OUT
        HLT
first   DAT
second DAT
third   DAT

You received some answers. Please leave some feedback and if satisfied, you can mark one answer as accepted. — trincot, Oct 09 '21 at 07:08

score 1 · Answer 1 · answered Oct 08 '21 at 15:25

I suggest that you write the C or pseudo code for this. It is only going to be a line or two or so, and that will clarify your thinking.

Your pseudo/C code will contain if-then-else statements. Here's the pattern for if-then-else in high level C, then repeated in low level C. When you translate your if-then-else statements, follow this pattern:

if ( <condition> ) {
    <then-part>
}
else {
    <else-part>
}

Let's note that only one of the then-part and else-part should run.

The same control structure, if-then-else, in the if-goto-label style of assembly language:

    if <condition> is false goto elsePart1;
    <then-part>
    goto endIf1;
elsePart1:
    <else-part>
endIf1:

Let's first note that labels do not execute — the processor doesn't see them as they are removed by the assembler in generating machine code. The processor only sees & executes machine code instructions, and labels do not have machine code.

Here's how the if-then-else works in if-goto-label: when the condition is false, it will skip over the then-part to run the else-part instead. But on condition true, it will not branch and so execute the then-part. After execution of the then-part we need to skip over the else-part and that is the reason for the unconditional branch and the endIf1: label in the if-goto-label version. (Without that unconditional branch, it would run the else-part after the then-part, which would be bad.) It is also important that after an if-then-else statement, the program runs the next statement, regardless of whether its then-part fired or its else-part fired.

If you have multiple if-then-else statements, just use a different numbering for its labels. Nested if-then-else's should still follow this pattern — suggest to translate outer ones first, then inner ones, but the other order will work as well. It can also be done in program order, but that makes it harder to follow these simple patterns.

score 1 · Accepted Answer · answered Oct 08 '21 at 19:42

Some issues:

When you do this:
```
LDA second
STA third 
```
...you loose the original input for third, and so it is impossible to still produce the correct output. The same happens at the other places where you execute STA. Instead you could consider to swap values. Typically you need a temporary variable for that (an additional DAT). For instance, if you want to swap second with third, then:
```
LDA second
STA temp
LDA third
STA second
LDA temp
STA third
```
You start with a comparison between first and third and when you detect that first is greater than third you copy second to third. It is strange that you decide on involving second at this point (about which you made no conclusions). It would make more sense to do something with first. If you would swap first with third then you get to the "invariant" that first is now guaranteed to be not greater than third, whether you branched to branch1 or arrived at that label from the previous instruction. This is a first step in getting the input sorted.
If BRP branch3 results in a jump to branch3 you will end up with only 2 outputs instead of 3. None of the three OUT instructions should be skipped over. Or else you should add more OUT instructions so that in each path of execution there are always exactly 3 of them executed.

Here is the corrected script, which you can run here:

#input: 3 1 2
        INP
        STA first
        INP
        STA second 
        INP
        STA third
        SUB first
        BRP branch1
        LDA first   # don't deal with second, but with first
        STA temp    # use temp to perform swap first <--> third
        LDA third
        STA first
        LDA temp
        STA third
branch1 LDA third   # at this point we know first <= third
        SUB second
        BRP branch2 
        LDA second  # don't deal with first, but with second
        STA temp    # use temp to perform swap second <--> third
        LDA third
        STA second
        LDA temp
        STA third 
branch2 LDA third   # at this point we know first <= third && second <= third 
        OUT
        LDA first
        SUB second
        BRP branch3
        LDA second
        OUT
        LDA first   # We cannot use branch3 here, as there we still output second
        OUT
        HLT
branch3 LDA first
        OUT
        LDA second
        OUT
        HLT
first   DAT
second  DAT
third   DAT
temp    DAT

<script src="https://cdn.jsdelivr.net/gh/trincot/lmc@v0.816/lmc.js"></script>

Input three numbers into the LMC and output them largest to smallest?

2 Answers2