CODEWITHSUNDEEP
assemblymips
Sly Cooper
Sly Cooper

Reputation: 79

Finding square root of an integer on MIPS assembly

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

Upvotes: 4

Views: 48929

Answers (8)

Tanvir Ahmed Khan
Tanvir Ahmed Khan

Reputation: 19

Here is a Procedure/Function in MIPS32 for finding the square root of an integer.

SQUARE_ROOT:

    # res = n
    # while(i < n/2)
    # res = (res + n / res) / 2;
    
    addi $sp, $sp, -20
    sw   $ra, 16($sp)               # Saving the return address into stack
    sw   $s3, 12($sp)               # Saving other register values
    sw   $s2,  8($sp)
    sw   $s1,  4($sp)
    sw   $s0,  0($sp)
    
    add  $s3, $zero, $a0            # s3 = n
    add  $s0, $zero, $a0            # res = n
    
    addi $a1, $zero, 2              # A = N, B = 2
    jal DIVISON                     # Divison(n, 2)
    
    add $s1, $zero, $v0             # s1 = n / 2
    addi $s2, $zero, 0              # idx (s2) = 0
    
SQUARE_ROOT_LOOP:
    beq  $s1, $s2, EXIT_SQUARE_ROOT # if (idx == n/2) break
    add $a0, $s3, $zero             # A = n
    add $a1, $s0, $zero             # B = res
    jal DIVISON                     # Divison(n, res)
    
    add  $s0, $s0, $v0              # res = res + (n/res)
    add  $a0, $zero, $s0            # A = res + (n/res)
    addi $a1, $zero, 2              # B = 2
    
    jal DIVISON                     # Divison((res + (n / res), 2)
    add  $s0, $zero, $v0            # res = res + (n / res) / 2
    
    addi $s2, $s2, 1                # idx++
    j SQUARE_ROOT_LOOP
    
EXIT_SQUARE_ROOT:       
    lw $s0, 0($sp)                  # Retrieving data stored in stack
    lw $s1, 4($sp)
    lw $s2, 8($sp)
    lw $s3, 12($sp)
    lw $ra, 16($sp)                 # Retrieving Return Address
    
    addi $sp, $sp, 20               # Reseting stack pointer 
    jr $ra                              

DIVISON:
    # While (A >= B) A -= B; result++
    add  $sp, $sp, -12              # Allocating Stack Memory
    sw   $s2, 8($sp)                # Storing register values
    sw   $s1, 4($sp)                
    sw   $s0, 0($sp)
    
    addi $s0, $zero, 0              # result (s0) = 0
    add  $s1, $zero, $a0            # s1 = A
    add  $s2, $zero, $a1            # s2 = B
DIV_LOOP:
    blt  $s1, $s2, EXIT_DIV         # If (A < B) break
    sub  $s1, $s1, $s2              # A -= B
    addi $s0, $s0, 1                # result++
    j DIV_LOOP
EXIT_DIV:
    add $v0, $zero, $s0             # v0 = result
    
    lw   $s2, 8($sp)                # restoring register values
    lw   $s1, 4($sp)                
    lw   $s0, 0($sp)
    addi $sp, $sp, 12               # restoring stack pointer
    
    jr $ra

Upvotes: 0

Talha Ahmed
Talha Ahmed

Reputation: 1

If you want to calculate the square root of an integer in mips you will first need to convert the integer to floating-point. Assuming the number you want to take square root of is stored in $t1 then its conversion to floating point will look like this

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

Now you can calculate the square root using sqrt.s function.

sqrt.s $f1,$f1

so now $f1 will hold the square root of integer that was stored in $t1

Upvotes: 0

Jaehyeon Park
Jaehyeon Park

Reputation: 23

You guys all wrong.

You can use sqrt.s or sqrt.d assembly code! ex) sqrt.s $f12, $f13

Don't waste your time to implementing those functions.

Upvotes: 0

user2128970
user2128970

Reputation:

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.

Upvotes: 10

Alexander
Alexander

Reputation: 63271

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.

Upvotes: 0

okstory
okstory

Reputation: 31

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

Upvotes: 3

whitehat101
whitehat101

Reputation: 2549

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.

Upvotes: 5

Patrik
Patrik

Reputation: 2692

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.

Upvotes: 1

Related Questions