在MIPS程序集上查找整数的平方根

Question

嘿，我怎么能使用MIPS汇编找到整数的平方根？

Answer 1

我们可以使用与针对该问题提交的算法类似的算法，并根据需要进行调整。在进入MIPS之前，让我们看一下用C实现：

//Function to compute sqroot(n)
int sqroot(int n) {
        int x = n;
        for (int i = 0; i < (n/2); i++)
             x = (x + n / x) / 2;

        return x;
}

该sqroot(n)函数将计算和等于的平方根底数的整数n。因此，如果您打电话给sqroot(225)您，您将获得15的预期sqroot(15)收益，但返回3而不是3.87298。

从C代码中，我们可以概述MIPS代码的外观：

In calling function:
    Load the number to be squared into $a0
    jal root

root:
    Initialize $t0 = n, $t1 = i = 0, $t2 = x = n = $a0, $t3 = n/2

Loop:
    Divide n/x
    Add x to n/x
    Divide (x + n/x) by 2
    Check if $t1 < $t3
    If it is, branch back to loop
    Else, move x into return register $v0

请注意：

1. 确保根据需要推入并弹出堆栈。为了简单起见，我将其省略。
2. 除以2的幂时，可以使用srl指令。
3. 有关MIPS说明的说明和其他信息，请单击此处。

Answer 2

我发现牛顿法x = (x + n/x) / 2在只操作整数时并不令人满意，因为终止条件很难准确计算。n/2只是一个猜测，几乎总是比必要的迭代更多。牛顿方法二次收敛，与 不成正比n，而是与 成正比sqrt(n)。另一个建议，“继续重复直到 x 停止变化”也不起作用，因为对于不完美的正方形x将在根的下限和上限之间交替 - 因为整数数学，该术语n/x将在x稍小或稍大时交替比sqrt(n)。

我从维基百科中采用了逐位根计算方法，并创建了一个 MIPS 版本。它不会受到低效 ( ) 或歧义 (或) 的影响。查找表方法可以更有效地返回结果，但假设查找表不可用，这是一个很好且可靠的方法。n/2floor(sqrt(n))ceil(sqrt(n))

首先，我将 C 示例翻译为仅使用小于 ( <) 比较，因为 MIPS 仅提供了小于设置的slt比较指令。

int isqrt(int num) {
  int ret = 0;
  int bit = 1 << 30; // The second-to-top bit is set

  // "bit" starts at the highest power of four <= the argument.
  while (num < bit) {
    bit >>= 2;
  }

  while (bit != 0) {
    if (num < ret + bit) {
      ret >>= 1;
    } else {
      num -= ret + bit;
      ret = (ret >> 1) + bit;
    }
    bit >>= 2;
  }
  return ret;
}

这是生成的 MIPS 代码：

isqrt:
  # v0 - return / root
  # t0 - bit
  # t1 - num
  # t2,t3 - temps
  move  $v0, $zero        # initalize return
  move  $t1, $a0          # move a0 to t1

  addi  $t0, $zero, 1
  sll   $t0, $t0, 30      # shift to second-to-top bit

isqrt_bit:
  slt   $t2, $t1, $t0     # num < bit
  beq   $t2, $zero, isqrt_loop

  srl   $t0, $t0, 2       # bit >> 2
  j     isqrt_bit

isqrt_loop:
  beq   $t0, $zero, isqrt_return

  add   $t3, $v0, $t0     # t3 = return + bit
  slt   $t2, $t1, $t3
  beq   $t2, $zero, isqrt_else

  srl   $v0, $v0, 1       # return >> 1
  j     isqrt_loop_end

isqrt_else:
  sub   $t1, $t1, $t3     # num -= return + bit
  srl   $v0, $v0, 1       # return >> 1
  add   $v0, $v0, $t0     # return + bit

isqrt_loop_end:
  srl   $t0, $t0, 2       # bit >> 2
  j     isqrt_loop

isqrt_return:
  jr  $ra

您可以像任何其他 MIPS 过程一样调用它：

addi  $a0, $zero, 15
jal   isqrt # v0 = result

此过程总是$v0 = floor(sqrt($a0))为正参数返回。

当心：代码为否定参数进入无限循环。在调用此过程之前清理您的输入。