Finding square root of an integer on MIPS assembly

问题:

hey how exactly can I find the square root of an integer using MIPS assembly?

回答1:

We can use an algorithm like the one submitted for this question and adapt it as needed. Before getting into MIPS, lets look at an implementation in 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;
}

The sqroot(n) function will compute and integer equivalent to the floor of the square root of n. So if you were to call sqroot(225) you would get 15 as expected, but sqroot(15) would return 3 instead of 3.87298.

From the C code, we can outline what the MIPS code will look like:

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

Please Note:

1. Be sure to Push and Pop the stack as needed. I left that out for simplicity.
2. When dividing by a power of 2, you can use the srl instruction.
3. For clarification and additional information on MIPS instructions, click here.

回答2:

I found Newton's method x = (x + n/x) / 2 unsatisfactory when operating with only integers, because the terminating condition is difficult to calculate accurately. n/2 is just a guess, and is almost always more iterations than necessary. Newton's method converges quadratically, and is not proportional to n, but rather sqrt(n). The other suggestion, "keep repeating until x stops changing" does not work either, because for non-perfect squares x will alternate between the floor and the ceiling of the root — because of integer mathematics the term n/x will alternate when x is slightly smaller or slightly larger than sqrt(n).

---

I took a digit-by-digit root calculation method from wikipedia, and created a MIPS version. It does not suffer from inefficiency (n/2) or ambiguity (floor(sqrt(n)) or ceil(sqrt(n))). Lookup table methods could return results more efficiently, but assuming a lookup table is unavailable, this is a good and reliable method.

First, I translated the C example to use only less-than (<) comparisons, because MIPS only provides a set-less-than slt comparison instruction.

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

Here is the resulting MIPS code:

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

You call it like any other MIPS procedure:

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

This procedure always returns $v0 = floor(sqrt($a0)) for positive arguments.

Beware: the code enters an infinite loop for negative arguments. Sanitize your input before calling this procedure.

回答3:

It is not in MIPS, but assembly nonetheless. The basic algorithm I found was based on the fact that the first n odd numbers added together = n^2.

So if you take advantage of that by reversing the process and subtracting from the number you would like to take the square root of, you can loop through to get either the exact answer, or an approximation. I believe its the root + 1 for non-perfect squares.

The idea being that the number of times you loop through is n, which is your square root.

Hope this helps.

   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

回答4:

You can try this algorithm, which gives the integer smaller than or equal to the square root of your number.

Suppose you want the square root of n. Then keep repeating the following calculations:

x = (x + n/x) / 2

Choose x = n to start and keep repeating until x stops changing.

回答5:

Here's a simple to understand algorithm for calculating the floor of the square root of a positive integer, in C:

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

It relies on the same principle as okstory's answer, in a slightly different manner.

Theory: Progressively increasing odd numbers are added to a partialSum, as long as the partialSum is less than the operand. The result is equal to the number of odd numbers summed to produce the partialSum.