Quel est le nom de cet algorithme de racine carrée?

L'algorithme est le suivant:Quel est le nom de cet algorithme de racine carrée?

res <- 0 
for i from 15 downto 0 do: 
    change the ith bit of result to 1 
    if res^2 > x then: 
     change the ith bit of res back to 0 
return res

Je comprends parfaitement comment cela fonctionne, mais je ne sais pas ce que cette méthode est appelée. J'ai regardé le wiki pour les méthodes de calcul de la racine carrée mais en vain. Est-ce la méthode digit-by-digit?

(lié: How to compute the integer square root of a number in x86-64, without using div?)

Source

2017-09-29 whoshotya

Dans d'autres domaines (en particulier la conversion analogique-numérique), cette procédure est appelée "approximation successive". Dans les racines carrées, cependant, la méthode de Newton est aussi appelée «approximation successive». Vous pouvez appeler cette méthode "approximation binaire successive" pour la distinguer. Il n'est pas utilisé pour les racines carrées, car la méthode de Newton converge beaucoup plus rapidement. –

Celui-ci est assez clair ce que wikipedia appelle l'algorithme [chiffre par chiffre] (https://en.wikipedia.org/wiki/Integer_square_root#Digit-by-digit_algorithm), en utilisant des opérations au niveau du bit pour une implémentation en base 2. BTW, sur le matériel x86 moderne, le sqrt entier le plus rapide est d'utiliser le matériel '' double précision 'FP. Sur Haswell, la conversion vers/de 'double' est une latence de 4 cycles dans chaque sens, plus 16 temps de latence pour' sqrtsd'. (Et ce n'est que 3 instructions/5 uops, donc l'exécution hors service peut facilement cacher cette latence s'il y a autre chose à faire.) –

il ressemble à une ancienne relique de l'époque, où les CPU n'avaient même pas d'instructions multiplicatrices. le 'res^2' peut facilement être évité (en utilisant 2 valeurs différentes pour res et res², initialisé avec 0x8000 et 0x40000000: un-res-shiftet à droite de 1 bit, l'autre - res² - de 2 bits à chaque boucle), après que cela peut être facilement mis en œuvre sur 6502 et CPU similaires – Tommylee2k

Comme Peter Cordes mentionné dans les commentaires, c'est digit-by-digit algorithm (ici les chiffres binaires).

C'est une sorte de recherche binaire. Vous définissez le i-ème bit si le résultat au carré devient plus proche de x mais ne le dépasse pas, donc l'addition des puissances nécessaires de deux approximations résulte de mieux en mieux.

Source

2017-09-29 04:15:34 MBo

Je ne suis pas sûr que cela répond réellement à la question, cependant .. "... genre de recherche binaire" n'est pas vraiment un nom. –

@David: Mais "algorithme chiffre-par-chiffre" répond, IMO. –

Je suis d'accord. Ce n'était pas dans la réponse originale. –

Quel est le nom de cet algorithme de racine carrée?

Répondre

Questions connexes