4

嘿，我怎样才能使用 MIPS 程序集找到整数的平方根？

4

7 回答 7

9

我们可以使用类似为这个问题提交的算法，并根据需要进行调整。在进入 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 说明的说明和其他信息，请单击此处。
于 2013-07-26T06:06:07.560 回答
5

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

我从wikipedia中采用了逐位根计算方法，并创建了 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))。

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

于 2013-10-10T21:13:23.617 回答
3

它不在 MIPS 中，但在汇编中。我发现的基本算法是基于这样一个事实，即前 n 个奇数加在一起 ​​= n^2。

因此，如果您通过反转过程并减去您想要取平方根的数字来利用这一点，您可以循环获得确切的答案或近似值。我相信它是非完美正方形的根 + 1。

这个想法是你循环的次数是 n，这是你的平方根。

希望这可以帮助。

   mov eax, 9513135         ; eax = number to take square root of
    mov ebx, eax            ; make a copy of eax in ebx


    loopIt :
        sub ebx, count      ; count starts as 1, 3, 5, 7, 9
        inc count           ; count = even
        inc count           ; count = odd
        inc sqrt            ; gives sqrt value
        mov eax, sqrt
        cmp ebx, 0
        js timetoReturn     ; return value if signed num, aka goes over zero
        jnz loopIt


    timetoReturn :
        mov reg, eax            ; just outputting the value
于 2013-12-06T21:40:45.757 回答
1

你可以试试这个算法，它给出的整数小于或等于你的数字的平方根。

假设你想要 的平方根n。然后不断重复以下计算：

x = (x + n/x) / 2

选择x = n开始并不断重复，直到 x 停止变化。

于 2013-07-25T21:09:35.993 回答
0

这是一个简单易懂的算法，用于计算 C 中正整数平方根的下限：

int approx_sqrt(int x) {
    int result;
    for (int partialSum = 0, oddNum = 1; partialSum < x; partialSum += oddNum, oddNum +=2) result++;
    return result;
}

它依赖于与 okstory 的答案相同的原则，但方式略有不同。

理论：只要 partialSum 小于操作数，就会将逐渐增加的奇数添加到 partialSum。结果等于奇数的总和以产生 partialSum。

于 2015-03-02T03:31:12.060 回答
0

如果要计算 mips 中整数的平方根，首先需要将整数转换为浮点数。假设您要取平方根的数字存储在 $t1 中，那么其转换为浮点数将如下所示

mtc1 $t1, $f1
cvt.s.w $f1, $f1

现在您可以使用 sqrt.s 函数计算平方根。

sqrt.s $f1,$f1

所以现在 $f1 将保存存储在 $t1 中的整数的平方根

于 2021-03-31T17:52:30.550 回答
0

你们都错了。

您可以使用 sqrt.s 或 sqrt.d 汇编代码！例如）sqrt.s $f12, $f13

不要浪费时间来实现这些功能。

于 2019-05-20T02:58:01.500 回答