Trouver la racine carrée d'un entier sur MIPS de l'assemblée

J'ai trouvé la méthode de Newton x = (x + n/x) /2 insatisfaisante en cas de fonctionnement avec seulement entiers, parce que la condition d'arrêt est difficile à calculer avec précision. n/2 est juste une supposition, et est presque toujours plus d'itérations que nécessaire. La méthode de Newton converge quadratiquement, et n'est pas proportionnelle à n, mais plutôt sqrt(n). La suggestion de l'autre, "répéter jusqu'à ce que x de cesse de changer" ne fonctionne pas non plus, parce que pour les non-carrés parfaits x va alterner entre le plancher et le plafond de la racine — entier en raison de mathématiques, le terme n/x alternent lorsque x est légèrement plus petit ou légèrement plus grand que sqrt(n).

---

J'ai pris un chiffre par chiffre de la racine de la méthode de calcul de wikipédia, et a créé une version MIPS. Il ne souffre pas de l'inefficacité (n/2) ou d'ambiguïté (floor(sqrt(n)) ou ceil(sqrt(n))). La table de méthodes peut retourner des résultats de manière plus efficace, mais en supposant une table de recherche n'est pas disponible, c'est une bonne méthode fiable et.

Tout d'abord, j'ai traduit le C exemple d'utilisation seulement moins (<) les comparaisons, car MIPS seulement fournit un ensemble moins de slt comparaison de l'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;
}

Ici est celle du 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

Vous l'appelez comme n'importe quel autre MIPS procédure:

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

Cette procédure toujours retourne $v0 = floor(sqrt($a0)) pour arguments positifs.

Méfiez-vous: le code entre dans une boucle infinie pour arguments négatifs. Désinfecter votre entrée avant l'appel de cette procédure.

OriginalL'auteur whitehat101

Vous pouvez essayer cet algorithme, ce qui donne le plus petit entier supérieur ou égal à la racine carrée de votre numéro.

Supposons que vous voulez la racine carrée de n. Alors continuez à répéter les calculs suivants:

x = (x + n/x) /2

Choisir x = n de départ et répétez jusqu'à ce que x de cesse de changer.

OriginalL'auteur Patrik

Les gars, vous tous mauvais.

Vous pouvez utiliser sqrt.s ou sqrt.d de l'assemblée de code!
ex) sqrt.s $f12, $f13

Ne perdez pas votre temps à la mise en œuvre de ces fonctions.

OriginalL'auteur Jaehyeon Park