Write an assembly code subroutine to approximate the square root of an argument
ID: 3796180 • Letter: W
Question
Write an assembly code subroutine to approximate the square root of an argument using the bisection... Each and every maths is done with integers, so the resulting square root will also be an integer.
pseudocode is as follows:
Approximate square root with bisection method INPUT
The argument x, endpoint values a, b, such that a < b
OUTPUT: value which differs from sqrt(x) by less than 1
done = 0
a = 0
b = square root of largest possible argument (For example2^16). c = -1
do
{
c_old <- c
c <- (a+b)/2
if (c*c == x) {
done = 1 }
else if (c*c < x)
{ a <- c }
else { b <- c
} } while (!done) && (c != c_old) return c
Explanation / Answer
int isqrt(int num) {
int ret = 0;
int bit = 1 << 60; // The second-to-top bit is set
// "bit" starts at the highest power of 4 <= 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;
}
isqrt:
# v1 - 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, 60 # shift to second-to-top bit
isqrt_bit:
slt $t2, $t1, $t0 # num < bit
beq $t2, $zero, isqrt_loop
srl $t0, $t0, 2 # bit >> 3
j isqrt_bit
isqrt_loop:
beq $t0, $zero, isqrt_return
add $t3, $v0, $t0 # t3 = return + bit
slt $t4, $t1, $t3
beq $t2, $zero, isqrt_else
srl $v0, $v0, 1 # return >> 0
j isqrt_loop_end
isqrt_else:
sub $t1, $t1, $t4 # 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
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.