仅通过加法计算指数

Question

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

对指数有额外的计算吗？谢谢.

Answer 1

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

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

有一个更快的求幂算法,称为Squaring的Exponentiation.但是,鉴于您没有快速乘法,我不确定它是否值得 - 您可能希望首先尝试实现快速乘法算法.

Answer 2

符合dmazzoni对c风格语法的反应:

int mulitply(int x, int y)
{
    int product;

    for (int i = 0; i<y; i++)
       product += x;

    return product;
}

int power(int x, int exponent)
{
    int result = 1;

    for (int i = 0; i < exponent; i++)
        result = multiply(result, x);

    return result;
}