assembly - programas - Encontrar la raíz cuadrada de un entero en el ensamblado de MIPS

potencia de un numero en ensamblador

Question

hey ¿cómo exactamente puedo encontrar la raíz cuadrada de un entero usando el ensamblado MIPS?

Answer 1

Aquí hay un algoritmo fácil de entender para calcular el piso de la raíz cuadrada de un entero positivo, en C:

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

Se basa en el mismo principio que la respuesta de okstory, de una manera ligeramente diferente.

Teoría: Se agregan números impares progresivamente crecientes a unSum parcial, siempre que elSuma parcial sea menor que el operando. El resultado es igual al número de números impares sumados para producir elSum parcial.

Answer 2

Encontré el método de Newton x = (x + n/x) / 2 insatisfactorio cuando operaba solo con números enteros , porque la condición de terminación es difícil de calcular con precisión. n/2 es solo una suposición, y casi siempre es más iteraciones de lo necesario. El método de Newton converge cuadráticamente , y no es proporcional a n , sino más bien sqrt(n) . La otra sugerencia, "seguir repitiendo hasta que x deje de cambiar", tampoco funciona, porque para los cuadrados no perfectos x alternará entre el piso y el techo de la raíz; debido a las matemáticas enteras, el término n/x se alternará cuando x sea ligeramente más pequeño o ligeramente más grande que sqrt(n) .

Tomé un método de cálculo de raíz dígito por dígito de wikipedia , y creé una versión de MIPS. No sufre de ineficiencia ( n/2 ) o ambigüedad ( floor(sqrt(n)) o ceil(sqrt(n)) ). Los métodos de la tabla de búsqueda pueden devolver resultados de manera más eficiente, pero suponiendo que una tabla de búsqueda no está disponible, este es un método bueno y confiable.

Primero, traduje el ejemplo C para usar solo comparaciones menores que ( < ), porque MIPS solo proporciona una instrucción de comparación sin set-less- 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;
}

Aquí está el código MIPS resultante:

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

Lo llamas como cualquier otro procedimiento MIPS:

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

Este procedimiento siempre devuelve $v0 = floor(sqrt($a0)) para argumentos positivos .

Cuidado : el código ingresa un bucle infinito para argumentos negativos . Desinfecte su entrada antes de llamar a este procedimiento.

Answer 3

No está en MIPS, pero ensamblar de todos modos. El algoritmo básico que encontré se basaba en el hecho de que los primeros n números impares sumados = n ^ 2.

Por lo tanto, si aprovecha esto invirtiendo el proceso y restando del número del que desea tomar la raíz cuadrada, puede recorrerlo para obtener la respuesta exacta o una aproximación. Creo que es la raíz + 1 para cuadrados no perfectos.

La idea es que la cantidad de veces que ingresas es n, que es tu raíz cuadrada.

Espero que esto ayude.

 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

Answer 4

Podemos usar un algoritmo como el presentado para esta pregunta y adaptarlo según sea necesario. Antes de entrar en MIPS, veamos una implementación en 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;
}

La función sqroot(n) calculará un entero equivalente al piso de la raíz cuadrada de n . Entonces, si llamaras a sqroot(225) obtendrías 15 como se esperaba, pero sqroot(15) devolvería 3 en lugar de 3.87298.

Desde el código C, podemos delinear cómo se verá el código 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

Tenga en cuenta:

1. Asegúrese de presionar y abrir la pila según sea necesario. Lo dejé por simplicidad.
2. Al dividir por una potencia de 2, puede usar la instrucción srl.
3. Para aclaración e información adicional sobre las instrucciones de MIPS, haga clic aquí .

Answer 5

Puede probar este algoritmo, que da el entero menor o igual que la raíz cuadrada de su número.

Supongamos que quiere la raíz cuadrada de n . Entonces sigue repitiendo los siguientes cálculos:

x = (x + n/x) / 2

Elija x = n para comenzar y siga repitiendo hasta que x deje de cambiar.