Beste antwoord
1e methode
= UNICHAR (8730) geeft het vierkantswortelsymbool in Microsoft Excel.
Getest in Excel 2016
2e methode
- Ga naar Tabblad invoegen en klik op het Symbol uit de Symbols-groep.
- Selecteer onder Symbolen wiskundige operatoren uit subset en gebruik het vierkantswortelsymbool.
Antwoord
De meeste moderne CPUs bieden native een vierkantswortelbewerking. Dus met een typische programmeertaal op typische moderne hardware, is dat vrijwel zeker wat de bewerking uiteindelijk zal zijn.
Laten we het dus hebben over de methode die bijna alle moderne algemene CPUs gebruiken.
Getalweergave
Het eerste dat we moeten begrijpen, is hoe een computer het soort getallen waar we het over hebben feitelijk weergeeft. Ze worden opgeslagen in een soort wetenschappelijke notatie.
Nu het soort wetenschappelijke notatie waarmee u misschien bekend bent, waarbij een getal als -134,5 wordt weergegeven als -1.345 \ maal 10 ^ {2}.
Elk getal dat niet nul is, kan worden weergegeven in deze vorm, die conceptueel uit drie delen bestaat: het teken (dat wil zeggen, is het getal positief of negatief), de mantisse (een getal tussen 1 en 10, inclusief 1 maar niet inclusief 10, in dit geval 1.345), en de exponent (de macht waartoe de radix wordt verhoogd, in dit geval 2; merk op dat de exponent in het algemeen negatief of nul kan zijn).
De representatie dat bijna alle moderne computers gebruiken, lijkt erg op elkaar, behalve dat het nummer wordt opgeslagen met een binaire weergave in plaats van een decimale weergave. Dus het negeren van het tekenbit en nul (aangezien het vinden van de vierkantswortel van nul triviaal is en de vierkantswortel van een negatief getal geen reëel getal is), worden positieve getallen feitelijk opgeslagen in de vorm m \ maal 2 ^ {e} waarbij m is een getal tussen 1 en 2 (inclusief 1 maar niet inclusief 2).
Deze weergave wordt “drijvende komma” genoemd, vanwege de manier waarop u het binaire punt kunt verplaatsen (analoog aan de decimaalteken waarmee u misschien bekend bent) door de exponent aan te passen.
De reden waarom dit allemaal belangrijk is, is omdat de CPU de representatie gebruikt om vierkantswortels te berekenen. Stel dat de exponent even is. Vervolgens:
\ sqrt {m \ maal 2 ^ {2 \ epsilon}} = \ sqrt {m} \ maal 2 ^ {\ epsilon}
Evenzo, als de exponent is oneven, dan:
\ sqrt {m \ maal 2 ^ {2 \ epsilon + 1}} = \ sqrt {2} \ sqrt {m} \ maal 2 ^ {\ epsilon}
Onthoud dat m in het bereik [1,2) ligt. Dit betekent dat we het probleem hebben teruggebracht tot het berekenen van de vierkantswortel van een willekeurig getal tot één van het berekenen van de vierkantswortel van een getal in dat bereik. Of, als we \ sqrt {2} niet vooraf willen berekenen, een getal in het bereik [1,4). Hoe dan ook, we hebben het probleem drastisch vereenvoudigd, omdat we nu methoden kunnen gebruiken die zich goed gedragen in dat bereik van getallen.
Vermenigvuldigen en delen
Nu we zover zijn gekomen, zou je kunnen denken (als je naar de andere antwoorden hebt gekeken) dat de oplossing nu is om een methode als Newton-Raphson-iteratie te gebruiken om het kwadraat te berekenen wortel. Om de vierkantswortel van n te berekenen, kiest u een eerste schatting x\_0 en herhaalt u:
x\_ {i + 1} = \ frac {1} {2} \ left (x\_i + \ frac {n} {x\_i } \ right)
Dit antwoord is fout . Nou, het is niet verkeerd omdat het u een juist antwoord geeft. Maar het is verkeerd omdat geen enkele zichzelf respecterende CPU-ontwerper (of welke bibliotheekschrijver dan ook als ze het in software zouden moeten implementeren) op deze manier drijvende-kommawortel zou implementeren.
De deling door twee is een erg goedkope bewerking in binair (wat, onthoud, is basis 2, dus het verschuift gewoon het binaire punt met één plaats). De andere divisie is echter een erg dure bewerking en in dit geval moet u de bewerking meerdere keren uitvoeren.
Divisie is in feite zo duur dat moderne CPUs een iteratief algoritme gebruiken dat vergelijkbaar is naar (maar niet echt) Newton-Raphson iteratie om deling uit te voeren! Het is duidelijk dat we dit niet willen doen in hardware, in een innerlijke loop.
Op moderne computerhardware is het veel goedkoper om uit te voeren een vermenigvuldigingsbewerking dan een deelbewerking. De reden waarom is een beetje ingewikkeld om uit te leggen; het heeft te maken met het feit dat we veel meer transistors op een chip kunnen plaatsen dan vroeger, en vermenigvuldiging is een probleem dat je op veel transistors efficiënt kunt overstappen. Zoek Wallace-bomen op als u in de details geïnteresseerd bent.
In ieder geval is het punt dat vermenigvuldiging een relatief goedkope operatie is. Dus als we de vierkantswortelbewerking kunnen implementeren in termen van vermenigvuldigen in plaats van delen, zou dit beter zijn.
Newton-Raphson, neem er twee
Nu komt het eerste belangrijke inzicht: in plaats van de vierkantswortel te berekenen, berekent u de reciproque van de vierkantswortel. Dat wil zeggen, in plaats van \ sqrt {n}, bereken \ frac {1} {\ sqrt {n}}. Het blijkt dat dit een veel eenvoudiger getal is om te berekenen, en als je de vierkantswortel nodig hebt, vermenigvuldig dit getal dan met n en je bent klaar.
De Newton-Raphson-methode voor wederzijdse vierkantswortel ziet er als volgt uit . Als x\_0 een eerste schatting is voor \ frac {1} {\ sqrt {n}}, herhaal dan:
x\_ {i + 1} = \ frac {1} {2} x\_i \ left (3 – n {x\_i} ^ 2 \ right)
Nogmaals, delen door twee is vrij goedkoop, en al het andere is vermenigvuldigen en optellen / aftrekken.
Dit is een geweldige manier om te implementeren het in software. Bovendien is het de moeite waard erop te wijzen dat in veel praktische situaties (bijv. Het normaliseren van een vector met behulp van de stelling van Pythagoras) de reciproque vierkantswortel eigenlijk nuttiger is dan de vierkantswortel, aangezien delen door een vierkantswortel minder efficiënt is dan vermenigvuldigen met een reciproque kwadraat. root.
Dit is echter niet hoe het gewoonlijk in hardware wordt geïmplementeerd.
Goldschmidts algoritme
We kunnen nu kijken naar het algoritme van Goldschmidt, dat de vierkantswortel en de wederzijdse vierkantswortel samen berekent.
Gegeven b\_0 = n, als we een reeks getallen Y\_i kunnen vinden zodat b\_n = b\_0 { Y\_0} ^ 2 {Y\_1} ^ 2 \ cdots {Y\_ {n-1}} ^ 2 benadert 1, dan nadert y\_n = {Y\_0} {Y\_1} \ cdots {Y\_ {n-1}} \ frac {1} {\ sqrt {b\_0}} en x\_n = b\_0 {Y\_0} {Y\_1} \ cdots {Y\_ {n-1}} zullen \ sqrt {b\_0} naderen.
De serie die we gebruiken is in wezen de Update-stap Newton-Raphson:
\ begin {align *} b\_i & = b\_ {i-1} {Y\_ {i-1}} ^ 2 \\ Y\_i & = \ frac {1} {2 } (3 – b\_i) \ end {align *}
En dan kunnen we de vierkantswortel bijhouden:
\ begin {align *} x\_0 & = n Y\_0 \\ x\_ {i} & = x\_ {i-1} Y\_i \ end {align *}
En de wederzijdse vierkantswortel:
\ begin {align *} y\_0 & = Y\_0 \\ y\_ {i} & = y\_ {i-1} Y\_i \ end {align *}
Maar als we x\_i en y\_i bijhouden, merk dan op dat b\_i = x\_ {i-1} y\_ {i-1}. We hoeven dus eigenlijk nooit b\_i bij te houden:
\ 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 *}
En nu, we hoeven Y\_i ook niet bij te houden:
\ begin {align *} x\_i & = x\_ {i-1} \ links (1 + \ frac {1} {2} \ left (1 – x\_ {i-1} y\_ {i-1} \ right) \ right) \\ & = 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 *}
Er is hier enige overtollige berekening die we kunnen verwijderen, wat het volgende suggereert algoritme. Gegeven Y als een benadering van \ frac {1} {\ sqrt {n}}, stel in:
\ begin {align *} x\_0 & = n Y \\ y\_0 & = Y \ end {align * }
Herhaal vervolgens:
\ 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 *}
Hoewel delen door twee goedkoop is, kunnen we dat ook vermijden door h\_i = \ frac {1} {2} y\_i bij te houden in plaats van y\_i. Dit is het algoritme van Goldschmidt.
Stel dat Y een benadering is van \ frac {1} {\ sqrt {n}}. Stel in:
\ begin {align *} x\_0 & = n Y \\ h\_0 & = \ frac {Y} {2} \ end {align *}
Herhaal dan:
\ 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 *}
Dan convergeert x\_i naar \ sqrt {n} en h\_n convergeert naar \ frac {1} {2 \ sqrt {n}}.
Implementatie van dit in hardware
Tot zover goed. Het is zeker een heel eenvoudig algoritme. Maar waarom is het beter?
Moderne CPUs hebben vaak een snel circuit dat een geoptimaliseerde multiply-accumulate-bewerking uitvoert, vaak fused multiply- add, of kortweg FMA. Als je de verwijzing naar Wallace-bomen eerder hebt opgezocht, zou het je duidelijk moeten zijn hoe FMA bijna net zo efficiënt kan zijn als een gewone vermenigvuldigingsoperatie.
FMA is een van de meest bruikbare primitieven die er zijn. Als je een polynoom moet evalueren, bijvoorbeeld:
p (x) = a\_0 + a\_1 x + a\_2 x ^ 2 + \ cdots a\_n x ^ n
kun je Horners regel, die in wezen een aantal FMAs is:
\ 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 *}
De binnenste lus van het algoritme van Goldschmidt is drie FMAs en niets anders.Daarom is het een voordeel: je hebt maar één soort circuit nodig (mogelijk slechts één circuit; merk op dat de tweede twee FMAs onafhankelijk zijn en dus kunnen profiteren van pipelining) plus wat besturingslogica om alles te implementeren. En het is een circuit dat nuttig is bij veel andere bewerkingen, dus je verspilt niet veel hardware alleen aan de vierkantswortelbewerking.
Het voorlaatste stukje van de puzzel is hoe je een goede initiaal krijgt. schatting, en het korte antwoord is dat de beste methode is om een tabelopzoekopdracht te gebruiken. Zelfs een tafel van bescheiden formaat, omdat we alleen op zoek zijn naar vierkantswortels in zon klein bereik, is behoorlijk efficiënt.
Het laatste stukje van de puzzel is: hoe weten we wanneer we klaar zijn itererend? En het antwoord daarop is dat we de nauwkeurigheid kennen van de getallen die we gebruiken en hoe goed de eerste schatting is. Daaruit kunnen we van tevoren het maximale aantal benodigde iteraties uitrekenen. We herhalen dus niet echt als zodanig, we doen de iteratie gewoon een vast aantal keren.