Code source racine carrée trouvé sur le réseau

Question

Je suis à la recherche d'un algorithme pour le calcul de la racine carrée et trouvé ce fichier source. Je voudrais essayer de le reproduire car il semble assez simple mais je ne peux pas le relier à un algorithme connu (Newton, Babylone ...). Pouvez-vous me dire le nom?

int sqrt(int num) { 
    int op = num; 
    int res = 0; 
    int one = 1 << 30; // The second-to-top bit is set: 1L<<30 for long 

    // "one" starts at the highest power of four <= the argument. 
    while (one > op) 
     one >>= 2; 

    while (one != 0) { 
     if (op >= res + one) { 
      op -= res + one; 
      res += 2 * one; 
     } 
     res >>= 1; 
     one >>= 2; 
    } 
    return res; 
} 

Answer 1

Comme @Eugene Sh. références, c'est la méthode classique « chiffre par chiffre » fait pour calculer la racine carrée. Appris en base 10 quand de telles choses étaient enseignées à l'école primaire.

Le code OP ne permet pas non plus de sélectionner des numéros. sqrt(1073741824) --> -1 plutôt que prévu 32768. 1073741824 == 0x40000000. En outre, il échoue la plupart (toutes?) Valeurs ceci et plus. Bien sûr, le sqrt(some_negative) de l'OP est également un problème.

alternative candidat: aussi here

unsigned isqrt(unsigned num) { 
    unsigned res = 0; 

    // The second-to-top bit is set: 1 << 30 for 32 bits 
    // Needs work to run on unusual platforms where `unsigned` has padding or odd bit width. 
    unsigned bit = 1u << (sizeof(num) * CHAR_BIT - 2); 

    // "bit" starts at the highest power of four <= the argument. 
    while (bit > num) 
    bit >>= 2; 

    while (bit > 0) { 
    if (num >= res + bit) { 
     num -= res + bit; 
     res = (res >> 1) + bit; // Key dif between this and OP's code 
    } else { 
     res >>= 1; 
    } 
    bit >>= 2; 
    } 
    return res; 
} 

---

mise à jour portabilité. La plus grande puissance de 4 est nécessaire.

#include <limits.h> 
// greatest power of 4 <= a power-of-2 minus 1 
#define POW4_LE_POW2M1(n) ( ((n)/2 + 1) >> ((n)%3==0) ) 

unsigned bit = POW4_LE_POW2M1(UINT_MAX);