computer-sciencelittle-man-computer

How to add cx^2 to a+bx in LMC, with overflow output as 999?


I need to write an LMC program to calculate the value of a+bx+cx² for given values of a, b, c and x. If the result exceeds 999, then it needs to output 999; if less than 999, then output the result.

The a+bx+x² part (without c-coefficient) is already done by @trincot in this answer:

         INP
         STA a
         INP
         STA b
         INP
         STA x
         STA x2
         LDA z # "inverse" ans
         SUB a # do this first
loop     STA ans
         LDA x
         BRZ output
         SUB one
         STA x
         LDA ans
         SUB x2  # subtract both x...
         BRP continue
         BRA overflow
continue SUB b   # ... and b
         BRP loop

overflow LDA zero  # prepare for outputing 999 (overflow)
         STA ans
output   LDA z
         SUB ans # 999 - (999 - (a + bx + x^2))
         OUT
         HLT

a        DAT 0
b        DAT 0
x        DAT 0
x2       DAT 0
z        DAT 999
ans      DAT 0

zero     DAT 0
one      DAT 1

But have no idea how to modify this code so to add c times


Solution

  • To minmise on the logic you need, you could calculate 𝑎 − 𝑏𝑥 − 𝑐𝑥² as follows:

            𝑎 − (𝑏 − 𝑐𝑥)𝑥

    This has a recursive pattern, so that the logic to use for the inner expression 𝑏 − 𝑐𝑥 is the same as the logic for the outer expression once you have the result for the inner one: 𝑎 − 𝑝𝑥. If we swap values in the variables 𝑎, 𝑏 and 𝑐, we can execute this sequence:

            𝑐 := 𝑏 − 𝑐𝑥
            𝑏 := 𝑎
            𝑐 := 𝑏 − 𝑐𝑥

    ...and then 𝑐 will be the final answer. Clearly we can put the following in a loop that is executed twice:

            𝑐 := 𝑏 − 𝑐𝑥
            𝑏 := 𝑎

    The second thing to consider is what the code already does. I quote from my answer from where that code originates:

    it is indeed difficult to detect overflow (more than 999) because typically an LMC accumulator cannot store greater values, and the accumulator's value is not defined (in the specification) when such overflow happens, nor is it specified whether the "negative" flag will be set. So there is really nothing we can use to detect such overflow which would be compatible on all LMC emulators.

    The trick is to calculate the expression as 999 − (𝑎 − 𝑏𝑥 − 𝑥²) and detect negative overflow (below 0), for which we have the BRP instruction.

    So here we would perform that "inversion" at the start of the loop, then keep subtracting (instead of adding) and finally (if no negative overflow occurred) invert the result again.

    Here is an implementation of that idea -- you can run it here:

    #input: 2 5 2 3
             INP
             STA a
             INP
             STA b
             INP
             STA c
             INP
             STA x
    
             LDA one
    repeat   STA counter # Execute twice: b + c*x => c, and a => b
             LDA max
             SUB b # invert b
             BRA step
    loop     STA c
             LDA inv
             SUB x
             BRP step
             LDA max # indicate overflow
             OUT
             HLT
    step     STA inv
             LDA c
             SUB one
             BRP loop
             LDA max
             SUB inv # re-invert and store in c
             STA c
             LDA a
             STA b # The second time b takes the role of a
             LDA counter
             SUB one
             BRP repeat
             LDA c
             OUT
             HLT
    
    a        DAT
    b        DAT
    c        DAT
    x        DAT
    counter  DAT
    inv      DAT
    
    zero     DAT 0
    one      DAT 1
    max      DAT 999
    
    
    <script src="https://cdn.jsdelivr.net/gh/trincot/lmc@v0.816/lmc.js"></script>