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.