Search code examples
algorithmlittle-man-computer

Write LMC program that calculate sum of numbers input by user. Display summation before halting

I am trying to solve this code challenge:

Write a LMC program that calculates the sum of numbers provided by the user. Display the summation as output before halting the program. If the user has provided less than or equal to ten input values, then only sum even numbers. Odd numbers are ignored. If the user has provided more than ten values, then only sum any odd numbers subsequent to the tenth input. The existing summation of even numbers shall remain. If the user enters zero, at any point, then the summation is displayed.

For example:

Input values: 3, 3, 4, 0
Result:4

Input values: 2, 3, 7, 0
Result: 2

Input values: 1, 2, 3, 4, 5, 6, 7, 8, 9, 8, 7, 6, 5, 4, 3, 0
Result: 43

My code

This is the code I ended up with:

start
             INP
             STA input
             BRZ halt
             LDA inputCounter

             SUB ten
             BRP afterTen

// Input <= 10
             LDA input
             STA isEven
             SUB one
             BRP oddNumber
             LDA isEven
             ADD one

             STA isEven
             SUB two
             BRZ evenNumber
oddNumber    LDA inputCounter
             ADD one
             STA inputCounter
             BRA start

evenNumber   LDA input
             ADD evenSum
             STA evenSum
             LDA inputCounter
             ADD one
             STA inputCounter
             BRA start

// Input > 10
afterTen     LDA input
             STA isEven
             SUB one
             BRP evenAfterTen
             LDA isEven
             ADD one
             STA isEven
             SUB two
             BRZ oddAfterTen
evenAfterTen LDA inputCounter
             ADD one
             STA inputCounter
             BRA start

oddAfterTen  LDA input
             ADD oddSum
             STA oddSum
             LDA inputCounter
             ADD one
             STA inputCounter
             BRA start

// Display sum
halt         LDA evenSum
             ADD oddSum
             OUT
             HLT
// Variables
evenSum      DAT 0
oddSum       DAT 0
inputCounter DAT 0
isEven       DAT 0
input        DAT 0
// Constants
one          DAT 1
two          DAT 2
ten          DAT 10

Problem

When running the above for the first example input, I already get the wrong output (0 instead of the expected 4):

enter image description here

Analysis

When I step through the code, I see that after having read the first input it gets into the correct section (Input <= 10), and correctly identifies the first number as odd. The input counter is correctly incremented, and the next input is taken.

So it continues for the other inputs, and once 0 is input, it correctly jumps to the last section to output the result.

But for the input 4 it also jumps to the oddNumber section, and doesn't execute the code that subtracts 2 from it. By consequence the necessary addition to evenSum is not performed either. Why is the BRP instruction not branching?

Where is my mistake?

Solution

  • The problem is in the part that checks whether a number is even. That code will first subtract 1, and if that instruction does not lead to negative overflow, it is concluded that the number is odd! This is obviously not (always) true. For instance if you start out with 2, then it wrongly concludes it is odd.

    To test whether a number is odd, you would need (under LMC's limitations) a loop where you repeatedly subtract the number 2 until you get to zero or get negative overflow.

    As you have similar code in the second half of your code, the problem is repeated there as well.

    Here is a correction:

    #input: 1 2 3 4 5 6 7 8 9 8 7 6 5 4 3 0
start        INP
             STA input
             BRZ halt
             LDA inputCounter
             SUB ten
             BRP afterTen

// First ten inputs:
             LDA input
repeat1      STA isEven
             SUB two        # subtract 2
             BRP continue   
             BRA oddNumber  # negative overflow! => result was -1, input is odd
continue     BRZ evenNumber # zero => input is even
             BRA repeat1    # neither: continue to subtract 2...

evenNumber   LDA input
             ADD evenSum
             STA evenSum
oddNumber    LDA inputCounter
             ADD one
             STA inputCounter
             BRA start

// From 10th input onwards:
afterTen     LDA input
repeat2      STA isEven
             SUB two
             BRP continue2
             BRA oddAfterTen
continue2    BRZ evenAfterTen
             BRA repeat2
oddAfterTen  LDA input
             ADD oddSum
             STA oddSum
evenAfterTen LDA inputCounter
             ADD one
             STA inputCounter
             BRA start

// Display sum
halt         LDA evenSum
             ADD oddSum
             OUT
             HLT
// Variables
evenSum      DAT 0
oddSum       DAT 0
inputCounter DAT 0
isEven       DAT 0
input        DAT 0
// Constants
one          DAT 1
two          DAT 2
ten          DAT 10


<script src="https://cdn.jsdelivr.net/gh/trincot/[email protected]/lmc.js"></script>

    Remarks

    1. There is no need for a separate evenSum and oddSum. You can just add to the same sum.

    2. There is some code repetition: two pieces of code perform an odd/even test. You can avoid this repetition by adding 1 to isEven when dealing with the inputs after the first ten, and then you can use the same code to perform the odd/even test, as by adding 1 you inverse the outcome.

    3. isEven is a mailbox that is not really needed: the odd/even test can be done directly on the accumulator value without ever storing it to isEven.

    4. As the Little Man Computer has a reset feature, which restarts the program without resetting the mailbox contents to their original values (including DAT), you would get inconsistent output as in particular the evenSum and oddSum "variables" would then not be reset. To avoid this, add instructions to set the sum(s) to zero at the very start of the program.

    Here is the code with those improvements:

    #input: 1 2 3 4 5 6 7 8 9 8 7 6 5 4 3 0
             LDA zero
             STA sum   # To avoid problems after LMC-reset
start        INP
             STA input
             BRZ halt
             LDA inputCounter
             SUB ten
             BRP afterTen                 
             LDA input
             BRA testeven
             
afterTen     LDA input
             ADD one  # By adding one, we inverse the odd/even test

testeven     SUB two        # subtract 2
             BRP continue   
             BRA oddNumber  # negative overflow! => result was -1, input is odd
continue     BRZ evenNumber # zero => input is even
             BRA testeven   # neither: continue to subtract 2...

evenNumber   LDA input
             ADD sum
             STA sum
oddNumber    LDA inputCounter
             ADD one
             STA inputCounter
             BRA start

// Display sum
halt         LDA sum
             OUT
             HLT
// Variables
sum          DAT 0
inputCounter DAT 0
input        DAT 0
// Constants
zero         DAT 0
one          DAT 1
two          DAT 2
ten          DAT 10


<script src="https://cdn.jsdelivr.net/gh/trincot/[email protected]/lmc.js"></script>