Bästa svaret
1: a metoden
= UNICHAR (8730) ger kvadratrotsymbolen i Microsoft Excel.
Testad i Excel 2016
Andra metoden
- Gå till Infoga flik och klicka på Symbolen från Symbolgruppen.
- Under Symboler väljer du matematiska operatörer från delmängd och använder kvadratrotssymbolen.
Svar
De flesta moderna processorer tillhandahåller en kvadratrotoperation. Så med ett typiskt programmeringsspråk på typisk modern hårdvara är det nästan säkert vad operationen i slutändan kommer att bli.
Så låt oss prata om metoden som nästan alla moderna allmänna processorer använder.
Nummerrepresentation
Det första vi behöver förstå är hur en dator faktiskt representerar den typ av nummer som vi pratar om. De lagras i en slags vetenskaplig notation.
Nu den typ av vetenskaplig notation som du kanske känner till där ett tal som -134,5 representeras som -1.345 \ gånger 10 ^ {2}.
Alla tal som inte är noll kan representeras i denna form, som konceptuellt har tre delar: -tecknet (det vill säga är numret positivt eller negativt), mantissa (ett tal mellan 1 och 10, inklusive 1 men inte inklusive 10, i detta fall 1.345) och exponent (den effekt som radixen höjs till, i detta fall 2; notera att exponenten kan vara negativ eller generellt noll).
Representationen som nästan alla moderna datorer använder är mycket lika, förutom att numret lagras med en binär representation snarare än en decimal. Så ignorera teckenbiten och nollan (eftersom det är trivialt att hitta kvadratroten till noll och kvadratroten till ett negativt tal inte är ett reellt tal) sparas positiva tal faktiskt i formen m \ gånger 2 ^ {e} där m är ett tal mellan 1 och 2 (inklusive 1 men inte inklusive 2).
Denna representation kallas ”flytpunkt” på grund av hur du kan flytta binärpunkten (analogt med decimal som du kanske känner till) runt genom att justera exponenten.
Anledningen till att allt detta är viktigt är att CPU använder representationen för att beräkna kvadratrötter. Antag att exponenten är jämn. Sedan:
\ sqrt {m \ times 2 ^ {2 \ epsilon}} = \ sqrt {m} \ times 2 ^ {\ epsilon}
På samma sätt, om exponenten är udda, då:
\ sqrt {m \ times 2 ^ {2 \ epsilon + 1}} = \ sqrt {2} \ sqrt {m} \ times 2 ^ {\ epsilon}
Kom ihåg att m är i intervallet [1,2]. Det betyder att vi har minskat problemet med att beräkna kvadratroten för valfritt tal till en för att beräkna kvadratroten för ett tal i det intervallet. Eller om vi inte vill förberäkna \ sqrt {2}, ett nummer i intervallet [1,4). Hur som helst har vi förenklat problemet dramatiskt, eftersom vi nu kan använda metoder som beter sig bra i det numreringsområdet.
Multiplikation och division
Så nu när vi har kommit så långt, kanske du tror (om du har tittat på de andra svaren) att lösningen nu är att använda en metod som Newton-Raphson iteration för att beräkna kvadraten rot. För att beräkna kvadratroten av n, välj en initial gissning x\_0 och upprepa:
x\_ {i + 1} = \ frac {1} {2} \ left (x\_i + \ frac {n} {x\_i } \ höger)
Detta svar är fel . Det är inte fel genom att det ger dig ett korrekt svar. Men det är fel genom att ingen självrespektande CPU-designer (eller någon biblioteksförfattare om de var tvungna att implementera den i programvara) skulle implementera floating-point kvadratrot på detta sätt.
Uppdelningen med två är en mycket billig operation i binär (som, kom ihåg, är bas 2, så det flyttar bara binärpunkten med ett ställe). Den andra divisionen är dock en mycket dyr operation, och i det här fallet måste du utföra operationen flera gånger.
Division är faktiskt så dyr, att moderna processorer använder en iterativ algoritm som liknar till (men inte faktiskt) Newton-Raphson iteration att utföra division! Det är uppenbart att vi inte vill göra detta i hårdvara, i en inre slinga.
På modern datorhårdvara är det mycket billigare att utföra en multiplikationsoperation än en divisionsoperation. Anledningen till varför är lite komplex att förklara; det har att göra med det faktum att vi kan passa mycket mer transistorer på ett chip än vad vi brukade kunna, och multiplikation är ett problem som du kan flytta till många transistorer effektivt. Slå upp Wallace-träd om du är intresserad av detaljerna.
Hur som helst är poängen att multiplikation är en relativt billig operation. Så om vi kan implementera kvadratrotoperationen i termer av multiplikation snarare än division, skulle det vara bättre.
Newton-Raphson, ta två
Nu kommer den första nyckelinsikten: I stället för att beräkna kvadratroten, beräkna ömsesidiga av kvadratroten. I stället för \ sqrt {n}, beräkna \ frac {1} {\ sqrt {n}}. Det visar sig att detta är ett mycket lättare nummer att beräkna, och om du behöver kvadratroten, multiplicera detta tal med n så är du klar.
Newton-Raphson-metoden för ömsesidig kvadratrot ser ut så här . Om x\_0 är en initial uppskattning till \ frac {1} {\ sqrt {n}}, iterera:
x\_ {i + 1} = \ frac {1} {2} x\_i \ left (3 – n {x\_i} ^ 2 \ höger)
Återigen är delningen med två ganska billig och allt annat är multiplikation och addition / subtraktion.
Detta är ett bra sätt att implementera det i programvara. Dessutom är det värt att påpeka att den ömsesidiga kvadratroten faktiskt är mer användbar än kvadratroten, eftersom delning med en kvadratrot är mindre effektiv än att multiplicera med en ömsesidig kvadrat root.
Så här implementeras det vanligtvis inte i hårdvara.
Goldschmidts algoritm
Vi kan nu titta på Goldschmidts algoritm, som beräknar kvadratrot och ömsesidig kvadratrot tillsammans.
Givet b\_0 = n, om vi kan hitta en serie siffror Y\_i så att b\_n = b\_0 { Y\_0} ^ 2 {Y\_1} ^ 2 \ cdots {Y\_ {n-1}} ^ 2 närmar sig 1, så kommer y\_n = {Y\_0} {Y\_1} \ cdots {Y\_ {n-1}} närmar sig \ frac {1} {\ sqrt {b\_0}} och x\_n = b\_0 {Y\_0} {Y\_1} \ cdots {Y\_ {n-1}} närmar sig \ sqrt {b\_0}.
Serien som vi använder är i huvudsak den Newton-Raphson uppdateringssteg:
\ begin {align *} b\_i & = b\_ {i-1} {Y\_ {i-1}} ^ 2 \\ Y\_i & = \ frac {1} {2 } (3 – b\_i) \ end {align *}
Och då kan vi hålla reda på kvadratroten:
\ begin {align *} x\_0 & = n Y\_0 \\ x\_ {i} & = x\_ {i-1} Y\_i \ end {align *}
Och den ömsesidiga kvadratroten:
\ begin {align *} y\_0 & = Y\_0 \\ y\_ {i} & = y\_ {i-1} Y\_i \ end {align *}
Men om vi håller reda på x\_i och y\_i, observera att b\_i = x\_ {i-1} y\_ {i-1}. Så vi behöver aldrig hålla reda på 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 *}
Och nu behöver vi inte heller hålla reda på Y\_i:
\ begin {align *} x\_i & = x\_ {i-1} \ vänster (1 + \ frac {1} {2} \ vänster (1 – x\_ {i-1} y\_ {i-1} \ höger) \ höger) \\ & = 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} \ vänster (1 – x\_ {i-1} y\_ {i-1} \ höger) \ höger) \\ & = y\_ {i-1} + y\_ {i-1} \ frac {1} { 2} \ left (1 – x\_ {i-1} y\_ {i-1} \ right) \ end {align *}
Det finns lite överflödig beräkning här, som vi kan ta bort, vilket föreslår följande algoritm. Givet Y som en approximation till \ frac {1} {\ sqrt {n}}, ställ in:
\ begin {align *} x\_0 & = n Y \\ y\_0 & = Y \ end {align * }
Sedan itera:
\ börja {align *} r\_i & = \ frac {1} {2} \ vänster (1 – x\_i y\_i \ höger) \\ x\_ {i +1} & = x\_i + x\_i r\_i \\ y\_ {i + 1} & = y\_i + y\_i r\_i \ end {align *}
Även om delningen med två är billig kan vi också undvika det genom att hålla reda på h\_i = \ frac {1} {2} y\_i istället för y\_i. Detta är Goldschmidts algoritm.
Antag att Y är en approximation till \ frac {1} {\ sqrt {n}}. Set:
\ begin {align *} x\_0 & = n Y \\ h\_0 & = \ frac {Y} {2} \ end {align *}
Då iterera:
\ 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 *}
Sedan konvergerar x\_i till \ sqrt {n} och h\_n konvergerar till \ frac {1} {2 \ sqrt {n}}.
Implementera detta i hårdvara
Hittills så bra. Det är verkligen en mycket enkel algoritm. Men varför är det bättre?
Moderna processorer har ofta en snabb krets som utför en optimerad multiplicera-ackumulera operation , ofta kallad smält multiplicera- lägg till, eller FMA för kort. Om du letade upp hänvisningen till Wallace-träd tidigare, bör det vara klart för dig hur FMA kan vara nästan lika effektiv som en rak multiplikationsoperation.
FMA är en av de mest användbara primitiverna att ha runt. Om du behöver utvärdera ett polynom, till exempel:
p (x) = a\_0 + a\_1 x + a\_2 x ^ 2 + \ cdots a\_n x ^ n
kan du använda Horners regel, som i huvudsak är en massa FMA: er:
\ 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 *}
Den inre slingan i Goldschmidts algoritm är tre FMA och inget annat.Det är därför det är en fördel: du behöver bara en typ av krets (eventuellt bara en krets; notera att de andra två FMA: erna är oberoende och så kan dra nytta av pipelining) plus viss kontrolllogik för att implementera allt. Och det är en krets som är användbar i många andra operationer, så du slösar inte mycket hårdvara bara med kvadratrotoperationen.
Den näst sista biten i pusslet är hur man får en bra initial uppskattning, och det korta svaret är att den bästa metoden är att använda en tabelluppslagning. Till och med ett blygsamt bord, eftersom vi bara letar efter kvadratrötter i ett så litet intervall, är ganska effektivt.
Den sista biten i pusslet är: Hur vet vi när vi är klara? iterera? Och svaret på det är att vi vet hur exakta siffrorna vi använder och hur bra den ursprungliga uppskattningen är. Utifrån det kan vi räkna ut det maximala antalet iterationer som krävs i förväg. Så vi slingrar faktiskt inte som sådana, vi gör bara iterationen ett fast antal gånger.