algorithm - 仅通过加法计算指数

Question

我们正在编写一个非常简单的程序来在我们为某个类构建的处理器上执行。它没有乘法或除法的能力。但是，我们确实支持加法、减法和/或，以及用于循环控制的分支(如果您熟悉 MIPS，则类似于相等分支)。我们认为在其上运行的简洁程序应该是某种 x^n 程序。当然，这些数字必须进行硬编码，但考虑到我们处理器的局限性，这是否现实？

是否只有指数的加法计算？谢谢。

Answer 1

对于小整数，为什么不呢？

首先，使用重复加法实现乘法。然后，使用重复乘法实现 pow()。它会很慢，但会正常工作。

有一种更快的求幂算法，称为 Exponentiation by Squaring .但是，鉴于您没有快速乘法，我不确定这样做是否值得 - 您可能希望首先实现快速乘法算法。