Meilleure réponse
1ère méthode
= UNICHAR (8730) donne le symbole racine carrée dans Microsoft Excel.
Testé dans Excel 2016
2e méthode
- Aller à Insérer longlet et cliquez sur le Symbole dans le groupe de symboles .
- Sous Symboles, sélectionnez Opérateurs mathématiques dans le sous-ensemble et utilisez le symbole racine carrée.
Réponse
La plupart des processeurs modernes fournissent nativement une opération de racine carrée. Donc, avec un langage de programmation typique sur du matériel moderne typique, cest presque certainement ce que sera lopération en fin de compte.
Parlons donc de la méthode utilisée par presque tous les processeurs universels modernes.
Représentation numérique
La première chose que nous devons comprendre est de savoir comment un ordinateur représente réellement le type de nombres dont nous parlons. Ils sont stockés dans une sorte de notation scientifique.
Maintenant, le type de notation scientifique que vous connaissez peut-être où un nombre comme -134,5 est représenté par -1,345 \ fois 10 ^ {2}.
Tout nombre qui nest pas zéro peut être représenté sous cette forme, qui comporte conceptuellement trois parties: le signe (cest-à-dire le nombre positif ou négatif), la mantisse (un nombre entre 1 et 10, dont 1 mais pas 10, dans ce cas 1,345), et le exposant (la puissance à laquelle la base est élevée, dans ce cas 2; notez que lexposant peut être négatif ou nul en général).
La représentation que presque tous les ordinateurs modernes utilisent est très similaire, sauf que le nombre est stocké en utilisant une représentation binaire plutôt quune décimale. Donc, en ignorant le bit de signe et zéro (puisque trouver la racine carrée de zéro est trivial, et que la racine carrée dun nombre négatif nest pas un nombre réel), les nombres positifs sont en fait stockés sous la forme m \ times 2 ^ {e} où m est un nombre entre 1 et 2 (y compris 1 mais non compris 2).
Cette représentation est appelée «virgule flottante», en raison de la façon dont vous pouvez déplacer le point binaire (analogue à la point décimal avec lequel vous êtes peut-être familier) en ajustant lexposant.
La raison pour laquelle tout cela est important est que le CPU utilise la représentation pour aider à calculer les racines carrées. Supposons que lexposant soit pair. Alors:
\ sqrt {m \ times 2 ^ {2 \ epsilon}} = \ sqrt {m} \ times 2 ^ {\ epsilon}
De même, si lexposant est impair, alors:
\ sqrt {m \ times 2 ^ {2 \ epsilon + 1}} = \ sqrt {2} \ sqrt {m} \ times 2 ^ {\ epsilon}
Noubliez pas que m est compris entre [1,2). Cela signifie que nous avons réduit le problème du calcul de la racine carrée de nimporte quel nombre à celui du calcul de la racine carrée dun nombre dans cette plage. Ou, si nous ne voulons pas précalculer \ sqrt {2}, un nombre dans la plage [1,4). Dans tous les cas, nous avons considérablement simplifié le problème, car nous pouvons désormais utiliser des méthodes qui se comportent bien dans cette plage de nombres.
Multiplication et division
Alors maintenant que nous sommes arrivés jusquici, vous pourriez penser (si vous avez regardé les autres réponses) que la solution est maintenant dutiliser une méthode comme litération Newton-Raphson pour calculer le carré racine. Pour calculer la racine carrée de n, choisissez une estimation initiale x\_0 et répétez:
x\_ {i + 1} = \ frac {1} {2} \ left (x\_i + \ frac {n} {x\_i } \ right)
Cette réponse est fausse . Eh bien, ce n’est pas faux dans la mesure où cela vous donnera une réponse correcte. Mais cest faux en ce quaucun concepteur de CPU qui se respecte (ou aucun écrivain de bibliothèque sil devait limplémenter dans un logiciel) nimplémenterait la racine carrée à virgule flottante de cette façon. opération en binaire (qui, rappelez-vous, est en base 2, donc il suffit de déplacer le point binaire dun endroit). Cependant, lautre division est une opération très coûteuse, et dans ce cas, vous devez effectuer lopération plusieurs fois.
La division est si chère, en fait, que les processeurs modernes utilisent un algorithme itératif similaire à (mais pas réellement) litération Newton-Raphson pour effectuer la division! Il est clair que nous ne voulons pas faire cela dans le matériel, dans une boucle interne.
Sur le matériel informatique moderne, il est beaucoup moins coûteux à exécuter une opération de multiplication quune opération de division. La raison est un peu complexe à expliquer; cela a à voir avec le fait que nous pouvons installer beaucoup plus de transistors sur une puce que nous ne le pouvions auparavant, et la multiplication est un problème que vous pouvez déplacer efficacement sur beaucoup de transistors. Recherchez les arbres Wallace si vous êtes intéressé par les détails.
En tout cas, le fait est que la multiplication est une opération relativement bon marché. Donc, si nous pouvons implémenter lopération de racine carrée en termes de multiplication plutôt que de division, ce serait mieux.
Newton-Raphson, prenez deux
Voici maintenant le premier aperçu clé: au lieu de calculer la racine carrée, calculez la réciproque de la racine carrée. Autrement dit, au lieu de \ sqrt {n}, calculez \ frac {1} {\ sqrt {n}}. Il savère que cest un nombre beaucoup plus facile à calculer, et si vous avez besoin de la racine carrée, multipliez ce nombre par n et vous avez terminé.
La méthode Newton-Raphson pour la racine carrée réciproque ressemble à ceci . Si x\_0 est une estimation initiale de \ frac {1} {\ sqrt {n}}, itérer:
x\_ {i + 1} = \ frac {1} {2} x\_i \ left (3 – n {x\_i} ^ 2 \ right)
Encore une fois, la division par deux est assez bon marché, et tout le reste est multiplication et addition / soustraction.
Cest une excellente façon de mettre en œuvre dans le logiciel. De plus, il convient de souligner que dans de nombreuses situations pratiques (par exemple, normaliser un vecteur en utilisant le théorème de Pythagore), la racine carrée réciproque est en fait plus utile que la racine carrée, car la division par une racine carrée est moins efficace que la multiplication par un carré réciproque root.
Cependant, ce nest pas ainsi quil est généralement implémenté dans le matériel.
Lalgorithme de Goldschmidt
Nous pouvons maintenant regarder lalgorithme de Goldschmidt, qui calcule ensemble la racine carrée et la racine carrée réciproque.
Étant donné b\_0 = n, si nous pouvons trouver une série de nombres Y\_i tels que b\_n = b\_0 { Y\_0} ^ 2 {Y\_1} ^ 2 \ cdots {Y\_ {n-1}} ^ 2 approche 1, puis y\_n = {Y\_0} {Y\_1} \ cdots {Y\_ {n-1}} sapproche de \ frac {1} {\ sqrt {b\_0}} et x\_n = b\_0 {Y\_0} {Y\_1} \ cdots {Y\_ {n-1}} approcheront \ sqrt {b\_0}.
La série que nous utilisons est essentiellement la Étape de mise à jour Newton-Raphson:
\ begin {align *} b\_i & = b\_ {i-1} {Y\_ {i-1}} ^ 2 \\ Y\_i & = \ frac {1} {2 } (3 – b\_i) \ end {align *}
Et alors nous pouvons garder une trace de la racine carrée:
\ begin {align *} x\_0 & = n Y\_0 \\ x\_ {i} & = x\_ {i-1} Y\_i \ end {align *}
Et la racine carrée réciproque:
\ begin {align *} y\_0 & = Y\_0 \\ y\_ {i} & = y\_ {i-1} Y\_i \ end {align *}
Mais si nous gardons une trace de x\_i et y\_i, observez que b\_i = x\_ {i-1} y\_ {i-1}. Nous navons donc jamais à garder une trace de b\_i:
\ begin {align *} Y\_i & = \ frac {1} {2} \ left (3 – b\_i \ right) \\ & = 1 + \ frac {1} {2} \ left (1 – b\_i \ right) \\ & = 1 + \ frac {1} {2} \ left (1 – x\_ {i-1} y\_ {i-1} \ right ) \ end {align *}
Et maintenant, nous navons pas non plus besoin de garder une trace de Y\_i:
\ begin {align *} x\_i & = x\_ {i-1} \ gauche (1 + \ frac {1} {2} \ gauche (1 – x\_ {i-1} y\_ {i-1} \ droite) \ droite) \\ & = x\_ {i-1} + x\_ {i- 1} \ frac {1} {2} \ left (1 – x\_ {i-1} y\_ {i-1} \ right) \\ y\_i & = y\_ {i-1} \ left (1 + \ frac {1 } {2} \ left (1 – x\_ {i-1} y\_ {i-1} \ right) \ right) \\ & = y\_ {i-1} + y\_ {i-1} \ frac {1} { 2} \ left (1 – x\_ {i-1} y\_ {i-1} \ right) \ end {align *}
Il y a un calcul redondant ici, que nous pouvons supprimer, suggérant ce qui suit algorithme. Étant donné Y comme approximation de \ frac {1} {\ sqrt {n}}, définissez:
\ begin {align *} x\_0 & = n Y \\ y\_0 & = Y \ end {align * }
Ensuite, répétez:
\ begin {align *} r\_i & = \ frac {1} {2} \ left (1 – x\_i y\_i \ right) \\ x\_ {i +1} & = x\_i + x\_i r\_i \\ y\_ {i + 1} & = y\_i + y\_i r\_i \ end {align *}
Même si la division par deux est bon marché, nous pouvons éviter cela aussi en gardant une trace de h\_i = \ frac {1} {2} y\_i au lieu de y\_i. Cest lalgorithme de Goldschmidt.
Supposons que Y est une approximation de \ frac {1} {\ sqrt {n}}. Définir:
\ begin {align *} x\_0 & = n Y \\ h\_0 & = \ frac {Y} {2} \ end {align *}
Puis itérer:
\ begin {align *} r\_i & = \ frac {1} {2} – x\_i h\_i \\ x\_ {i + 1} & = x\_i + x\_i r\_i \\ h\_ {i + 1} & = h\_i + h\_i r\_i \ end {align *}
Ensuite, x\_i converge vers \ sqrt {n} et h\_n converge vers \ frac {1} {2 \ sqrt {n}}.
Implémentation de cela dans le matériel
Jusquici tout va bien. C’est certainement un algorithme très simple. Mais pourquoi est-ce mieux?
Les processeurs modernes ont souvent un circuit rapide qui effectue une opération optimisée multiplier-accumuler , souvent appelée multiplication fusionnée- ajouter, ou FMA pour faire court. Si vous avez recherché la référence aux arbres Wallace plus tôt, il devrait être clair pour vous comment FMA pourrait être presque aussi efficace quune opération de multiplication simple.
FMA est lune des primitives les plus utiles à avoir autour. Si vous avez besoin dévaluer un polynôme, par exemple:
p (x) = a\_0 + a\_1 x + a\_2 x ^ 2 + \ cdots a\_n x ^ n
vous pouvez utiliser Horner règle, qui est essentiellement un tas de FMA:
\ begin {align *} p\_ {n-1} & = a\_ {n-1} + x a\_n \\ p\_ {n-2} & = a\_ {n-2} + x p\_ {n-1} \\ & \ vdots \\ p\_1 & = a\_1 + x p\_2 \\ p\_0 & = a\_0 + x p\_1 \ end {align *}
La boucle interne de lalgorithme de Goldschmidt est constituée de trois FMA et rien dautre.Cest pourquoi cest un avantage: vous navez besoin que dun type de circuit (éventuellement un seul circuit; notez que les deux seconds FMA sont indépendants et peuvent donc bénéficier du pipelining) plus une logique de contrôle pour tout mettre en œuvre. Et cest un circuit qui est utile dans de nombreuses autres opérations, donc vous ne gaspillez pas beaucoup de matériel uniquement sur lopération de la racine carrée.
Lavant-dernière pièce du puzzle est de savoir comment obtenir une bonne initiale estimation, et la réponse courte est que la meilleure méthode consiste à utiliser une recherche de table. Même une table de taille modeste, car nous ne recherchons que des racines carrées dans une si petite gamme, est assez efficace.
La dernière pièce du puzzle est: Comment savons-nous quand nous avons terminé itérer? Et la réponse à cela est que nous connaissons la précision des nombres que nous utilisons et la qualité de l’estimation initiale. À partir de là, nous pouvons déterminer à lavance le nombre maximal ditérations requises. Donc, nous ne faisons pas de boucle en tant que telle, nous faisons simplement litération un nombre fixe de fois.