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

Question

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 x²

trincot · Accepted Answer

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

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

Answers (1)

Related Questions