如何在小人计算机中实现求幂？

Question

我和我的朋友已经为此工作了几个小时，但似乎无法弄清楚。我们正在尝试在 LMC 汇编中编写一个程序，该程序接受两个输入：一个用于整数，另一个用于另一个用作指数的整数。

// 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

这是我拥有的最新代码。它似乎只适用于平方数。在这里，我实现了一个“嵌套循环”，其中数字乘以等于指数的次数。

我觉得我遇到这么多麻烦是因为我们两天前才开始使用 LMC x-D。不过这很有趣。感谢你们提供的任何帮助！

Answer 1

您的尝试中存在一些问题：

• sum

  从第一个输入的值开始，即求幂的底数。但如果功率（第二个输入）为零，则

  sum

  已经太大，因为结果应该为 1。因此

  sum

  的起始值不正确

• j

  被初始化为基数（第一个输入），这意味着内部循环会迭代那么多次。这不可能是正确的。例如，如果第一个输入是 3，那么如果需要与自身相乘，则迭代次数应该为 3（将和从 0 移动到 3，然后从 3 移动到 6，最后从 6 移动到 9） ），而不是 4。

• 当重复外层循环时，某些变量不会重置为原始值。例如，

  j

  仍然为零（外循环第一次迭代的结果），因此内循环将不再迭代。

不是问题，但

mCount

的减少没有明显的目的。它的值以后从未被测试或使用过。

为了得到正确的结果，首先用一些伪代码编写算法会有所帮助。例如，以下是如何在一个接受两个输入的简单 JavaScript 函数中完成此操作：

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;
}

现在添加LMC代码来匹配它：

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;
}

所以我们最终得出：

#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>

您可以在此处使用一个小型 LMC 模拟器来运行此程序。