仅通过加法计算指数

Question

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

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

Answer 1

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

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

有一种更快的求幂算法，称为平方求幂。但是，鉴于您没有快速乘法，我不确定它是否值得 - 您可能想首先实现快速乘法算法。

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

Answer 3

与 Aequitarum 的解决方案类似，但对幂使用重复平方，对乘法使用重复加倍。对于较大的 x,y 应该更快：

int multiply(int x, int y) {
  int product = 0;
  int bitmask = 1;

  while (y >= bitmask) {
    if (y & bitmask) product += x;
    x += x;
    bitmask += bitmask;
  }
  return product;
}

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

  while (exponent >= bitmask) {
    if (exponent & bitmask) result = multiply(result, x);
    x = multiply(x, x);
    bitmask += bitmask;
  }
  return result;
}

Answer 4

这是非常现实的。几年前，处理器还没有可以执行乘法和除法等高级运算的 ALU。

乘法通常使用移位和加法来完成。这是一些伪汇编：（

; multiply registers a and b

; use c as high b
mov c,#0
; use d as low result
mov d,#0
; use e as high result
mov e,#0
.nextbit:
  ; shift low bit out of a
  shr a
  ; skip if zero
  bcc .noadd
    ; add b to result
    add d,b
    adc e,c
  .noadd:
  ; double b
  shl b
  rcl c
  ; test a
  cmp a,#0
bne .nextbit

请注意，两个字节值相乘的结果是一个两个字节值。）

一旦有了乘法，您就可以循环计算幂。

使用说明：

mov x,y = move y into x
shr x = shift right one bit
shl x = shift left one bit
rcl x = rotate left one bit with carry inserted
add x,y = add y to x
adc x,y = add y to x with carry
cmp x,y = compare x to y
bcc = branch on carry clear
bne = branch on not equal
#0 = literal number zero (as opposed to 0, which would be the address zero)

Answer 5

您可能会发现有关 乘法 ALU 的相关维基百科文章。通过加法和按位运算（与和或），您可以按一位一步实现乘法，而不必按照较小运算符的大小进行多次加法。

Answer 6

指数 n 的 k 次方：

exponent(n,k) {
   for(x=1..n)
      x = x + exponent(x,k-1)
}