How can I implement exponentation into Little Man Computer?

Question

My friend and I have been working at this for hours but can't seem to figure it out. We're trying to code a program in LMC assembly that accepts two inputs: one for an integer, and the other for another integer to use as an exponent.

// inputs
        INP 
        STA sum
        STA n
        STA mCount
        ADD one
        STA j
        INP
        STA exponent
        STA i
// loop 1 (mult)
mult    LDA j
        BRZ exloop
        SUB one
        STA j
        LDA sum
        ADD n
        STA sum
        LDA mCount
        SUB one
        STA mCount
        BRA mult
// loop 2 (exp)
exloop  LDA i
        BRZ end
        SUB one
        STA i
        BRA mult
// end
end     LDA sum
        OUT
        HLT
// variables
sum     DAT
mCount  DAT
n       DAT
j       DAT
exponent DAT
i       DAT
one     DAT 1

This is the latest bit of code I have for it. It seems to only work for square numbers. Here, I've implemented a 'nested loop', where the number multiplies by itself an amount of times equal to the exponent.

I feel like I'm only having this much trouble because we only started using LMC two days ago x-D. It's very fun though. Appreciate any help y'all can give!

Answer 1

There are a few issues in your attempt:

• sum starts out as the value of the first input, i.e. the base of the exponentiation. But if the power (second input) would be zero, the sum is already too large, as the outcome should then be 1. So the starting value for sum is not correct

• j is initialised as one more as the base (first input), which means the inner loop iterates that many times. This cannot be correct. For instance, if the first input is 3, then if it needs to be multiplied with itself, then the number of iterations should be 3 (to move the sum from 0 to 3, then from 3 to 6, and finally from 6 to 9), not 4.

• When the outer loop repeats, some variables are not reset to their original values. For instance, j will still be zero (the result of the first iteration of the outer loop), and so the inner loop will not iterate anymore.

Not a problem, but the decreasing of mCount serves no apparent purpose. Its value is never tested or used later.

To get it right, it will help to first write the algorithm in some pseudo code. For instance, here is how it could be done in a simple JavaScript function taking two inputs:

function power(base, exp) {    
    let result = 1;    
    while (exp > 0) {
        exp--;
        // Here we multiply base with result and store in product:
        let product = 0;
        let countdown = base;
        while (countdown > 0) {
            countdown--;
            product += result;
        }
        result = product;
    }
    return result;
}

Now add LMC code to match it:

function power(base, exp) {    
    let result = 1;    
    // LDA one
    // STA result
    
    while (exp > 0) {
    // outerloop LDA exp
        // BRZ output
        exp--;
        // SUB one
        // STA exp
        let product = 0;
        // LDA zero
        // STA product
        let countdown = base; 
        // LDA base
        while (countdown > 0) {
        // innerloop BRZ exloop
            countdown--;
            // SUB one
            // STA countdown
            product += result;
            // LDA product
            // ADD result
            // STA product
        }
        // LDA countdown
        // BRA innerloop
        result = product;
        // exloop LDA product
        // STA result
    }
    // BRA outerloop
    return result;
}

So we finally arrive at:

#input: 3 4
          LDA one
          STA result
          INP
          STA base
          INP
          STA exponent

outerloop LDA exponent
          BRZ end
          SUB one
          STA exponent
          LDA zero
          STA product
          LDA base
innerloop BRZ exloop
          SUB one
          STA countdown
          LDA product
          ADD result
          STA product
          LDA countdown
          BRA innerloop
exloop    LDA product
          STA result
          BRA outerloop

end       LDA result
          OUT
          HLT

// variables
base      DAT
exponent  DAT
countdown DAT
result    DAT
product   DAT
// constants
one       DAT 1
zero      DAT 0


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

You can run this program with a little LMC emulator here on the spot.